第七章 图论.ppt

《第七章 图论.ppt》由会员分享，可在线阅读，更多相关《第七章 图论.ppt（227页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 图图 论论1引言考虑你最喜欢的城镇街道图，在所有两考虑你最喜欢的城镇街道图，在所有两条或者多条街道的汇合处或者一条街道条或者多条街道的汇合处或者一条街道的尽头划上一个粗点就得到一个的尽头划上一个粗点就得到一个图图。考虑可能性：考虑可能性：某些街道是单行道，只允某些街道是单行道，只允许单向行驶，再所有单行道上划一个单许单向行驶，再所有单行道上划一个单向的箭头。在所有的双行道上划一个双向的箭头。在所有的双行道上划一个双向的箭头，这样就得到一个所谓的向的箭头，这样就得到一个所谓的有向有向图图。2引言考虑这个城市的居民，在一对相爱的人考虑这个城市的居民，在一对相爱的人中间划一条线，也得到

2、一个中间划一条线，也得到一个图图。但是你要承认：有时一个人对另一个人但是你要承认：有时一个人对另一个人的爱不一定能够得到回报，可能还得在的爱不一定能够得到回报，可能还得在这些线上划上箭头，这样就得到了一个这些线上划上箭头，这样就得到了一个有向图有向图。3引言考虑你所喜爱的这个城镇的所有不同种考虑你所喜爱的这个城镇的所有不同种类的动物和植物，如果一个物种捕食另类的动物和植物，如果一个物种捕食另一个物种就在它们之间划一个箭头，这一个物种就在它们之间划一个箭头，这样就得到另外一个样就得到另外一个有向图有向图。我们还可以得到表示物种之间竞争的我们还可以得到表示物种之间竞争的有有向图向图。4因此：因此：

3、图和有向图为相关实体或以某种图和有向图为相关实体或以某种方式相互约束的实体构成的集合提供了方式相互约束的实体构成的集合提供了一种数学模型一种数学模型。图论在智力难题和游戏方面有着历史根图论在智力难题和游戏方面有着历史根据，但今天它为许多学科的研究，如：据，但今天它为许多学科的研究，如：网络学，化学、心理学、社会科学、生网络学，化学、心理学、社会科学、生态学和遗传学等，都提供了一种自然的态学和遗传学等，都提供了一种自然的同时又是很重要的语言和构架。同时又是很重要的语言和构架。5第第7 7章章 图论图论1 1 图的基本概念图的基本概念2 2 路与回路路与回路 3 3 图的矩阵表示图的矩阵表示 4

4、4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图5 5 平面图平面图6 6 对偶图与着色对偶图与着色 7 7 树与生成树树与生成树 8 8 根树及其应用根树及其应用67-1图的基本类型定义7-1.1所谓图G是一个三元组：G=其中：V(G)是一个非空的结点集合；E(G)是边的集合；G是从边集合E到结点无序偶（或有序偶）集合上的函数。1 图 7例1G其中：V(G)a，b，c，d；E(G)e1，e2，e3，e4，e5，e6；G(e1)(a，b)，G(e2)(a，c)，G(e3)(b，d)，G(e4)(b，c)，G(e5)(d，c)，G(e6)(a，d)。一个图可用一一个图可用一个图形表示；个图形表示；例例1

5、可表示为可表示为：8说明：若把图中的边ei看作总是与两个结点关联，则一个图G由两种实体组成，它有一个叫做顶点（有时也叫做节点）的元素的有限集合V=a,b,c和一个叫做边的不同顶点对的有限集合E，一个图可简记为图可简记为G=。集合V中顶点的个数n叫做图的阶。92 一些概念v若边ei与结点无序偶(vj，vk)相关联，则称该边为无向边。v若边ei与结点有序偶相关联，则称该边为有向边。其中vj称为ei的起始结点；vk称为ei的终止结点。10Gv每一条边都是无向边的图称无向图。v每一条边都是有向边的图称有向图。Gv1，v2，v3，v4，v5，11v如果在图中一些边是有向边，另一些边是无向边，则称这个图是

