编辑“︁图论”︁（章节）

== 历史 ==
[[File:Konigsberg bridges.png|thumb|200px|柯尼斯堡七桥问题]]
一般认为，[[莱昂哈德·欧拉|欧拉]]于1736年出版的关于[[柯尼斯堡七桥问题]]的论文是图论领域的第一篇文章<ref name = "Biggs">{{citation|last1=Biggs|first1=N.|last2=Lloyd|first2=E.|last3=Wilson|first3=R.|title=Graph Theory, 1736–1936|publisher=Oxford University Press|year=1986}}</ref>。此问题被推广为著名的欧拉路问题，亦即[[一笔画问题]]。而此论文与[[亞歷山大‑泰奧菲爾·范德蒙|范德蒙]]的一篇关于[[骑士巡逻|骑士周游问题]]的文章，则是继承了[[戈特弗里德·莱布尼茨|莱布尼茨]]提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的[[欧拉示性数|欧拉公式]]与图论有密切联系，此后又被[[奥古斯丁·路易·柯西|柯西]]等人<ref name="Cauchy">{{Citation|author=Cauchy, A. L.|year=1813|title=Recherche sur les polyèdres - premier mémoire|journal=Journal de l'École polytechnique|volume= 9 (Cahier 16)|pages=66–86|postscript=.}}</ref><ref>{{Citation|author=L'Huillier, S.-A.-J.|title=Mémoire sur la polyèdrométrie|journal=Annales de Mathématiques|volume=3|year=1812–1813|pages=169–189|postscript=.}}</ref>进一步研究推广，成了[[拓扑学]]的起源。1857年，[[威廉·哈密顿|哈密顿]]发明了“{{link-en|環遊世界遊戲|icosian game|環遊世界遊戲}}”（icosian game），与此相关的则是另一个广为人知的图论问题“[[哈密顿路径问题]]”。

[[詹姆斯·约瑟夫·西尔维斯特|西尔维斯特]]于1878年发表在《[[自然 (期刊)|自然]]》上的一篇论文中首次提出“图”这一名词<ref name="Sylvester">{{cite journal | last1 = Sylvester | first1 = James Joseph | year = 1878 | title = Chemistry and Algebra | url = https://archive.org/stream/nature15unkngoog#page/n312/mode/1up | journal = Nature | volume = 17 | issue = | page = 284 | doi = 10.1038/017284a0 }}</ref>。

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

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

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

图论中概率方法的引入，尤其是[[保罗·埃尔德什|埃尔德什]]和{{link-en|Alfréd Rényi|Alfréd Rényi|Alfréd Rényi}}关于随机图连通的渐进概率的研究使得图论产生了新的分支[[随机图论]]。