淺談圖論與其在資訊工程的應用

在這個離散數學專欄，要和大家簡單介紹在離散數學中具有重要應用的圖論 (graph theory)。

圖論起源於 1736 年，數學家尤拉 (Leonhard Euler) 解答了困惑柯尼斯堡 (今日俄羅斯加里寧格勒) 居民的問題，稱為柯尼斯堡七橋問題 (Seven Bridges of Königsberg)。當時為東普魯士首都的哥尼斯堡，市區橫跨普萊格爾河兩岸，河中有兩個小島，這兩個小島與河岸間共有七座橋連接。閒暇時人們經常在這七座橋上散步，某一天有人提出了：能不能從河岸或小島的某一個地方出發，每座橋都只走過一遍，最後又回到原出發點。這個問題看似簡單，但許多人嘗試了各式各樣的走法，始終找不到每座橋都只走過一遍的走法。尤拉將這個問題抽象化為點與邊的觀念，證明了每座橋都只走過一遍的散步方式是不可能的，也因此開啟了圖論這一個新的領域。

圖1(a) 是尤拉時代的柯尼斯堡地圖，圖上畫出了當時七座橋的實際位置，河流和橋梁使用特別的顏色標記出來。若將實際地圖簡化，只考慮河岸、小島與七座橋的相對位置，則可得到如圖2(b)的簡圖。尤拉考慮將河岸、小島與七座橋之間的相連關係以點和邊的方式表示，則會得到如圖3(b)的圖。 在這個圖中，圓形的稱為點，分別代表地圖中的四個區域，其中藍色點代表北岸、紅色的點代表南岸、橘色的點代表左邊的小島，白色的點代表右邊的小島。將點和點連起來的線稱為邊，代表連接兩個陸地的橋。例如，北岸與左小島有兩座橋相連，所以藍色的點和橘色的點會有兩條邊。

當尤拉用圖的方式思考，原先柯尼斯堡居民一直無法解決的七橋問題，突然變得簡單了。尤拉發現如果每一座橋只能走過一次，且每一座橋都要經過，最後又要回到原出發點。那麼對每一個區域而言，和這個區域相連的橋，一定可以分成兩類，一類是走進這個區域的橋，一類是離開這個區域的橋。因為每一座橋都要經過，所以不會有橋不屬於這兩類，因為每一座橋只能走過一次，所以不會有橋同時屬於這兩類。接著因為要從原出發的區域開始，中間經過其他的區域，再回到原點。所以對於原出發的區域而言，有多少橋從這個區域離開，就要有多少橋能夠回到這個區域。同時就中間經過的區域而言，這些區域只是經過，所有多少橋可以走進這個區域就有多少橋可以離開這個區域。因此得到了一個簡單的結論，對每一個區域而言，可以走進這個區域的橋的數目要和可以離開這個區域的橋的數目一樣多。雖然目前沒有走法，無法確認哪座橋是走進的橋，哪座橋是離開的橋，但可以確定的是連接一個區域的橋的數目一定要是偶數。尤拉根據這個觀念，檢查圖1(c)上面的點，很容就發現，這個圖上的點並不符合與其相鄰的邊的數目都是偶數的這個性質，於是就解出了柯尼斯堡七橋問題是不可能的事。

在圖論中吸引了更多注意的一個問題是四色地圖問題 (four-color map problem). Frank Guthrie, 笛摩根 (Augustus De Morgan) 較早的一個學生, 發現了他可以用四個不同顏色將英國地圖上色而沒有兩個相鄰地區有相同的顏色. 他要他的兄弟, 在 1852 年是笛摩根的一個學生, 去請教笛摩根他的推測, 四個顏色足以將每一個地圖上色而沒有相鄰的兩個區域會是相同顏色, 是否為真. 笛摩根公布了這個問題, 而多年來許多人致力於解決此問題.

在 1879 年, Alfred Bray Kempe, 曾在劍橋大學研究數學的一位律師, 發表了四色推測的一個證明, 受到高度讚揚. 不幸的, 他的證明有一個致命的錯誤. 這個定理最後是由依利諾大學的美國數學家 Kenneth Appel 和 Wolfgang Haken 所證明. 他們的證明是以 Kempe 的工作為基礎, 並使用超過 1000 小時的電腦運算時間來檢查 1936 個不同地圖型態. 他們的證明, 第一個使用電腦所得到的重要數學結果, 一開始就遭遇到相當多懷疑的態度. 幾年之後, 型態的數目降低了, 但直至今日沒有一個證明不需要重用電腦。

圖 (graph) G 是由稱為頂點 (vertices) 的物件有限集合 V, 稱為邊 (edges) 的物件的有限集合 E, 以及指定給每一個邊的一個子集合 的函數 所構成, 其中 v 和 w 為頂點 (且可能為相同的頂點). 當我們需要對 G 的部分加以命名時我們會寫成 . 若 e 為一個邊, 且 , 我們稱 e 為在 v 和 w 之間的邊，且 e 由 v 和 w 決定。頂點 v 和 w 稱為 e 的端點 (end points). 若在 v 和 w 之間只有一個邊, 我們通常將 e 視為集合 . 這應該不會導致任何混淆. 這樣的情形限制了只能有有限數目的頂點, 而此處討論所有的圖都有有限數目的頂點。

圖經常以圖形來表示, 以一個點來表示每一個頂點而以一條線來表示每一個邊. 在例題 1 中的 G 表示於圖 2. 我們通常省略邊的名稱, 因為它們沒有固有的意義. 而且, 我們可能會想要在邊上放置其他更有用的標記. 若圖的資訊對討論已經充分足夠, 有時我們也會省略頂點的標記。

圖通常被用來記錄關係(relation)或關連(connections)的資訊. 一個在 和 之間的邊指出在物件 和 之間的一個關連. 在一個圖的圖形表示法中, 關連是最重要的資訊, 而通常許多不同的圖形可以表示相同的圖。

在這裡，我們將討論圖論所使用的一大類問題. 第一類問題的任務是要走出一條路徑使得圖中每一個邊恰使用一次. 可能需要也可能不需開始且結束於相同頂點. 一個簡單的例子是一般的謎題, 要求玩家要追蹤一個幾何圖形而不使用鉛筆在紙上做記號, 或通過一個邊超過一次.

在一個圖 G 中的一個路徑稱為尤拉路徑 (Euler path) 若它包含每一個邊恰一次. 一個尤拉迴路(Euler circuit)是一個同時為迴路的尤拉路徑. 尤拉 (Leonhard Euler, 1707-1783) 在數學的許多領域有重要貢獻. “尤拉路徑” 及 “尤拉迴路” 這些名稱肯定了他在七橋問題 (Königsberg Bridge problem) 的貢獻.

(未完）

本專欄作者：亞洲大學 資工系 呂威甫

參考資料：離散數學(最新修訂版)。呂威甫、施文慈譯。碁峰出版社。