6、混合图。Gv1，v2，v3，v4，(v1，v4)，(v2，v4)，12v在一个图中，若两个节点由一条有向边或一条无向边相关联，则这两个节点称为邻接点。v在一个图中不与任何节点相邻接的节点，称为孤立节点。仅由孤立节点组成的图称为零图，仅由一个孤立节点组成的图称为平凡图。13v关联于同一结点的两条边称为邻接边。关联于同一结点的一条边称为自回路或环。如图7-1.3中(c，c)是环。环的方向是没有意义的，它既可作为有向边，也可作无向边。143 度数 定义7-1.2设图G=是无向图，v是图G中的结点，所有与v关联的边数，称为结点v的度数，记作deg(v)。例：例：在图7-1.4中，结点A的度数为2，结点

7、B的度数为3。约定：约定：每个环在其对应结点上度数增加2。故图7-1.4中结点E的度数为5。15记：记：(G)maxdegv|vV(G)，(G)mindegv|vV(G)，分别称为G=的最大度和最小度。如图7-1.4中(G)5，(G)2。16定理7-1.1设图G是具有n个点，m条边的无向图，其中结点集合为V=v1，v2，vn，则：证明 因为每条边必关联两个结点，而一条边给于关联的每个结点的度数为 1。因此在一个图中，结点度数的总和等于边数的两倍。17定义7-1.3设图G是有向图，v是图G中的结点；以v为始点的有向边的条数称为v的出度，记作deg+(v)；以v为终点的有向边的条数称为v的入度，记

8、作deg(v)；结点的出度与入度之和就是该结点的度数。4 入度和出度 18证明 因为每一条有向边必对应一个入度和一个出度，若一个结点具有一个入度或出度，则必关联一条有向边；所以，有向图中各结点入度之和等于边数，各结点出度之和也等于边数；因此，任何有向图中，入度之和等于出度之和。定理7-1.3设有向图G具有n个结点，m条边，其中结点构成的集合V=v1，v2，vn，则有：195 多重图定义7-1.4如果两个结点之间有多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两个结点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图。20例：图7-1.5

9、所示的均为多重图。图(a)中结点a和b之间有两条平行边，结点b和c之间有三条平行边，在结点b有两个平行的环。结点a的度数为3，结点c的度数为4，结点b的度数为9。图(b)中，只有结点v1和v2之间有两条平行边。这是因为该有向图中，与认为是不同的结点对。216 完全图 定义7-1.5在n阶简单无向图中，如果任意两个不同的结点之间都有一条边关联，则称此无向图为无向完全图，记作Kn。定理7-1.4n个结点的无向完全图Kn的边数是n(n-1)/2。证明在Kn中，任意两点间都有边相连，n个结点中任取两点的组合数为：故Kn的边数为|E|n(n-1)/2。22注意：如果在Kn中，对每条边任意确定一个方向，就

10、称该图为n个结点的有向完全图。显然，它的边数也为n(n-1)/2。给定任意一个含有n个结点的图G，总可以把它补成一个具有同样结点的完全图，方法是把那些没有连上的边添加上去。237 补图例：如图7-1.6中(a)和(b)互为补图。248 子图例：如图7-1.7中(b)和(c)都是(a)的子图。25如果G的子图包含G的所有结点，则称该子图为G的生成子图。如图7-1.8中(b)和(c)都是(a)的生成子图。2627例：如图7-1.7中图(c)是图(b)相对于图(a)的补图。而图(b)不是图(c)相对于图(a)的补图，因为图(b)中有结点c。在上面一些图的基本概念中，一个图由一个图在上面一些图的基本概

11、念中，一个图由一个图形表示，由于图形的结点位置和连线长度都可任意形表示，由于图形的结点位置和连线长度都可任意选择，故一个图的图形表示并不是唯一的。选择，故一个图的图形表示并不是唯一的。289 同构 29说明：v若G与G同构，它的充要条件是：两个图的结点和边分别存在着一一对应，且保持关联关系，例如图7-1.9中，(a)与(b)是同构的，(c)与(d)也是同构的。30从图7-1.9的(c)与(d)中可以看到此两图在结点间存在着一一对应映射g：g(a)u3，g(b)u1，g(c)u4，g(d)u2，且有：，分别与，一一对应。31v分析本例还可以知道，此两图的结点度数也分别对应相等，如表7-1.1所示

