图论 发表评论(0) 编辑词条

　图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
　　图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。
　　图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。
　　问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个「图」（如下图）。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对於一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。
　　1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由於运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。
　　在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。20世纪80-90年代曾邦哲的综合系统论（结构论）观将“四色猜想”命题转换等价为“互邻面最大的多面体是四面体”。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。
[编辑本段]图论中最著名的四色猜想解决办法
　　韩世君利用三角形性质和数学归纳法解决了四色猜想
　　摘要：将平面图的不相连点使其相连（这样增加着色难度），形成有许多三角形相连的平面图，根据三角形的稳定性，利用数学归纳法，平面图进行着色最多需４种颜色。
　　定理：在平面图中,对不同顶点进行着色,相邻顶点着不同颜色,不相邻顶点着相同颜色,则最多需4种颜色。
　　证明：在平面图中，不在同一直线上的三点决定一个平面，那么三点构成的三角形是平面图中最基本、最简单、最稳定、密闭的图形。
　　由于在对地图着色过程中不考虑图的具体形状只考虑点是否相邻，将平面图的不相连点使其相连（这样增加着色难度），形成有许多三角形相连的平面图（三点以下肯定成立）。如图1：添加辅助线（不相邻的点使其相邻，这样就增加了着色的色数，有利于证明），将图1分解为４个△ABC。
　　在平面图中的无数点中，任取相邻三点构成各点相邻的△ABC（见图2），则需3种颜色A B C,在平面图中再任取一点 D 与 A B C 三点相邻,同时D又与A B C三点相连后形成三角形。任取一点E与 A、B、C、D四色相连，E必与四色之一色相同即E点在△ABD中与C色相同、在△ACD中与B色相同、在△BCD中与A色相同、在△ABC外与D色相同，E与另外三色相连形成新的三角形。
　　在三角形的三点之外任取一点只有在三角形的内部和外部两种情况且这两种情况的点不会相邻，该点最多与三角形的三点相连且又形成新的三角形。
　　继续选取一点进行着色，该点同样最多与三角形的三点相连且又形成新的三角形，该点至少为四色中的一色。逐点（第n点）着色至将所有点（第n+1点）着色只须A、B、C、D四色其中一色。
　　图的着色方法：任意一张地图，将孤立的点用一种颜色着色（Ａ色），不能形成密闭图形的相连的点用两种颜色（Ａ、Ｂ色）。将剩余的点不相连的用虚线使其相连形成许多三角形，完全不相连的图不进行相连。任取相连三点着三种颜色（Ａ、Ｂ、Ｃ色），再取与其相连的点，如果与Ａ、Ｂ、Ｃ三色的点都相连着Ｄ色，否则着与其不相连的其中一色，用虚线相连的点可以用同一种颜色也可以用两种颜色，依次取与着色的点相连的点用以上方法进行着色。这样对所有的点进行着色最多用四色（Ａ、Ｂ、Ｃ、Ｄ色）。
　　图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论
　　、极图理论，以及代数图论、拓扑图论等都有很大的发展
　　拓扑学的由来
　　几何拓扑学是十九世纪形成的一门数学分支，它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现一些孤立的问题，后来在拓扑学的形成中占着重要的地位。
　　在数学上，关于哥尼斯堡七桥问题、多面体的欧拉定理、四色问题等都是拓扑学发展史的重要问题。
　　哥尼斯堡（今俄罗斯加里宁格勒）是东普鲁士的首都，普莱格尔河横贯其中。十八世纪在这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，一天有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个问题看起来很简单有很有趣的问题吸引了大家，很多人在尝试各种各样的走法，但谁也没有做到。看来要得到一个明确、理想的答案还不那么容易。
　　1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。欧拉把这个问题首先简化，他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线。那么这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论——不可能每座桥都走一遍，最后回到原来的位置。并且给出了所有能够一笔画出来的图形所应具有的条件。这是拓扑学的“先声”。
　　在拓扑学的发展历史中，还有一个著名而且重要的关于多面体的定理也和欧拉有关。这个定理内容是：如果一个凸多面体的顶点数是v、棱数是e、面数是f，那么它们总有这样的关系：f+v-e=2。
　　根据多面体的欧拉定理，可以得出这样一个有趣的事实：只存在五种正多面体。它们是正四面体、正六面体、正八面体、正十二面体、正二十面体。
　　著名的“四色问题”也是与拓扑学发展有关的问题。四色问题又称四色猜想，是世界近代三大数学难题之一。
　　四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”
　　1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。
　　进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。
　　上面的几个例子所讲的都是一些和几何图形有关的问题，但这些问题又与传统的几何学不同，而是一些新的几何概念。这些就是“拓扑学”的先声。
　　什么是拓扑学？
　　拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。我国早期曾经翻译成“形势几何学”、“连续几何学”、“一对一的连续变换群下的几何学”，但是，这几种译名都不大好理解，1956年统一的《数学名词》把它确定为拓扑学，这是按音译过来的。
　　拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。
　　举例来说，在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，前面讲的欧拉在解决哥尼斯堡七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数。这些就是拓扑学思考问题的出发点。
　　拓扑性质有那些呢？首先我们介绍拓扑等价，这是比较容易理解的一个拓扑性质。
　　在拓扑学里不讨论两个图形全等的概念，但是讨论拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。左图的三样东西就是拓扑等价的，换句话讲，就是从拓扑学的角度看，它们是完全一样的。
　　在一个球面上任选一些点用不相交的线把它们连接起来，这样球面就被这些线分成许多块。在拓扑变换下，点、线、块的数目仍和原来的数目一样，这就是拓扑等价。一般地说，对于任意形状的闭曲面，只要不把曲面撕裂或割破，他的变换就是拓扑变幻，就存在拓扑等价。
　　应该指出，环面不具有这个性质。比如像左图那样，把环面切开，它不至于分成许多块，只是变成一个弯曲的圆桶形，对于这种情况，我们就说球面不能拓扑的变成环面。所以球面和环面在拓扑学中是不同的曲面。
　　直线上的点和线的结合关系、顺序关系，在拓扑变换下不变，这是拓扑性质。在拓扑学中曲线和曲面的闭合性质也是拓扑性质。
　　我们通常讲的平面、曲面通常有两个面，就像一张纸有两个面一样。但德国数学家莫比乌斯(1790～1868)在1858年发现了莫比乌斯曲面。这种曲面就不能用不同的颜色来涂满两个侧面。
　　拓扑变换的不变性、不变量还有很多，这里不在介绍。
　　拓扑学建立后，由于其它数学学科的发展需要，它也得到了迅速的发展。特别是黎曼创立黎曼几何以后，他把拓扑学概念作为分析函数论的基础，更加促进了拓扑学的进展。
　　二十世纪以来，集合论被引进了拓扑学，为拓扑学开拓了新的面貌。拓扑学的研究就变成了关于任意点集的对应的概念。拓扑学中一些需要精确化描述的问题都可以应用集合来论述。
　　因为大量自然现象具有连续性，所以拓扑学具有广泛联系各种实际事物的可能性。通过拓扑学的研究，可以阐明空间的集合结构，从而掌握空间之间的函数关系。本世纪三十年代以后，数学家对拓扑学的研究更加深入，提出了许多全新的概念。比如，一致性结构概念、抽象距概念和近似空间概念等等。有一门数学分支叫做微分几何，是用微分工具来研究取线、曲面等在一点附近的弯曲情况，而拓扑学是研究曲面的全局联系的情况，因此，这两门学科应该存在某种本质的联系。1945年，美籍中国数学家陈省身建立了代数拓扑和微分几何的联系，并推进了整体几何学的发展。
　　拓扑学发展到今天，在理论上已经十分明显分成了两个分支。一个分支是偏重于用分析的方法来研究的，叫做点集拓扑学，或者叫做分析拓扑学。另一个分支是偏重于用代数方法来研究的，叫做代数拓扑。现在，这两个分支又有统一的趋势。
　　拓扑学在泛函分析、李群论、微分几何、微分方程额其他许多数学分支中都有广泛的应用。