图论起源

文章来源http://xuexi88.blogspot.com/

图论起源0
历史上，图论曾经被好多位数学家各自独立的建立过，因为图论本身是应用数学的一部分（Sylvester 较早的指出了图论的基本的组合属性和它具有广泛应用的一些理由），所以这种情况并不是偶然的巧合。事实上，提到这个主题的文字记载最早是出现在 Euler 的著作中，虽然他所考虑的原始问题似乎是一个颇为无聊的难题，然而这个问题确实有其实际的背景。后来 Kirohhoff 和 Cayley 在图论上的新发现也各有其实际的根源。 Kirohhoff 对于电网络的研究导致他发展了图论的基本概念和关于图中的树的定理；而 Cayley 则是为了计数有机化学中的同分异构物而考虑树。另外一个与图有关的难题是 Hamilton 提出来的，它同样是促进了图论的发展。后来，著名的四色猜想出现了，并且至今一直作为一个解决不了的难题闻名于世。

1. 哥尼斯堡七桥问题

Euler （1707--1782）在 1736 年解决了一个当时没有解决的著名问题，称为哥尼斯堡（Konigberg）七桥问题，从而使他成了图论和拓扑学的创始人。有七条桥将普莱格尔 Pregel 河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始，通过每一条桥正好一次，再回到起点。很容易通过试验摸索去尝试解决这个问题，然而，任何尝试都决不可能成功，因为 Euler 得到的重要结果指出：在这种情形下是不可能有解的。

Euler 并不限于处理这种特殊情形，他推广了这个问题，并且对于一个给定的图是否可以走遍给出了一个判定法则；就是说这个图必须是连通的，并且每个点都与偶数条线相关联。

2. 电网络

Kirohhoff 在1847 年为了求解一类线性方程组而发展了树的理论。这个线性方程组是描述一个电网络的每一条支路中和环绕每一个回路的电流的。他虽然是一个物理学家，但他像数学家那样思考问题。他把一个电网络和其中的电阻、电容、电感等等抽象化了。他用一个只有点和线组成的相应的组合结构来代替原来的电网络而并不指明每条线所代表的电气元件的种类。这样一来，Kirohhoff 实际上是把每个电网络用它的基本图来替代。他还证明，为了求解这个方程组，并不需要分别考虑一个电网络的图中的每个圈。与此相反，他用一个简单而有力的构造法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法已经现在已经成为一个标准的方法。

3. 化学同分异构物

1857 年， Cayley 非常自然的在有机化学的领域里发现了一族重要的图，称为树。他从事于计数有给定的碳原子数 n 的饱和碳氢化合物 CnH2n+2 的同分异构物。当然，Cayley 抽象的重新叙述了这个问题： 求 p 个点的树的数目，其中每个点的度等于1或者4。他没有能够立即成功的解决这个问题，所以他改变了这个问题，逐步计数了：有根树（其中有一个点与其余各点有区别的树）、树、每个点的度至多等于4的树。最后，他还是数出了每个点的度等于1或4的树，从而解决了那个化学问题。后老，Jordan 作为一个纯数学的对象独立的发现了树（1869）。西勒维斯脱写道（1882）：Jordan 这样做一点也没有察觉到它与现代化学学说有关。

4. 绕行世界

威廉 哈密顿爵士在1859年发明了一种游戏。这种游戏用一个规则的实心十二面体，它的二十个顶点标以有名的城市的名字，要求游戏者找一条沿着各边通过每个顶点正好一次的闭回路，即“绕行世界”。他以25个金币的代价把他的设计卖给了一个玩具商。然而，这是一笔滑头生意，因为这个游戏经济上并不成功。 用图的语言来说，游戏的目的是在十二面体的图中找到一个生成圈。

5. 四色猜想

四色问题又称四色猜想，是世界近代三大数学难题之一。
四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”
这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。
四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。
1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家汉密尔顿爵士请教。汉密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年汉密尔顿逝世为止，问题也没有能够解决。
1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。
肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”。如为正规地图，否则为非正规地图。一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。
肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。
不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形中的一个。
肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。
11年后，即1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。不久，泰勒的证明也被人们否定了。人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对地图着色，用五种颜色就够了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。
进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年，美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法，结合自己新的设想；证明了某些大的构形可约。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。看来这种推进仍然十分缓慢。
高速数字计算机的发明，促使更多数学家对“四色问题”的研究。从1936年就开始研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。他的学生丢雷写了一个计算程序，海克不仅能用这程序产生的数据来证明构形可约，而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”形着手。
他把每个国家的首都标出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都(称为顶点)及铁路(称为弧或边)外，擦掉其他所有的线，剩下的称为原图的对偶图。到了六十年代后期，海克引进一个类似于在电网络中移动电荷的方法来求构形的不可避免组。在海克的研究中第一次以颇不成熟的形式出现的“放电法”，这对以后关于不可避免组的研究是个关键，也是证明四色定理的中心要素。
电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。
这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。
“四色问题”的被证明仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。
不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍由不少数学家和数学爱好者在寻找更简洁的证明方法。
本文转自诺贝尔学术资源网 http://bbs.ok6ok.com,☆文献互助、学术交流和学术资源

文章来源http://xuexi88.blogspot.com/