12、。32两图同构的一些必要条件：1结点数目相同；2边数相等；3度数相同的结点数目相等。这几个条件不是两个图同构的充分条件这几个条件不是两个图同构的充分条件 图中图中(a)和和(b)满足上满足上述三个条件，述三个条件，但此两个图并但此两个图并不同构。不同构。33作业：P279(2)(3)347-2 路与回路1 路 定义定义7-2.1给定图G，设v0，v1，vnV，e1，e2，enE，其中ei是关联于结点vi-1，vi 的边，交替序列v0e1v1e2envn称为联结v0到vn的路。35特别：v0和vn分别称作路的起点和终点，边的数目n称作路的长度。当v0vn时，这条路称作回路。若一条路中所有的边e1

13、，e2，en均不相同，称作迹。若一条路中所有的结点v0，v1，vn均不相同，则称作通路。闭的通路，即除v0vn外，其余的结点均不相同的路，就称作圈。36例 在图7-2.1中有：路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v237注明：在简单图中一条路v0e1v1e2envn，由它的结点序列v0v1vn确定，所以简单图的路，可由其结点序列表示。此外，在有向图中，结点数大于一的一条路可也由边序列e1e2en表示。38定理7-2.1在一个具有n个结点的图中，如果从

14、结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。证明 如果从结点vj到结点vk存在一条路，该路上的结点序列是vjvivk；如果在这条路中有l条边，则序列中必有l+1个结点；39若ln-1，则必有结点vs，它在序列中不止一次出现，即必有结点序列vjvsvsvk；在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。40推论在一个具有n个结点的图中，若从结点vj到vk存在一条路，则必存在一条从vj到vk而边数小于n的通路。412 连通图 定义7-2.2在无向图G中，结点

15、u和v之间若存在一条路，则称结点u和结点v是连通的。可以证明，结点之间连通性是结点集V上的等价关系，对应这个等价关系，可对结点集V作出一个划分；把V分成非空子集V1，V2，Vm，使得两个结点vj和vk是连通的，当且仅当它们属于同一个Vi；把子图G(V1)，G(V2)，G(Vm)称为图G的连通分支(图)，今后我们把图G的连通分支数记作W(G)。42定义7-2.3若图G只有一个连通分支，则称G是连通图。在连通图中，任意两个结点之间必是连通的。例(a)是连通图(b)是具有三个连通分支的非连通图 43注意：对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。在图中删除结点v，即是把v以及与v关

16、联的边都删去。例如：在图7-2.3(a)中删除v1，即由图(a)变为图(b)。44在图中删除某边，仅需把该边删去。例如：在图7-2.3(a)中删除边e即由图(a)变为图(c)。453 割集与连通度 定义定义7-2.4设无向图G为连通图，若有点集V1V，使图G删除了V1的所有结点后，所得的子图是不连通图，而删除了V1的任何真子集后，所得到的子图仍是连通图，则称V1是G的一个点割集。若某一个结点构成一个点割集，则称该结点为割点。(a)中移去割点s后，成为有两个连通分支的非连通图(b)。例：46若G不是完全图，定义k(G)minV1V1是G的点割集为G的点点连连通通度度(或连通度)。连通度k(G)是

17、为了产生一个不连通图需要删去的点的最少数目。于是一个不连通图的连通度等于0，存在割点的连通图其连通度为1。完全图Kp中，删去任何m个(mp-1)点后仍是连通图，但是删去了p-1个点后产生了一个平凡图，故定义k(Kp)=p-1。47定义7-2.5设无向图G为连通图，若有边集E1E，使图G中删除了El中的所有边后得到的子图是不连通图，而删除了El的任一真子集后得到的子图是连通图，则称E1是G的一个边割集。若某一个边构成一个边割集，则称该边为割边(或桥)。48G的割边也就是G的一条边e使W(G-e)W(G)。定义非平凡图G的边连通度为：(G)minE1 E1是G的边割集。边连通度(G)是为了产生一个

18、不连通图需要删去的边的最少数目。对平凡图G定义(G)0，此外一个不连通图也有(G)0。49定理7-2.2对于任何一个图G，有k(G)(G)(G)证明：若若G不连通：不连通：则k(G)(G)0，故上式成立。若若G连通：连通：1)证明证明(G)(G)如果G是平凡图，则(G)0(G)；若G是非平凡图，则因每一结点的所有关联边必含一个边割集，故(G)(G)。502)再证再证k(G)(G)(a)设(G)1，即G有一割边，显然这时k(G)1，上式成立。(b)设(G)2，则必可删去某(G)条边，使G不连通，而删去其中(G)-1条边，它仍是连通的，且有一条桥e(u，v)。对(G)-1条边中的每一条边都选取一个

