图论

图论（英语：Graph theory），是组合数学的一个分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。图论的研究对象相当于一维的单纯复形。一般认为，欧拉于1736年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章。此问题被推广为著名的欧拉路问题，亦即一笔画问题。而此论文与范德蒙德（英语：Alexandre-Théophile Vandermonde）的一篇关于骑士周游问题的文章，则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西等人进一步研究推广，成了拓扑学的起源。1857年，哈密顿发明了“环游世界游戏（英语：icosian game）”（icosian game），与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。西尔维斯特于1878年发表在《自然》上的一篇论文中首次提出“图”这一名词。欧拉的论文发表后一个多世纪，凯莱研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚也于1935至1937年发表了一些成果，1959年，De Bruijn（英语：Nicolaas Govert de Bruijn）做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。四色问题可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由Francis Guthrie（英语：Francis Guthrie）于1852年提出，而最早的文字记载则出现在德摩根于1852年写给哈密顿的一封信上。包括凯莱、肯普（英语：Alfred Kempe）等在内的许多人都曾给出过错误的证明。泰特（英语：Peter Guthrie Tait）（Peter Guthrie Tait）、希伍德（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）关于随机图连通的渐进概率的研究使得图论产生了新的分支随机图论。图论中有许多定义，以下是一些与之相关最基本的定义。图论中，图是有序对 G = ( V , E ) {displaystyle G=(V,E)} ，其中 V {displaystyle V} 是点集； E ⊆ { { x , y } : ( x , y ) ∈ V 2 , x ≠ y } {displaystyle Esubseteq left{left{x,yright}:(x,y)in V^{2},xneq yright}} 是边集，由所有无序顶点对构成（换句话说，边连接了顶点对）。对于一个边 { x , y } {displaystyle left{x,yright}} ，顶点 x , y {displaystyle x,y} 被称作是边的端点，边则被称为连接了此两个点。为了避免歧异，上述的定义被更精准地称作无向简单图。事实上可以推广为更一般的定义：图是有序三元组 G = ( V , E , ϕ ) {displaystyle G=(V,E,phi )} ，其中 V {displaystyle V} 是点集； E {displaystyle E} 是边集（此时 E {displaystyle E} 不再如前面限定是该集合的子集）；而 ϕ : E → { { x , y } : ( x , y ) ∈ V 2 } {displaystyle phi :Eto left{left{x,yright}:(x,y)in V^{2}right}} 将每个边映射到一个无序顶点对（于是边连接了顶点对）。此时的定义就允许自环、重边的出现，其中自环是两端点相同的边，重边是两个或多个连接相同端点的边。为了避免歧异，上述的定义被更精准地称作无向图。V , E {displaystyle V,E} 的元素个数通常都是有限的；并且如果个数是无限的，有许多著名的性质都会改变、甚至错误他们是无限的。此外， V {displaystyle V} 通常不被接受是空集合，而 E {displaystyle E} 则被接受为空集合。以下再给出一些图论中的定义：图的阶是其顶点个数 | V | {displaystyle |V|} ，图的边数是 | E | {displaystyle |E|} ，顶点的度所有边的端点中此顶点出现的次数（自环会被算两次）。子图同构问题：给定两个图 G {displaystyle G} 和 H {displaystyle H} ，问 G {displaystyle G} 中是否存在一个子图与 H {displaystyle H} 同构。这是一个NP完全问题。一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：类似地，有些问题要求寻找符合某些条件的最大导出子图，如：平面图判定：判定给定的图是否是平面图（此问题与子图的关系，参见库拉托夫斯基定理）一个尚未解决的与子图相关的猜想，重构猜想（Reconstruction conjecture）：一个n阶图是否能够由其所有n-1阶导出子图唯一确定？许多问题与将图以特定方式染色有关，如：