更改

[[File:Konigsberg bridges.png|缩略图|柯尼斯堡七桥问题]]

[[File:Konigsberg bridges.png|缩略图|柯尼斯堡七桥问题]]

一般认为，'''欧拉 Leonhard Euler'''于1736年出版的关于'''柯尼斯堡七桥问题  Seven Bridges of Königsberg'''的论文是图论领域的第一篇文章。<ref name="Biggs">{{Citation|author1=Biggs, N. |author2=Lloyd, E. |author3=Wilson, R. |title=Graph Theory, 1736-1936|publisher=Oxford University Press|year=1986}}</ref> 此问题被推广为著名的欧拉路问题，亦即一笔画问题。而该论文与'''范德蒙德 Vandermonde'''的一篇关于骑士周游问题的文章，则是继承了'''莱布尼茨 Leibniz'''提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被'''柯西 Cauchy'''<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>等人进一步研究推广，成了'''拓扑学 topology'''的起源。1857年，'''哈密顿  Hamilton'''发明了“环游世界游戏” icosian game，与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

一般认为，'''欧拉 Leonhard Euler'''于1736年出版的关于'''柯尼斯堡七桥问题  Seven Bridges of Königsberg'''的论文是图论领域的第一篇文章。<ref name="Biggs">{{Citation|author1=Biggs, N. |author2=Lloyd, E. |author3=Wilson, R. |title=Graph Theory, 1736-1936|publisher=Oxford University Press|year=1986}}</ref> 此问题被推广为著名的欧拉路问题，亦即一笔画问题。而该论文与'''范德蒙德 Vandermonde'''的一篇关于骑士周游问题的文章，则是继承了'''莱布尼茨 Leibniz'''提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被'''柯西 Cauchy'''<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>等人进一步研究推广，成了'''拓扑学 topology'''的起源。1857年，'''哈密顿  Hamilton'''发明了“环游世界游戏” icosian game，与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

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

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

欧拉的论文发表后一个多世纪，'''凯莱 Cayley'''研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。<ref>{{citation|first=A.|last=Cayley|authorlink=Arthur Cayley|year=1857|title=On the theory of the analytical forms called trees|journal=[[Philosophical Magazine]]|series=Series IV|volume=13|issue=85|pages=172–176|doi=10.1017/CBO9780511703690.046|isbn=9780511703690}}</ref> 由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，'''波利亚 Pólya'''也于1935至1937年发表了一些成果，1959年，'''De Bruijn'''做了一些推广。<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

欧拉的论文发表后一个多世纪，'''凯莱 Cayley'''研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。<ref>{{citation|first=A.|last=Cayley|authorlink=Arthur Cayley|year=1857|title=On the theory of the analytical forms called trees|journal=[[Philosophical Magazine]]|series=Series IV|volume=13|issue=85|pages=172–176|doi=10.1017/CBO9780511703690.046|isbn=9780511703690}}</ref> 由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，'''波利亚 Pólya'''也于1935至1937年发表了一些成果，1959年，'''De Bruijn'''做了一些推广。<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

'''四色问题 four color problem'''可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由'''Francis Guthrie'''于1852年提出，而最早的文字记载则出现在'''德摩根 De Morgan'''于1852年写给哈密顿的一封信上。包括凯莱、'''肯普 Kempe'''等在内的许多人都曾给出过错误的证明。'''泰特Peter Guthrie Tait'''、'''希伍德 Percy John Heawood'''、'''拉姆齐 Ramsey'''和'''Hugo Hadwiger'''对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，'''Heinrich Heesch'''发表了一个用计算机解决此问题的方法。<ref>Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.</ref>1976年，'''阿佩尔 Kenneth Appel'''和'''沃夫冈·哈肯 Wolfgang Haken'''借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。<ref name="AA1">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part I. Discharging|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=429–490|postscript=.|doi=10.1215/ijm/1256049011|doi-access=free}}</ref><ref name="AA2">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part II. Reducibility|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=491–567|postscript=.|doi=10.1215/ijm/1256049012|doi-access=free}}</ref>  

'''四色问题 four color problem'''可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由'''Francis Guthrie'''于1852年提出，而最早的文字记载则出现在'''德摩根 De Morgan'''于1852年写给哈密顿的一封信上。包括凯莱、'''肯普 Kempe'''等在内的许多人都曾给出过错误的证明。'''泰特Peter Guthrie Tait'''、'''希伍德 Percy John Heawood'''、'''拉姆齐 Ramsey'''和'''Hugo Hadwiger'''对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，'''Heinrich Heesch'''发表了一个用计算机解决此问题的方法。<ref>Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.</ref>1976年，'''阿佩尔 Kenneth Appel'''和'''沃夫冈·哈肯 Wolfgang Haken'''借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。<ref name="AA1">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part I. Discharging|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=429–490|postscript=.|doi=10.1215/ijm/1256049011|doi-access=free}}</ref><ref name="AA2">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part II. Reducibility|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=491–567|postscript=.|doi=10.1215/ijm/1256049012|doi-access=free}}</ref>  

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

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

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

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