> form [維基百科](https://zh.wikipedia.org/wiki/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98)

# 七橋問題

## 故事
柯尼斯堡七橋問題（德語：Königsberger Brückenproblem；英語：Seven Bridges of Königsberg）是圖論中的著名問題。這個問題是基於一個現實生活中的事例：

當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？

## 解決方式

萊昂哈德·歐拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年發表在論文《柯尼斯堡的七橋》中，證明符合條件的走法並不存在，也順帶提出和解決了一筆畫問題。

這篇論文在聖彼得堡科學院發表，成為圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。

這樣若從某點出發後最後再回到這點，則這一點的線數必須是偶數，這樣的點稱為偶頂點。相對的，連有奇數條線的點稱為奇頂點。歐拉論述了，由於柯尼斯堡七橋問題中存在4個奇頂點，它無法實現符合題意的遍歷。


歐拉把問題的實質歸於一筆畫問題，即判斷一個圖是否能夠遍歷完所有的邊而沒有重複，而柯尼斯堡七橋問題則是一筆畫問題的一個具體情境。

歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則，從而解決了「一筆畫問題」。

**對於一個給定的連通圖，如果存在超過兩個的奇頂點，那麼滿足要求的路線便不存在了，且在n>0的情況下，有2n個奇頂點的圖至少需要n筆畫出。如果只有兩個奇頂點，則可從其中任何一地出發完成一筆畫。若所有點均為偶頂點，則從任何一點出發，所求的路線都能實現，他還說明了怎樣快速找到所要求的路線。**

不少數學家都嘗試去解析這類事例。而這些解析，最後發展成為了數學中的圖論。

# 一筆畫問題

一筆畫問題（Eulerian graph）是圖論中一個著名的問題。一筆畫問題起源於柯尼斯堡七橋問題。數學家歐拉在他1736年發表的論文《柯尼斯堡的七橋》中不僅解決了七橋問題，也提出了一筆畫定理，順帶解決了一筆畫問題。一般認為，歐拉的研究是圖論的開端。

與一筆畫問題相對應的一個圖論問題是哈密頓路徑問題。

能夠在不重複折返的前提下一筆畫寫出或一次走完該路徑的條件，是文字、圖形、路徑的奇頂點的數目正好是0個或2個時，而如果奇頂點的數目兩個時，必須正好為起點或終點，奇頂點是指該點延展出奇數數目的方向，例如T字路口延展出三條道路方向，而線段的端點也是只有一個方向的奇頂點

## 問題的提出

一筆畫問題是柯尼斯堡問題經抽象化後的推廣，是圖遍歷問題的一種。在柯尼斯堡問題中，如果將橋所連接的地區視為點，將每座橋視為一條邊，那麼問題將變成：對於一個有著四個頂點和七條邊的連通圖 $G(S,E)$，能否找到一個恰好包含了所有的邊，並且沒有重複的路徑。

歐拉將這個問題推廣為：對於一個給定的圖，怎樣判斷是否存在著一個恰好包含了所有的邊，並且沒有重複的路徑？這就是一筆畫問題。用圖論的術語來說，就是判斷這個圖是否是一個能夠遍歷完所有的邊而沒有重複。這樣的圖現稱為**歐拉圖**。這時遍歷的路徑稱作**歐拉路徑**（一個環或者一條鏈），如果路徑閉合（一個圈），則稱為**歐拉迴路**。

一筆畫問題的推廣是多筆畫問題，即對於不能一筆畫的圖，探討最少能用多少筆來畫成。

## **定理一**
連通的無向圖 $G$ 有歐拉路徑的充要條件是：$G$ 中奇頂點（連接的邊數量為奇數的頂點）的數目等於 0 或者 2。

連通的無向圖 $G$ 是歐拉環（存在歐拉迴路）的充要條件是：$G$ 中每個頂點的度都是偶數。[2]

## **證明：**
* **必要性：**
如果一個圖能一筆畫成，那麼對每一個頂點，要麼路徑中「進入」這個點的邊數等於「離開」這個點的邊數：這時點的度為偶數。要麼兩者相差一：這時這個點必然是起點或終點之一。注意到有起點就必然有終點，因此奇頂點的數目要麼是 0，要麼是 2。

* **充分性：**
如果圖中沒有奇頂點，那麼隨便選一個點出發，連一個環 $C_1$。如果這個環就是原圖，那麼結束。如果不是，那麼由於原圖是連通的，$C_1$ 和原圖的其它部分必然有公共頂點 $s_1$。從這一點出發，在原圖的剩餘部分中重複上述步驟。由於原圖是連通圖，經過若干步後，全圖被分為一些環。由於兩個相連的環就是一個環，原來的圖也就是一個歐拉環了。

如果圖中有兩個奇頂點 $u$ 和 $v$，那麼加多一條邊將它們連上後得到一個無奇頂點的連通圖。由上知這個圖是一個環，因此去掉新加的邊後成為一條路徑，起點和終點是 $u$ 和 $v$。證畢。

---

連通無向圖有歐拉路徑的充要條件也可以寫作「圖中奇頂點數目不多於 2 個」，這是因為奇頂點數目不可能是 1 個。實際上，連通無向圖中，奇頂點的數目總是偶數。

對於不連通的無向圖，如果有兩個互不連通的部分都包含至少一條邊，那麼顯然不能一筆畫。只有當此圖的邊全都在某一個連通部分中（即其它的連通部分都是一個個孤立的頂點，度數為 0），並滿足連通無向圖關於一筆畫的充要條件，而該圖才能一筆畫。也即是說，可以一筆畫的（無向）圖如果不是連通圖，就必定是一個可以一筆畫的連通圖與若干個孤立頂點的組合。

除了用頂點的度數作為判定的充要條件，還可以用圖中邊的特性來作為歐拉迴路存在的判定準則。連通的無向圖 $G$ 中存在歐拉迴路，等價於圖 $G$ 所有的邊可以劃分為若干個環的不交並。具體來說，等價於存在一系列的環 $C_1, C_2, \cdots, C_m$，使得圖 $G$ 里的每一條邊都恰好屬於某一個環。

## **定理二**
如果連通無向圖 $G$ 有 $2k$ 個奇頂點，那麼它可以用 $k$ 筆畫成，並且至少要用 $k$ 筆畫成。[2]

## **證明：**
將這 $2k$ 個奇頂點分成 $k$ 對後分別連起，則得到一個無奇頂點的連通圖。由上知這個圖是一個環，因此去掉新加的邊後至多成為 $k$ 條歐拉路徑，因此必然可以用 $k$ 筆畫成。但是假設全圖可以分為 $q$ 條歐拉路徑，則由定理一知，每條鏈中只有不多於兩個奇頂點，於是 $2q \geq 2k$。因此必定要 $k$ 筆畫成。

---

**有向圖的一筆畫**
對有向圖來說，一筆畫不僅指遍歷所有邊，而且要遵循正確的方向。嚴謹地說，一個連通有向圖 $G$ 有歐拉路徑，指存在一個頂點，從它出發，沿著有向邊的方向，可以不重複地遍歷圖中所有的邊。有向圖的歐拉迴路則是指可以從某一頂點開始，沿有向邊的方向不重複地遍歷所有邊，然後回到原來出發的頂點。用類似於定理一中證明的思路，可以得到有向圖一筆畫的判定準則：

一個連通的有向圖可以表示為一條從頂點 $u$ 到 $v$ 的（不閉合的）歐拉路徑的充要條件是：
$u$ 的出度（從這個頂點發出的有向邊的數量）比入度（指向這個頂點的有向邊的數量）多 1，
$v$ 的出度比入度少 1，而其它頂點的出度和入度都相等。

一個連通的有向圖是歐拉環（存在歐拉迴路）的充要條件是以下兩個之一：
- 每個頂點的出度和入度都相等；
- 存在一系列的（有向）環 $C_1, C_2, \cdots, C_m$，使得圖 $G$ 里的每一條邊都恰好屬於某一個環。