|
图论最早起源于瑞士数学家L.欧拉1736年的论著中的柯尼斯堡七桥问题（Königsberg bridge problem）。在柯尼斯堡的公园里，普莱格尔河上有七座桥把岛与岛、岛与河岸连接起来。有人提出一个问题，如何从陆地的某一块出发，经过每一座桥恰好一次，最后回到出发点。许多人尝试很多次之后都失败了。最后欧拉用抽象的方法把这个问题转化成了一个图论问题。他将每一块陆地用点表示，将每一座桥用一条线表示，从而得到一个图。称连有偶数条线的顶点为偶顶点，对应地，称连有奇数条线的顶点为奇顶点。欧拉论述了由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。柯尼斯堡七桥问题本质上等价于图论中广为人知的一笔画问题，即寻找从图中某一点出发，经过每条边恰好一次，最后回到出发点的路径。人们称这样的路径为欧拉回路。欧拉不仅证明了柯尼斯堡七桥问题没有解，并且给出了一笔画问题的充要条件。从此欧拉成为图论的创始人。在图论的发展历史中，还有一个重要的定理与欧拉有关，即欧拉定理。欧拉定理的内容是：对任一顶点数为V、棱数为E、面数为F的凸多面体，总有关系V+F-E=2成立。式中V+F-E即欧拉示性数，已成为拓扑学中的基本概念。根据多面体的欧拉定理还可以得出一个有趣的事实：只存在5种正多面体。它们分别是正四面体、正六面体、正八面体、正十二面体、正二十面体。 1857年，W.R.哈密顿（W.R.Hamilton）发明了世界环游游戏（Icosian game）。哈密顿的游戏是用一个正十二面体的20个顶点代表20个城市，如何从一个城市出发，经过每个城市恰好一次，最后回到出发点。世界环游游戏等价于图论中另一个广为人知的哈密顿圈问题，即寻找从图中某一点出发，经过每个点恰好一次，最后回到出发点的路径。人们称这样的路径为哈密顿圈。欧拉回路和哈密顿圈都是寻找一条起点和终点相同的路径，两者的区别在于前者要求恰好经过每条边一次，而后者要求恰好经过每个点一次。由于运筹学、计算机科学和编码理论中的很多问题都可以转化为哈密顿圈问题，从而引起学者们的广泛关注和研究。图论中还有一个最著名的问题——四色问题。四色问题又称为四色定理、四色猜想，是世界三大数学猜想之一。通俗地说，四色问题指每个地图都可以用不多于四种颜色来染色，而且任何两块邻接的区域不会染相同的颜色，其中邻接的两块区域是指它们有一段公共的边界，而不仅仅只是一个公共的顶点。1852年，一位英国制图员法兰西斯·古德里最早提出了四色问题。他将这个问题告诉了他的弟弟弗雷德里克·古德里。弗雷德里克这时正在伦敦大学读数学，师从法兰西斯上学时的老师奥古斯塔斯·德摩根。10月23日，弗雷德里克将他哥哥的发现告诉了老师德摩根。德摩根并没有找到有效地解决途径，于是同一天德摩根就在通信中向爱尔兰数学家威廉·哈密顿提出了这个问题。哈密顿接信后开始研究，但是直到1865年去世也没有解决。德摩根的信是关于四色问题的最早的记载，如今依然保存在都柏林三一学院中。1872年，英国当时最著名的数学家阿瑟·凯莱正式向伦敦数学学会提出了这个问题，于是四色问题成了世界数学界关注的问题，世界上许多一流的数学家都纷纷参加了四色问题的大会战。从此四色问题的证明经历了一段漫长的历程。1879年，伦敦律师兼数学家阿尔弗雷德·布雷·肯普发表了一篇关于四色问题的证明。11年后，也就是1890年，珀西·约翰·希伍德以精确地计算指出肯普的证明中包含一个错误。尽管无法得到四色定理，希伍德仍然没有彻底否定肯普论文的价值。希伍德运用肯普的方法得到一个较弱的定理：五色定理。1880年，物理学家彼得·古德里·泰特也发表了一个四色猜想的新证明，后来被证明也是错误的。后来越来越多的证明被给出，但是后来都被证明是错误的。于是人们慢慢意识到四色问题是一个可以媲美费马猜想的问题。二十世纪后，欧洲数学界对四色定理的研究出现停滞。相反地，这个问题在美国得到更多的关注。大家的证明基本上是按照肯普的想法在进行。许多数学家为此做出了很多优秀的工作。直到1976年，数学家凯尼斯·阿佩尔和沃夫冈·哈肯利用伊利诺伊大学的电子计算机运行了1200小时得到了该问题第一个完整的证明，从此四色问题也成为了四色定理，这也是第一个借助计算机证明的定理。不久，伊利诺伊大学数学系的邮戳上加上了“Four Colors Suffice”（四种颜色就够了），以庆祝四色猜想得到解决。四色定理的计算机证明轰动了世界，这不仅是一个百年难题的解决，同时这也是一系列新思维的起点。这个证明一开始不为许多数学家接受，因为他们认为这个证明无法直接验证。后来有人将阿佩尔和哈肯的证明经过了一系列的改进，但是仍然需要计算机进行验证。直到现在，仍有数学家希望能够找到更简洁的证明。 20世纪中叶以前，图论主要研究一些游戏问题，诸如博弈问题、迷宫问题等。众多古老问题吸引了许多学者从事图论研究，其中有著名的四色问题、哈密顿圈问题、图的重构问题、拉姆齐问题等。 20世纪中叶以后，由于生产管理、军事、交通运输、计算机网络等领域的需要，出现了很多的离散问题，而图论可为离散问题的研究提供数学模型。近代电子计算机的出现和发展，促使图论及其应用迅猛发展。图论与线性规划、动态规划等优化理论的内容和方法的相互渗透，促使了组合优化理论和算法的研究。图论的引进改变了计算机科学、网络科学等领域的面貌。当前应用图论来解决化学、物理学、生物学、运筹学、网络理论、信息论、控制论、经济学、社会科学等学科的问题，已显示出极大的优越性。图论可以刻画很多诸如化学、物理、生物、社会和信息系统中的关系和过程。很多现实的问题都可以用图表示。同时，对图论中古老问题以及趣味问题（如最短路问题、旅行售货商问题、中国邮递员问题等）的研究，促进了图论自身的发展。例如，四色问题的研究对图的染色理论、平面图理论、拓扑图论等分支的发展起了极大的推动作用。近30年来，由N.罗伯逊（N.Robertson）和P.D.西摩（P.D.Seymour）提出的图子式理论得到了极大的发展，借助图子式理论可对图的结构进行很好的刻画。 自20世纪40年代爱尔特希首次引入概率方法以来，概率方法在图论中得到了深入的发展，并且日渐成为研究中的一个有力工具。由于研究方法和内容的不同，图论已经产生了若干不同的理论和分支，如拟阵理论、超图理论、极图理论，以及代数图论、极值图论、随机图论、拓扑图论、应用图论等。 |
|
|
