图论

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

图论Graph theory)是 数学的一个分支,它以 为研究对象,研究 顶点组成的图形的数学理论和方法。图是区域在头脑和纸面上的反映,图论就是研究区域关系的学科。区域是一个平面,平面当然是二维的,但是,图在特殊的构造中,可以形成多维(例如大于3维空间)空间,这样的图已经超越了一般意义上的区域(例如一个有许多洞的曲面,它是多维的, 曲面染色已经超出了平面概念)。

图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用顶点代表事物,用连接两顶点的边表示相应两个事物间具有这种关系。

图论起源于著名的 柯尼斯堡七桥问题

图论的研究对象相当于一维的 拓扑学 [來源請求]

历史

柯尼斯堡七桥问题

一般认为,于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)和 哈肯(Wolfgang Haken)借助计算机给出了一个证明,此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂,在当时未被广泛接受。

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

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

其他语言
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
粵語: 圖論