圖論

圖論（英語：Graph theory），是組合數學分支，和其他數學分支如群論、矩陣論、拓撲學有着密切關係。

一個由6個頂點和7條邊組成的圖

圖是圖論的主要研究對象。圖是由若干給定的頂點及連接兩頂點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係。頂點用於代表事物，連接兩頂點的邊則用於表示兩個事物間具有這種關係。

圖論起源於著名的柯尼斯堡七橋問題。該問題於1736年被歐拉解決，因此普遍認為歐拉是圖論的創始人。^[1]

圖論的研究對象相當於一維的單純複形^[2]。

歷史

柯尼斯堡七橋問題

一般認為，歐拉於1736年出版的關於柯尼斯堡七橋問題的論文是圖論領域的第一篇文章^[3]。此問題被推廣為著名的歐拉路問題，亦即一筆畫問題。而此論文與范德蒙的一篇關於騎士週遊問題的文章，則是繼承了萊布尼茨提出的「位置分析」的方法。歐拉提出的關於凸多邊形頂點數、棱數及面數之間的關係的歐拉公式與圖論有密切聯繫，此後又被柯西等人^[4][5]進一步研究推廣，成了拓撲學的起源。1857年，哈密頓發明了「環遊世界遊戲（英語：icosian game）」（icosian game），與此相關的則是另一個廣為人知的圖論問題「哈密頓路徑問題」。

西爾維斯特於1878年發表在《自然》上的一篇論文中首次提出「圖」這一名詞^[6]。

歐拉的論文發表後一個多世紀，凱萊研究了在微分學中出現的一種數學分析的特殊形式，而這最終將他引向對一種特殊的被稱為「樹」的圖的研究。由於有機化學中有許多樹狀結構的分子，這些研究對於理論化學有着重要意義，尤其是其中關於具有某一特定性質的圖的計數問題。除凱萊的成果外，波利亞也於1935至1937年發表了一些成果，1959年，De Bruijn（英語：Nicolaas Govert de Bruijn）做了一些推廣。這些研究成果奠定了圖的計數理論的基礎。凱萊將他關於樹的研究成果與當時有關化合物的研究聯繫起來，而圖論中有一部分術語正是來源於這種將數學與化學相聯繫的做法。

四色問題可謂是圖論研究史上最著名也是產生成果最多的問題之一：「是否任何一幅畫在平面上的地圖都可以用四種顏色染色，使得任意兩個相鄰的區域不同色？」這一問題由法蘭西斯·古德里於1852年提出，而最早的文字記載則出現在德摩根於1852年寫給哈密頓的一封信上。包括凱萊、肯普（英語：Alfred Kempe）等在內的許多人都曾給出過錯誤的證明。泰特（英語：Peter Guthrie Tait）（Peter Guthrie Tait）、希伍德、拉姆齊和Hadwige（英語：Hugo Hadwiger）（Hugo Hadwiger）對此問題的研究與推廣引發了對嵌入具有不同虧格的曲面的圖的着色問題的研究。一百多年後，四色問題仍未解決。1969年，Heinrich Heesch（英語：Heinrich Heesch）發表了一個用計算機解決此問題的方法。1976年，凱尼斯·阿佩爾和沃夫岡·哈肯藉助計算機給出了一個證明，此方法按某些性質將所有地圖分為1936類並利用計算機一一驗證了它們可以用四種顏色染色。但此方法由於過於複雜，在當時未被廣泛接受。

1860年之1930年間，若當、庫拉托夫斯基和惠特尼從之前獨立於圖論發展的拓撲學中吸取大量內容進入圖論，而現代代數方法的使用更讓圖論與拓撲走上共同發展的道路。其中應用代數較早者如物理學家基爾霍夫於1845年發表的基爾霍夫電路定律。

圖論中概率方法的引入，尤其是埃爾德什和Alfréd Rényi（英語：Alfréd Rényi）關於隨機圖連通的漸進概率的研究使得圖論產生了新的分支隨機圖論。

定義

圖論中有許多定義，以下是一些與之相關最基本的定義。

無向圖

有三個邊和三個頂點的圖。

圖論中，圖是有序對 ${\displaystyle G=(V,E)}$，其中 ${\displaystyle V}$ 是點集；${\displaystyle E\subseteq \left\{\left\{x,y\right\}:(x,y)\in V^{2},x\neq y\right\}}$ 是邊集，由所有無序頂點對構成（換句話說，邊連接了頂點對）。對於一個邊 ${\displaystyle \left\{x,y\right\}}$，頂點 ${\displaystyle x,y}$ 被稱作是邊的端點，邊則被稱為連接了此兩個點。

為了避免歧異，上述的定義被更精準地稱作無向簡單圖。

事實上可以推廣為更一般的定義：圖是有序三元組 ${\displaystyle G=(V,E,\phi )}$，其中 ${\displaystyle V}$ 是點集；${\displaystyle E}$ 是邊集（此時 ${\displaystyle E}$ 不再如前面限定是該集合的子集）；而 ${\displaystyle \phi :E\to \left\{\left\{x,y\right\}:(x,y)\in V^{2}\right\}}$ 將每個邊映射到一個無序頂點對（於是邊連接了頂點對）。此時的定義就允許自環、重邊的出現，其中自環是兩端點相同的邊，重邊是兩個或多個連接相同端點的邊。

為了避免歧異，上述的定義被更精準地稱作無向圖。

