图论

一个由6个顶点和7条边组成的图

图论（英語：Graph theory），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。

图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。

图论的研究对象相当于一维的单纯複形。

历史

柯尼斯堡七桥问题

一般认为，欧拉于1736年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章。此问题被推广为著名的欧拉路问题，亦即一笔画问题。而此论文与范德蒙的一篇关于骑士周游问题的文章，则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西等人进一步研究推广，成了拓扑学的起源。1857年，哈密顿发明了“環遊世界遊戲”（icosian game），与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

西尔维斯特于1878年发表在《自然》上的一篇论文中首次提出“图”这一名词。

欧拉的论文发表后一个多世纪，凯莱研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚也于1935至1937年发表了一些成果，1959年，De Bruijn做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

四色问题可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由法兰西斯·古德里于1852年提出，而最早的文字记载则出现在德摩根于1852年写给哈密顿的一封信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特（Peter Guthrie Tait）、希伍德、拉姆齐和Hadwige（Hugo Hadwiger）对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一个用计算机解决此问题的方法。1976年，凱尼斯·阿佩爾和沃夫冈·哈肯借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。

1860年之1930年间，若当、库拉托夫斯基和惠特尼从之前独立于图论发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家基尔霍夫于1845年发表的基尔霍夫电路定律。

图论中概率方法的引入，尤其是埃尔德什和Alfréd Rényi关于随机图连通的渐进概率的研究使得图论产生了新的分支随机图论。

定義

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

無向圖

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

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

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

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

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

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

图论问题

子图相关问题

子图同构问题：给定两个图$G$和$H$，问$G$中是否存在一个子图与$H$同構。这是一个NP完全问题。

• 哈密顿回路问题可视为一个子图同构问题，即给定一个$n$个顶点的图，问是否存在一个子图与具有$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)

参见

• 组合数学
• 三間小屋問題

參考文獻

• 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（页面存档备份，存于互联网档案馆）