19、不同于u，v的端点，把这些端点删去，则必至少删去(G)-1条边。51若这样产生的图是不连通的，则k(G)(G)-1(G)；若这样产生的图是连通的，则e仍是桥，此时再删去u或v，就必产生一个不连通图，故k(G)(G)。由由1)和和2)得得k(G)(G)(G)52定理的证明可用图定理的证明可用图 7-2.5 7-2.5 来予以说明。来予以说明。这里：这里：k(G)2，(G)3，(G)4。53定理7-2.3一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每一条路都通过v。证明：若结点v是连通图G的一个割点，设删去v得到子图G，则G至少包含两个连通分支。设其为G1，

20、G2。54任取uV1，wV2，因为G是连通的，故在G中必有一条连结u和w的路C，但u和w在G中属于两个不同的连通分支，故u和w必不连通，因此C必须通过v，故u和w之间的任意一条路都通过v。反之反之，若连接图G中某两个结点的每一条路都通过v，删去v得到子图G，在G中这两个结点必然不连通，故v是图G的割点。554 有向图的连通性无向图的连通性，不能直接推广到有向图。在有向图G中，从结点u到v有一条路，称从u可达v。可达性是有向图结点集上的二元关系，它是自反和传递的，但一般来说它不是对称的，因为如果从u到v有一条路，不一定必有v到u的一条路，故可达性不是等价关系。56如果u可达v，它们之间可能不止一

21、条路，在所有这些路中，最短路的长度称为结点u和v之间的距离(或短程线)，记作d，它满足下列性质：d0d0d+dd如果从u到v是不可达的，则通常写成d=注意：当u可达v，且v也可达u时，d不一定等于d。有关距离的概念对无向图也适用。57定义7-2.6在简单有向图G中，任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个图是单侧连通的。如果对于图G中的任何一对结点两者之间是相互可达的，则称这个图是强连通的。如果在图G中略去边的方向，将它看成无向图后，图是连通的，则称该图弱连通的。58 从上述定义可以看出，若图G是强连通的，则必是单侧连通的；若图G是单侧连通的，则必是弱连通的。这两个命题，其

22、逆不真。例如：图7-2.6中分别给出了强连通图(a)，单侧连通图(b)，弱连通图(c)。59定理7-2.4一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。证明：充分性 如果G中有一个回路，它至少包含每个结点一次，则G中任两个结点都是相互可达的，故G是强连通图。必要性如果有向图G是强连通的，则任两个结点都是相互可达。故必可作一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的各结点就不是相互可达，与强连通条件矛盾。605 分图 定义7-2.7在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质

23、的最大子图，称为弱分图。61例：由v1，v2，v3，v4或v5导出的子图都是强分图。由v1，v2，v3，v4，v5导出的子图是单侧分图，也是弱分图。62强分图可由v1，v2，v3，v4导出；单侧分图可由v1，v2，v3，v1，v3，v4导出；弱分图可由v1，v2，v3，v4导出。63定理7-2.5在有向图G中，它的每一个结点位于且只位于一个强分图中。证明：1)假设vV，令S是G中所有与v相互可达的结点的集合，当然v也在S之中，而S是G的一个强分图。因此，G的每一结点必位于一个强分图中。2)假设v位于两个不同的强分图S1与S2之中，因为S1中每个结点与v相互可达，而v与S2中每个结点也相互可达，

24、故S1中任何一结点与S2中任何一个结点通过v都相互可达，这与题设S1为强分图矛盾。故G的每一结点只能位于一个强分图之中。64作业：P287(5)(8)657-3图的矩阵表示 1邻接矩阵在第三章中，对于给定集合A上的关系R，可用一个有向图表示，这种图形表示了集合A上元素之间的关系，关系图亦表示了集合中元素间的邻接关系。对于关系图，可用一个矩阵表示，一个矩阵也必对应于一个标定结点序号的关系图。66定义7-3.1设G是一个简单图，它有n个结点Vv1，v2，vn，则n阶方阵A(G)(aij)称为G的邻接矩阵。adj 表示邻接，nadj 表示不邻接。67例：图7-3.1 邻接矩阵为：68注意：当给定的简