${\displaystyle V,E}$ 的元素個數通常都是有限的；並且如果個數是無限的，有許多著名的性質都發生變化，甚至不再正確。此外，${\displaystyle V}$ 通常不被接受是空集合，而 ${\displaystyle E}$ 則被接受為空集合。以下再給出一些圖論中的定義：圖的階是其頂點個數 ${\displaystyle |V|}$，圖的邊數是 ${\displaystyle |E|}$，頂點的度所有邊的端點中此頂點出現的次數（自環會被算兩次）。

圖論問題

圖的計數

子圖相關問題

子圖同構問題：給定兩個圖${\displaystyle G}$和${\displaystyle H}$，問${\displaystyle G}$中是否存在一個子圖與${\displaystyle H}$同構。這是一個NP完全問題。

• 哈密頓迴路問題可視為一個子圖同構問題，即給定一個${\displaystyle n}$個頂點的圖，問是否存在一個子圖與具有${\displaystyle n}$個頂點的圈同構。

一類相關的常見問題要求在給定圖中尋找符合某些條件的最大子圖，其中有很多是NP完全的，如：

• 分團問題：在給定圖中尋找最大的團（NP完全）。

類似地，有些問題要求尋找符合某些條件的最大導出子圖，如：

• 最大獨立集問題：在給定圖中尋找最大的無邊的導出子圖，亦即獨立集（NP完全）。

平面圖判定：判定給定的圖是否是平面圖（此問題與子圖的關係，參見庫拉托夫斯基定理）

一個尚未解決的與子圖相關的猜想，重構猜想（Reconstruction conjecture）：一個n階圖是否能夠由其所有n-1階導出子圖唯一確定？

染色

• 點色數（Chromatic number）
• 邊色數（Chromatic index）
• 色多項式

許多問題與將圖以特定方式染色有關，如：

• 四色問題
• 完美圖問題（strong perfect graph theorem）
• 列表染色問題，列表邊染色問題
• 曲面染色

路徑問題

• 柯尼斯堡七橋問題
• 哈密頓迴路問題
• 最小生成樹問題
• 中國郵路問題
• 最短路問題
• 斯坦納樹
• 旅行商問題（NP困難）

網絡流與匹配

• 最大流問題，最小割問題，最大流最小割定理
• 最小費用最大流問題
• 二分圖及任意圖上的最大匹配
• 帶權二分圖的最大權匹配

覆蓋問題

• 最大團
• 最大獨立集
• 最小覆蓋集
• 最小支配集

重要的算法

• 戴克斯特拉算法(D.A)
• 克魯斯卡爾算法(K.A)
• 普里姆算法(P.A)
• 拓撲排序演算法(TSA)
• 關鍵路徑演算法(CPA)
• 廣度優先搜索算法(BFS)
• 深度優先搜索算法(DFS)

參見

• 數學主題

• 組合數學
• 三間小屋問題

註釋

1. 卜月華; 吳建專; 顧國華; 殷翔, 《图论及其应用》 第一版, 東南大學出版社: 1-2, 2007
2. Alexander Grigor』yan, Yuri Muranov, Shing-Tung Yau, Graphs associated with simplicial complexes (PDF), 2012年9月 [2018-05-24], （原始內容 (PDF)存檔於2022-06-13）
3. Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986
4. Cauchy, A. L., Recherche sur les polyèdres - premier mémoire, Journal de l'École polytechnique, 1813,, 9 (Cahier 16): 66–86.
5. L'Huillier, S.-A.-J., Mémoire sur la polyèdrométrie, Annales de Mathématiques, 1812–1813, 3: 169–189.
6. Sylvester, James Joseph. Chemistry and Algebra. Nature. 1878, 17: 284. doi:10.1038/017284a0.

參考文獻

• Berge, Claude, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II, Paris: Dunod, 1958. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
• Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986.
• Bondy, J.A.; Murty, U.S.R., Graph Theory, Springer, 2008, ISBN 978-1-84628-969-9.
• Bondy, Riordan, O.M, Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003.
• Chartrand, Gary, Introductory Graph Theory, Dover, 1985, ISBN 0-486-24775-9.
• Gibbons, Alan, Algorithmic Graph Theory, Cambridge University Press, 1985.
• Reuven Cohen, Shlomo Havlin, Complex Networks: Structure, Robustness and Function, Cambridge University Press, 2010
• Golumbic, Martin, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.
• Harary, Frank, Graph Theory, Reading, MA: Addison-Wesley, 1969.
• Harary, Frank; Palmer, Edgar M., Graphical Enumeration, New York, NY: Academic Press, 1973.
• Mahadev, N.V.R.; Peled, Uri N., Threshold Graphs and Related Topics, North-Holland, 1995.
• Mark Newman, Networks: An Introduction, Oxford University Press, 2010.

外部連結

線上圖書資料

• Graph Theory with Applications (1976) by Bondy and Murty
• Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs (2006) by Hartmann and Weigt
• Digraphs: Theory Algorithms and Applications（頁面存檔備份，存於互聯網檔案館） 2007 by Jorgen Bang-Jensen and Gregory Gutin
• Graph Theory, by Reinhard Diestel（頁面存檔備份，存於互聯網檔案館）

其他相關資料

• Hazewinkel, Michiel (編), Graph theory, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
• Graph theory tutorial（頁面存檔備份，存於互聯網檔案館）
• A searchable database of small connected graphs
• Image gallery: graphs
• Concise, annotated list of graph theory resources for researchers
• rocs（頁面存檔備份，存於互聯網檔案館） — a graph theory IDE
• Graph Theory Software（頁面存檔備份，存於互聯網檔案館）