历史

  柯尼斯堡七桥问题

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

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

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

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

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

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

图论问题

图的计数

子图相关问题

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

哈密顿回路问题可视为一个子图同构问题，即给定一个 n 个顶点的图，问是否存在一个子图与具有 n 个顶点的圈同构。

一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是完全的，如：

最大团问题：在给定图中寻找最大的团（完全）。

类似地，有些问题要求寻找符合某些条件的最大导出子图，如：

最大独立集问题：在给定图中寻找最大的无边的导出子图，亦即独立集（完全）。

平面图判定：判定给定的图是否是平面图（此问题与子图的关系，参见库拉托夫斯基定理）

一个尚未解决的与子图相关的猜想，重构猜想（ Reconstruction conjecture ）：一个 n 阶图是否能够由其所有 n-1 阶导出子图唯一确定？

染色

点色数（ Chromatic number ）

边色数（ Chromatic index ）

色多项式

许多问题与将图以特定方式染色有关，如：

四色问题

完美图问题（ strong perfect graph theorem ）

列表染色问题，列表边染色问题

曲面染色

路径问题

柯尼斯堡七桥问题

哈密顿回路问题

最小生成树问题

中国邮路问题

最短路问题

斯坦纳树

旅行商问题（困难）

网络流与匹配

最大流问题，最小割问题，最大流最小割定理

最小费用最大流问题

二分图及任意图上的最大匹配

带权二分图的最大权匹配

覆盖问题

最大团

最大独立集

最小覆盖集

最小支配集

重要的算法

戴克斯特拉算法(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, t 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 Applications2007 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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。