25、单图是无向图时，邻接矩阵为对称的，当给定图是有向图时，邻接矩阵并不一定对称。图G的邻接矩阵显然与n个结点的标定次序v1，v2，vn有关。69例如：图7-3.2中，若将结点v1和v2的次序调换一下，那么新的邻接矩阵将是原邻接矩阵第一、二行对调，第一、二列对调而得到。70说明：把一个n阶方阵A的某些列作一置换，再把相应的行作同样置换，得到一个新的n阶方阵A，称A与A置换等价。显然置换等价是n阶布尔矩阵集合上的一个等价关系。有向图的结点，按不同次序所写出的邻接矩阵是彼此置换等价的，今后略去这种元素次序的任意性，可取图的任意一个邻接矩阵作为该图的矩阵表示。71从邻接矩阵A中看到，第i行元素是由结点vi

26、出发的边所决定，第i行中值为1的元素数目等于vi的出度。同理，在第j列中值为1的元素数目是vj的入度。如果给定的一个图是零图，则其对应的矩阵中，所有元素都为零，即它是一个零矩阵，反之亦然。722 两结点之间路的条数设有向图G的结点集合Vv1，v2，vn，它的邻接矩阵为：A(G)(aij)nn。计算：从结点从结点vi到结点到结点vj的长度为的长度为2的路的数目。的路的数目。分析：每条从vi到vj的长度为2的路，中间必须经过一个结点vk，即vivkvj(1kn)；如果图G中有路vivkvj存在，那么aikakj1即aikakj1，反之如果图G中不存在路vivkvj，那么aik0或akj0，即aik

