离散数学 郝晓燕 第8章图论

《离散数学 郝晓燕 第8章图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章图论及其应用图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。哥尼斯堡七桥哥尼斯堡（今俄罗斯加里宁格勒）是东普鲁士的首都，普莱格尔河横贯其中。十八世纪在这条河上建有七座桥，将河中间的

2、两个岛和河岸联结起来。有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个问题看起来很简单有很有趣的问题吸引了大家，很多人在尝试各种各样的走法，但谁也没有做到。1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。欧拉把这个问题首先简化，他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线。那么这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论——不可能每座桥都走一遍，最后回到原来的位置。并且给出了所有能够一笔画出来的图形所

3、应具有的条件。这是拓扑学的“先声”。四色问题著名的“四色问题”也是与拓扑学发展有关的问题。四色问题又称四色猜想，是世界近代三大数学难题之一。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著

4、名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题（当n>2时，xn+yn=zn，n为奇素数，X，Y，Z没有正整数解。）进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两

5、台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。哈密顿问题1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由於运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意

6、和研究。§8-1-1图定义8-1.1一个图G定义为一个三元组，记作G=。其中：V是一个非空有限集合，其中元素v称为图G的顶点或结点；E是和V没有公共元素的有限集合，E可以是空集，其元素e称为图G的边；φ称为关联函数，是从E到V中的有序对或无序对的映射。由定义可知，图G中的每条边都与图中的无序或有序结点对相联系的。若边e∈E与无序结点对(vi，vj)相联系，则φ(e)=(vi，vj)，这时边e称为无向边，有时简称为边；若边e∈E与有序结点对相联系，则φ(e)=，此时边e称为有向

7、边或弧，vi称为弧e的始结点，vj称为弧e的终结点。若结点vi与vj由一条边(或弧)e所联结，则称结点vi和vj是边(或弧)e的端结点；同时也称结点vi与vj是邻接结点，记作viadjvj关联同一个结点的两条边或弧称为邻接边或邻接弧。而联结一结点与它自身的一条边，称为环。环的方向是无意义的。如果把图G中的弧或边总看作联结两个结点，则图G可简记为G=，其中V是非空结点集，E是联结结点的边集或弧集。在图G=中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图G称为无向图；如果有些边是有向边，另一些边是无向

8、边，图G称为混合图。图8-1（a）表示无向图G=，其中：V={v1，v2，v3，v4}E={e1，e2，e3，e4}图8-1（b）表示有向图G=，其中：V={v1，v2，v3，v4}E={e1，e2，e3，e4}在图G=