27、akj0。于是从结点vi到结点vj的长度为2的路的数目等于：73按照矩阵的乘法规则，这恰好等于矩阵(A(G)2中第i行，第j列的元素。74再分析：从vi到vj的长度为3的路，可以看作是由vi到vk的一条长度为1的路，再联结vk到vj的一条长度为2的路。故vi到vj的长度为3的路的数：一般地有：75证明：对l用数学归纳法：当 l2时，由上可知显然成立。设命题对l 成立；76根据邻接矩阵的定义：aik表示联接vi与vk的长度为1的路的数目；故：上式右边的每一项表示由vi经过一条边到vk，再由vk经过一条长度为l的路到vj的总长度为l+1的路的数目。77从上述矩阵中可以得到如下结论：v1与v2之间有

28、2条长度为3的路，结点v1与v3之间有一条长度为2的路，在结点v2有四条长度为4的回路，但没有长度为3的回路。例1：给定一图G如图所示。78说明：对于有向图G中任意两个结点之间的可达性，亦可用矩阵表达。793 可达性矩阵 80注意：可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。一般地讲，可由图G的邻接矩阵A得到可达性矩阵P，即令BnA+A2+An，再从Bn中将不为零的元素均改换为l，而为零的元素不变，这个改换的矩阵即为可达性矩阵P。81例题1：设图G的邻接矩阵为 求：G的可达性矩阵。82解：故由此可知图G中任两结点间均是可达的，并且任一结点均有回路，因而此图

29、是个连通图。83上述计算可达性矩阵的方法还是比较复杂。因为可达性矩阵是一个元素为1或0布尔矩阵；由于在每个Al矩阵中，对于两个结点间具有路的数目不感兴趣，它所关心的是该两结点间是否有路存在，因此可将矩阵A，A2，An，分别改为布尔矩阵A(1)，A(2)，A(n)，故PA(1)A(2)A(n)，其中A(i)表示在布尔运算意义下A的i次方。例题2设图G如图所示，求可达性矩阵P。84解：85同理可得：86说明：从上例的运算可以看到，如果把邻接矩阵看作是结点集V上关系R的关系矩阵，则可达性矩阵P即为MR，因此可达性矩阵P亦可用Warshall算法计算。上述可达性矩阵等概念，可以很容易地推广到无向图中，

30、只要将无向图中每条无向边看成是具有相反方向的两条边，这样，一个无向图就可看成一个有向图。无向图的邻接矩阵是一个对称矩阵，其可达性矩阵称为连通矩阵，也是对称的。87对于一个无向图G，除了可用邻接矩阵表示外，还对应着一个称为图G的完全关联矩阵。假定图G无自回路，如因某种运算得到了自回路，则将它删去。884 完全关联矩阵 例：例：对于图7-3.5 其关联矩阵为：89从关联矩阵中可以看出图形的一些性质：1.图中每一边关联两个结点，故M(G)的每一列中只有两个1。2.每一行中元素的和数是对应结点的度数。3.一行中元素全为0，其对应的结点为孤立结点。4.两个平行边其对应的两列相同。5.同一个图当结点或边的

31、编序不同时，其对应的M(G)仅有行序，列序的差别。9091例：对于图7-3.6 其关联矩阵为：925 完全关联矩阵的行相加施行这种运算，实际上就是相应于把G的结点vi与vj合并。939495例1图7-3.7(a)中使v4与v5合并得到图7-3.7(b)。96例例2图(a)合并结点v2和v3，删去自回路得图(b)。976 关联矩阵的秩定理7-3.2如果一个连通图G有r个结点，则其完全关联矩阵M(G)的秩为r-1，即rankM(G)r-1。证明仅对无向图进行证明。9899100101例例3计算图7-3.7(a)中其对应的完全关联矩阵的秩数，以验证定理7-3.2。图7-3.7(a)的完全关联矩阵为：

32、102103最后一个矩阵其秩为4，即rankM(G)5-14。104推论设图G有r个结点，w个最大连通子图，则图G完全关联矩阵的秩为r-w。1057-4 7-4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图“哥尼斯堡七桥问题哥尼斯堡七桥问题”：(昂哈德欧拉(LeonhardEuler)哥尼斯堡城市有一条横贯全城的普雷格尔(Pregel)河，城的各部分用七座桥联接，每逢假日，城中居民进行环城逛游，这样就产生了一个问题，能不能设计一次“遍游”，使得从某地出发对每座跨河桥只走一次，而在遍历了七桥之后却又能回到原地。106在图7-4.1中画出了哥尼斯堡城图，城的四个陆地部分分别标以A、B、C、D。欧拉在欧拉在

33、1736年的论文中提出了一条简单的准则，确年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。定了哥尼斯堡七桥问题是不能解的。107将陆地设想为图的结点，而把桥画成相应的连接边，这样城图可简化成如图7-4.2所示，于是通过哥尼斯堡城中每座桥一次且仅一次的问题，等价于在图7-4.2中从某一结点出发找一条路，通过它的每条边一次且仅一次，并回到原结点。分析：1081 欧拉图 定义7-4.1给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉欧拉路路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路欧拉回路。具有欧拉回路的图称作欧拉图欧拉图。定理7-4.

34、2无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。109证明：必要性设G具有欧拉路，即有点边序列v0e1v1e2v2eiviei+1ekvk，其中结点可能重复出现，但边不重复，因为欧拉路经过所有图G的结点，故图G必是连通的。对任意一个不是端点的结点vi，在欧拉路中每当vi出现一次，必关联两条边，故vi虽可重复出现，但deg(vi)必是偶数。对于端点，若v0vk，则d(v0)为偶数，即G中无奇数度结点，若端点v0与vk不同，则d(v0)为奇数，d(vk)为奇数，G中就有两个奇数度结点。110充分性若图G连通，有零个或两个奇数度结点，构造一条欧拉路如下：(1)若有两个奇数度结

35、点，则从其中的一个结点开始构造一条迹，即从v0出发经关联边e1“进入”v1，若deg(v1)为偶数，则必可由v1再经关联边e2进入v2，如此进行下去，每边仅取一次。由于G是连通的，故必可到达另一奇数度结点停下，得到一条迹L1：v0e1v1e2viei+1vk。若G中没有奇数度结点则从任一结点v0出发，用上述方法必可回到结点v0，得到上述一条闭迹L1。111(2)若L1通过了G的所有边，则L1就是欧拉路。(3)若G中去掉L1后得到子图G，则G中每个结点度数为偶数，因为原来的图是连通的，故L1与G至少有一个结点vi重合，在G中由vi出发重复(1)的方法，得到闭迹L2。(4)当L1与L2组合在一起，

36、如果恰是G，则即得欧拉路，否则重复(3)可得到闭迹L3，以此类推直到得到一条经过图G中所有边的欧拉路。112推论无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点度数全为偶数。由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图7-4.2中可以看到deg(A)5，deg(B)deg(C)deg(D)3，故欧拉回路必不存在。113一笔画的判别问题（与七桥问题类似）：要判定一个图G是否可一笔画出，有两种情况：从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路

37、和欧拉回路的判定条件予以解决。114例1：图7-4.3(a)中，因为deg(v2)deg(v3)3，deg(v1)deg(v4)deg(v5)2，故必有从v2到v3的一笔画。例2：图7-4.3(b)中，所有结点度数均为偶数，所以可以从任一结点出发，一笔画回到原出发点。1152 有向欧拉图 定义7-4.2给定有向图G，通过图中每边一次且仅一次的一条单向路(回路)，称作单向欧拉路欧拉路(回路回路)。定理7-4.2有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的

38、入度比出度大1，另一个结点的入度比出度小1。116定理定理7-4.2证明说明：证明说明：这个定理的证明，可以看作是无向图的欧拉路的推广，因为对于有向图的任意一个结点来说，如果入度与出度相等，则该点的总度数为偶数，若入度与出度之差为1时，其总度数为奇数，因此定理7-4.2的证明与定理7-4.1的证明类似。117例例1计算机鼓轮的设计。其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在图7-4.4中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，触点将得到信息1101，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息1010。问：问：鼓轮上鼓轮上16个部分怎样安排

39、导体及绝缘体，个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。组不同的四位二进制数信息。设有旋转鼓轮其表面被等分成24个部分，如图7-4.4所示。118设有一个八个结点的有向图(图7-4.5)，其结点分别记为三位二进制数000，001，010，011，100，101，110，111。设ai0，1，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a3l。该两条边分别记为a1a2a30和a1a2a3l。119按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是

40、a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。因为图中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。以结点a1a2a3为终点的两条边为0a1a2a3和1a1a2a3。120根据邻接边的标号记法，这16个二进制数可写成对应的二进制数序列0000100110101111。把这个序列排成环状,即与所求的鼓轮相对应，如图7-4.4所示。在图7-4.5中，每个结点的入度等于2，出度等于2，故在图中必可找到一条欧拉回路。如：(e0e1e2e4e9e3e6e13e10e5e11e7e15e

41、14e12e8)。121把上面的例子推广到鼓轮具有把上面的例子推广到鼓轮具有n个触点的情况：个触点的情况：构造2n-1个结点的有向图，设每个结点标记为n-1位二进制数，从结点a1a2an-1出发，有一条终点为a2a3an-10的边，该边记为a1a2an-10；还有一条边的终点为a2a3an-11的边，该边记为a1a2an-11。这样构造的有向图，其每一结点的出度和入度都是2，故必是欧拉图。由于邻接边的标记是第一条边的后n-1位二进制数与第二条边的前n-1位二进制数相同，为此就有一种2n个二进制数的环形排列与所求的鼓轮相对应。1223 汉密尔顿图 1859年，威廉汉密尔顿爵士(SirWillia

42、nHamilton)在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图7-4.6中找到一条回路，使它含有这个图的所有结点?汉密尔顿回路的问题（与欧拉回路非常类似）。汉密尔顿回路的问题（与欧拉回路非常类似）。123说明：如果把每个结点看成一个城市，联结两个结点的边看成是交通线，于是他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地?他把这个问题称为周游世界问题。按图7-4.6中所给的编号，可以看出这样一条回路是存在的。对于任何连通图也有类似的问题。124定义7-4.3给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路汉密尔顿路

43、。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图汉密尔顿图。定理7-4.3若图G具有汉密尔顿回路，则对于结点集V的每个非空子集S均有W(G-S)|S|成立。其中W(G-S)是G-S中连通分支数。125证明：设C是G的一条汉密尔顿回路，则对于V的任何一个非空子集S在C中删去S中任一结点a1，则C-a1是连通的非回路，若再删去S中另一结点a2，则W(C-a1-a2)2，由归纳法可得：W(C-S)|S|同时C-S是G-S的一个生成子图，因而W(G-S)W(C-S)所以W(G-S)|S|126说明：利用定理7-4.3可以证明某些图是

44、非汉密尔顿图。如图7-4.7中若取Sv1，v4，则G-S中有三个分图，故G不是汉密尔顿图。127如果W(G-S)|S|成立，不能说明某一特定图是汉密尔顿图。例如：（著名的彼得森(Petersen)图）如图7-4.8中所示，在图中删去任一个结点或任意两个结点，不能使它不连通；删去3个结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或5个以上的结点，余下子图的结点数都不大于5，故必不能有5个以上的连通分支数。所以该图满足W(G-S)|S|，但是可以证明它是非汉密尔顿图。1284 汉密尔顿图的充分条件 定理7-4.4设G具有n个结点的简单图，如果G中每一

45、对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。证明：首先证明首先证明G是连通图。是连通图。若G有两个或更多个互不连通的分图，设一个分图中有n1个结点，任取一个结点v1。设另一个分图中有n2个结点，任取一个结点v2，因为d(v1)n1-1，d(v2)n2-1，故d(v1)+d(v2)n1+n2-2n-1，这与题设矛盾，故G必连通。129其次，从一条边出发构成一条路，证明它是汉密尔其次，从一条边出发构成一条路，证明它是汉密尔顿路。顿路。设在G中有p-1条边的路，pn，它的结点序列为v1，v2，vp。如果有v1或vp邻接于不在这条路上的一个结点，我们立刻可扩展这条路，使它包含这一个结点，

46、从而得到p条边的路。否则，v1和vp都只邻接于这条路上的结点，证明在这证明在这种情况下，存在一条回路包含结点种情况下，存在一条回路包含结点v1，v2，vp。若v1邻接于vp，则v1，v2，vp，v1即为所求的回路。130131如果vp不邻接于vl-1，vm-1，vt-1中任一个，则vp至多邻接于p-k-1个结点，deg(vp)p-k-1，deg(v1)k，故deg(vp)+deg(v1)p-k-1+kp-1n-1，即v1与vp度数之和至多为n一2，得到矛盾。至此，有包含所有结点v1，v2，vp的一条回路，因为G是连通的，所以在G中必有一个不属于该回路的结点vx与v1v2vp中的某一个结点vk邻

47、接，如图7-4.9(b)所示。132于是就得到一条包含p条边的路(vx，vk，vk+1，vj-1，vp，vp-1，vj，v1，v2，vk-1)。如图7-4.9(c)所示，重复前述构造法，直到得到n-1条边的路。定理定理7-4.4的条件对于图中汉密尔顿路的条件对于图中汉密尔顿路的存在性只是充分的，但并不是必要的存在性只是充分的，但并不是必要条件。条件。设G是n边形，如图7-4.10，其中n6，虽然任何两个结点度数之和是46-1，但在G中有一条汉密尔顿路。133例题1考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要

48、求的考试安排总是可能的。设G为具有七个结点的图，每个结点对应于一门课程考试，如果两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边。因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当的安排。证明134定理7-4.5设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n，则在G中存在一条汉密尔顿回路。证明由定理74.4可知必有一条汉密尔顿路，设为v1v2vn，如果v1与vn邻接，则定理得证。如果v1与vn不邻接，假设v1邻接于vi1，vi2，vik，2ijn-1，可以证

49、明：证明：vn必邻接于必邻接于vi1-1，vi2-1，vik-1中之一中之一。135如果vn不邻接于vi1-1，vi2-1，vik-1中任一结点，则vn至多邻接于n-k-1个结点，因而d(vn)n-k-1，而d(v1)k，故d(v1)+d(vn)n-k-1+kn-1，与题设矛盾。所以必有汉密尔顿回路v1v2vj-1vnvn-1vjv1，如图7-4.11所示。1365 汉密尔顿图的充要条件 定义7-4.4给定图G有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G，对图G重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包闭包，记作C(G)。137例：下图给出

50、了对六个结点的一个图G，构造它的闭包的过程。138定理7-4.6当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。例题2指出图7-4.13(a)所示的图G中没有汉密尔顿路。139解用A标记任意一个结点a，所有与a邻接的结点均标记B，继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到所有结点标记完毕。这个有标记的图如图7-4.13(b)所示。注意：如果在标记过程中，遇到相邻结点出现相同标记时，可在此对应边上增加一个结点，并标上相异标记。如图所示。140如果在图G中有一条汉密尔顿路，那么它必交替通过结点A和结点B，然而本例中共有九个A结点和七个B结点，所以不可能存