离散数学-第6章-图论.ppt

1,离散数学,西安交通大学电子与信息工程学院计算机系,2,离散数学,6.Euler图Euler图的定义 Euler图的理论,3,离散数学,6 Euler图Euler图产生的背景就是前面介绍的Konigsberg七桥问题，有了前面几节的知识后，我们可以讨论Euler图的解决方法了。定义1.Euler路 Euler 圈 Euler图 设 G(V,E)是连通的、无孤立点的图。(1)Euler路是一条简单路P，路P穿过图G中每条边一次且仅一次；(2)Euler圈是一条简单圈C，圈C穿过图G中每条边一次且仅一次；(3)含有Euler 圈的图G称为Euler图(简称为E-图)。,4,离散数学,注：这类通过各边恰好一次的问题就是通常所说的一笔画问题（即笔不离纸，线不重复）。定理1.(Euler定理)设 G(V,E)是无孤立点的无向图。那么，G是Euler图 G是连通的且G中无奇结点。注：G中无奇结点即是G中每个结点都是偶结点。证.先证必要性)：(采用蹦圈法)设C是G的一条Euler圈。则(1)图G是连通的：首先，由于图G中无孤立点，所以图G中的每个结点都有一些边与之关联，而Euler圈C包含了图G中的每一条边，于是圈C在通过各边的同时必通过图G中每个结点。因而图G中每个结点都在Euler圈C上。,5,离散数学,因此，图G中任何两结点，沿着Euler圈C可相互到达，故图G是连通的。(2)图G中无奇结点：其次，当圈C穿过某结点时，必从一边进，从另一边出，因此给该结点度数的贡献是2；尽管圈C可能会多次穿过某些结点，但由上述原因和Euler圈C仅穿过每条边一次(C是Euler圈)及每个结点都在圈C上可知：圈C穿过某结点k次，就给该结点的度数贡献2 k；因此，图G中每个结点的度数必全为偶数，即图G中无奇结点。再证充分性)：(算法)No1.从任一结点出发，走成一个简单圈C；由于图G中每个结点都是偶结点(无奇结点)，且图G连通，故图G中至少存在一个简单圈C。,6,离散数学,No2.若此简单圈C已是Euler圈，则此图G就是Euler图，算法结束(出口)。No3.(插圈)否则，图G中必还有若干条边不属于圈C。由图G的连通性可知：必有圈C外的边ej与圈C上的结点vi相关联(vi称为接触点)。由于在图G中除去圈C(只删边，不删结点)后所得的子图G中，每个结点仍都是偶结点(因为在圈C上的结点，都是一边进，另一,7,离散数学,边出。因此圈C每穿过某结点一次，该结点的度数就被消耗掉2。故这些结点在删除圈C的边时，它们的度数都减少一个偶数)。由于图G中每个结点都仍是偶结点，于是从此结点vi出发，经过边ej 及子图G中的其它边，必可走出一个简单圈C，回到出发点vi。故圈C与圈C必由结点vi相连(如图1所示)。将圈C插入圈C中，形成一条新的更长的简单圈C:=CC，goto No2。由于图G中的边数是有限的，故算法不可能无穷的进行下去，所以算法必定在有限步结束。最后一定能得到一个包括图G中所有边在其上的简单圈C，此圈C即是Euler圈。所以图G即为Euler图。注：美籍华人。著有离散数学基础(刘振宏译)；条件：全是偶结点保证可走出简单圈；条件：连通性保证边(从而结点)可走完。,8,离散数学,例1.图G如图2所示。问图G是否为一Euler图？若是，试求出其Euler圈。解.由于图G中的六个结点全都是偶结点，并且图G显然是连通的，故根据上述Euler定理可知，图G为Euler图。按照算法，可求得图G中的Euler圈。具体步骤如下：在图中任意找一简单圈C(1,2,3,1)。发现还有7条边不在此圈,9,离散数学,中，边(3,4)不在圈中且与圈中的结点3相关联。由结点3出发经过边(3,4)可得一简单圈C(3,4,5,3)，将C插入C得到一个新的更长的简单圈 C(1,2,3,4,5,3,1)。此时仍有4条边不在圈C中，边(2,5)不在圈中且与圈中的结点2关联。由结点2出发经过边(2,5)又可得到一简单圈C(2,5,6,4,2)，将C插入C又得到一条新的更长的简单圈C(1,2,5,6,4,2,3,4,5,3,1)。由于图G中所有的边都已在圈C中，故知此圈C为图G的一个Euler圈。例2哥尼斯堡七桥问题无解。解.在七桥图中(图3)，由于每个结点均为奇结点，故由Euler定理的充要条件知，该图中不存在经过每条边一次且仅一次的Euler圈。即七桥图不是Euler图。该问题无解。,10,离散数学,11,离散数学,推论.(Euler定理二)设 G(V,E)是无孤立点的无向图。那么，G中有Euler路 G是连通的且G中恰有两个奇结点。证.(采用增边删边法及抻路法)G中有Euler路P=(v1,v2,vk)G=G(v1,vk)中有Euler圈C=(v1,v2,vk,v1)G是连通的且G中全是偶结点(Euler定理)G是连通的且G中恰有两个奇结点v1,vk(删掉边e=(v1,vk)。,12,离散数学,定义2.割边(cut edge)设G(V,E)是无向图，eE。若W(Ge)W(G)，则称边e为图G的割边。这里W(G)表示图G中的连通支数。例3.图G如图5所示。G中的边e是割边。因为W(Ge)=21=W(G)。如何在恰有两个奇结点的连通图中寻找Euler路，可采用下面的算法。Fleury算法：寻找在两个奇结点间的一条Euler路的算法(1)从一个奇结点出发，每走一边标记一边；下次不走标记过的边；(2)在走边的过程中，除非没有其它选择时才走割边。,13,离散数学,例4.如图6所示的图G中有一条Euler路。解.在右图G中，恰有两个奇结点4和9，且图G是连通的，故按Euler定理二可知其存在着Euler路。利用Fleury算法，可求得其一条Euler路为P=(4,5,6,4,3,2,1,3,10,12,11,10,9,8,7,9)。,14,离散数学,定理2.设G(V,E)是无孤立点的有向图。那么，G是Euler图 G是(弱)连通的且G中每个结点的出度都等于进度。证.仿定理1的证明可证。只不过这里的Euler圈应是有向圈。定理3 设 G(V,E)是无孤立点的有向图。那么，G中有Euler路G是(弱)连通的且G中除两个结点外，其余每个结点的出度都等于进度。而这两个结点：一个结点的进度比出度大1(终点)，另一个结点的出度比进度大1(起点)。证.仿定理1推论的证明可证。只不过这里的Euler路应是有向路。,15,离散数学,应用一：高效率计算机磁鼓的设计 计算机旋转磁鼓的表面被等分成2n个部分，与n个电刷相接触。绝缘体(空白部分)不通电表示信号0；导体(阴影部分)通电表示信号1。从而n个电刷上就产生一n位二进制信号。我们的问题是：如何合理的按排磁鼓表面上的空白与阴影部分，使的磁鼓转动n个位置，就可读出2n个不同的二进制数。图7表示有三个电刷a,b,c的磁鼓，磁鼓表面被分成了八个部分。它旋转一周只能读出六个不同的二进制数：110,101,011,100,000,001。因此按排不合理。如何设计？我们考虑四个两位二进制数：00,01,10,11,16,离散数学,将其作为一图G的结点。对于图G的任二结点p1p2和q1q2，若p2=q1，则在它们之间连一条有向边(p1p2,q1q2)，并用三位二进制数p1p2q2标记该边。图G如图8所示。图8所示的图G是一有向图，它显然是(弱)连通的，并且每个结点的进度=出度=2，满足定理2中的条件，因此存在着Euler圈。其Euler圈为：(000,001,011,111,110,101,010,100,000)。两位重复此八个三位二进制数，上述Euler圈可用一个八位二进制序列：00011101 来表示。,17,离散数学,注：此序列称为De Bruijn序列。这一应用是由Good(1946)提出的。按此序列来设计磁鼓绝缘体及导体的位置最为合理(如图9所示)，可以读出全部(八个)三位二进制数：000,001,011,111,110,101,010,100。应用二：一笔画问题对于一个给定的图，究竟需要多少笔才能画成？这里只讨论连通图的一笔画问题。因为假若一个图是不连通的，则此图的笔画问题就可以归结成对各连通支笔画的讨论。,18,离散数学,连通图的笔画是由图中奇结点的个数决定的。本章2定理2已经证明过：图中奇结点的个数是偶数。所以奇结点是成对出现的，即为2k个。(1)当k=0,1时，此连通图是一笔画的；(2)当k1时，此连通图是k笔画的(更进一步地，存在着k 条边不重的路)。应用三：中国邮路问题一个邮递员，每次送信，领取邮件，由邮局出发，要走遍他所负责的投递范围内的每一条街道，完成投递任务后，再返回邮局。问题是：他应该沿着怎样的路线走，使所走的总路程最短？,19,离散数学,这个问题抽象成图论语言就是：在给定的一个连通的带权图G=(V,E,w)(每条边上一个非负的权w(e)中，要求一个圈C，过每条边至少一次，并使圈C上的总权和w(C)达到最小。我们设图G的奇结点个数是2k(参见应用二)。这个问题的存在性是不容质疑的。我国山东师院的管梅谷教授于1962年首次研究并解决了上述问题。因此国际上将其称为中国邮路问题。(1)当k=0时(即无奇结点)，这时G是Euler图，有Euler圈，设其为C。显然，若按Euler圈C走，每条边走且仅走一次，总权和w(C)显然是最小的；(2)当k1时(即有奇结点)，我们解决问题的思路是给图G增加一些重复边，使其变成无奇结点的多重图G。由于图G是连通的，故图G也是连通的。因而根据Euler定理可知，图G必有Euler圈，设其为C。,20,离散数学,设这些需重复的边的集合是E1(E1E)，所增加的那些平行边的集合是E1=e e/eeE1，所获得新的带权多重图G=(V,E,w)，其中E=EE1，并且eE1，w(e)=w(e)(这里e/e，eE1)(参见图10)。,21,离散数学,现在由于圈C穿过图G中的每条边一次且仅一次，因而C必定穿过图G中的每条边一次。而图G中各边的总权和w(E)是固定不变的，所以要使 Euler圈C取得最小权值w(C)平行边集E1取得最小权值w(E1)边集E1取得最小权值w(E1)因而，中国邮路问题就转化为：在一给定的带权图G=(V,E,w)中，寻求这样一个边集E1E，其对应的平行边集为E1，使带权多重图G=GE1无奇结点，并使w(E1)=达到最小。我们称这样的边集E1是最优的。管梅谷教授解决此问题的思想方法我们总结为如下的定理。,22,离散数学,定理4.(管氏定理(1962)E1是最优的在图G的每个初级圈Ci上，都有E1的边(要重复的边)的长度之和不超过圈长的一半在图G的每个初级圈Ci上证.定理的证明主要基于以下两点：(1)当某条边重复k(k2)次后得到的图为Euler图时，则此边重复k-2次得到的图也一定为Euler图。(2)在图G的一个初级圈上，如果将原来的重复边都删去，而在原来没有重复边的边上都加上一条重复边，那么图中各结点的度数改变0或2，所以，这种做法不会改变图G是Euler图的性质。由此可知：当Euler圈中重复边的长度之和超过此圈总长的一半时，如作上述改变，则,23,离散数学,重复边长度之和减少，而Euler圈的性质不变。例5.在图11所示的图G中寻求最优边集E1。解.在右图G中，恰有四个奇结点，可以验证：边集E1(v1,v2),(v3,v4)是最优的。图G中共有七个初级圈：C1(v1,v2,v3,v1)，w(C1)=2+3+8=13，w(E1C1)=w(v1,v2)=26.5=1/213=1/2 w(C1)；C2(v1,v2,v4,v1)，w(C2)=2+10+7=19，,24,离散数学,w(E1C2)=w(v1,v2)=29.5=1/219=1/2 w(C2)；C3(v1,v3,v4,v1)，w(C3)=8+4+7=19，w(E1C3)=w(v3,v4)=49.5=1/219=1/2 w(C3)；C4(v2,v3,v4,v2)，w(C4)=3+4+10=17，w(E1C4)=w(v3,v4)=48.5=1/217=1/2 w(C4)；C5(v1,v2,v3,v4,v1)，w(C5)=2+3+4+7=16，w(E1C5)=w(v1,v2)+w(v3,v4)=2+4=6 8=1/216=1/2 w(C5)；C6(v1,v2,v4,v3,v1)，w(C6)=2+10+4+8=24，w(E1C6)=w(v1,v2)+w(v3,v4)=2+4=6 12=1/224=1/2 w(C6)；C7(v1,v3,v2,v4,v1)，w(C7)=8+3+10+7=28，,25,离散数学,w(E1C7)=w()=014=1/228=1/2 w(C7)；但是，边集E2(v1,v4),(v2,v3)不是最优的。因为 w(E2C5)=7+3=108=1/216=1/2 w(C5)；边集E3(v1,v3),(v2,v4)不是最优的。因为 w(E3C6)=8+10=1812=1/224=1/2 w(C6)；w(E3C7)=8+10=1814=1/228=1/2 w(C7)。注：在实际中应用管氏定理是很麻烦的。因为管氏定理要检查许多的初级圈，而且没有办法去系统的、逐个的检查，容易遗漏，因此一般不太实用。我们应另辟蹊径。(a)如果k=1,即带权图G中只有两个奇结点，(例如图12(a)，则可先求出这两个奇结点间的最短路径，然后将最短路径中的每条边重复一次(如图12(b)所示)，得到,26,离散数学,一个新的带权图G，它是一个Euler图(连通，无奇结点)，G中的Euler圈必定是取得最小值的圈。最短路径中的边必定构成最优边集E1。这里：E1(v1,v2),(v2,v3)；w(E1)=w(v1,v2)+w(v2,v3)=2+3=5。,27,离散数学,(b)如果k2,即带权图G中有2k个奇结点，匈牙利的J.Edmods和Johnson提出了如下算法，比较有效。J.Edmods和Johnson算法(匈牙利算法(1973)：No1.找出所有奇结点O=vi1,vi2,vi2k；No2.求出任一奇结点vit到另任一奇结点vis的最短路Pitis及其权w(Pitis)；(采用Dijkstra算法)No3.以O为结点集作完全图K2k，并令其边(vit,vis)上的权w(vit,vis)=w(Pitis)；No4.在带权图K2k中求出总权和最小的最大对集M*(图中不相邻边的集合的最大者，参见9偶图)；(采用J.Edmods算法(1965)No5.与M*中的每一杆(vit,vis)对应，图G中都有一条从,28,离散数学,奇结点vit到奇结点vis的最短路Pitis，我们令 E1=eePitis(vit,vis)M*于是，E1即是最优的。,29,离散数学,7.Hamilton 图 Hamilton图的定义 Hamilton图的理论,30,离散数学,7.Hamilton 图Hamilton 图的引出及其定义 Hamilton 图是由威廉哈密顿(Sir Willian Hamilton)爵士于1856年在解决关于正十二面体的一个数学游戏时首次提出的。1856年Hamilton爵士发明了一种数学游戏：一个人在(实心的)正十二面体的任意五个相继的顶点(正十二面体是由12个相同的正五边形组成，有二十个顶点，三十条棱)上插上五个大头针，形成一条路，要求另一个人扩展这条路，以形成一条过每个顶点一次且仅一次的圈。有趣的是Hamilton爵士后来将他的发明及解决方案卖给了一个玩具商，所获是25个金币。Hamilton爵士在1859年给他的朋友Graves的信中，将他的正十二面体数学游戏重新叙述为：能否在全球选定,31,离散数学,的二十个都会城市(据说有我们中国三个城市：北京、上海、西安)中，从任一城市出发，作全球航行，经过这二十个城市一次且仅一次(不能去其它城市)，然后回到出发点？这就是著名的环球航行问题或周游世界问题。Hamilton给出了这个问题的肯定的答案(参见图1及图2)。,32,离散数学,注：威廉哈密顿(Sir Willian Hamilton(1805-1865)爵士是(英国)爱尔兰最伟大的学者之一。他是都柏林大学的天文学教授，在那里他出版了许多关于物理和数学的论文。在数学方面，他提出了著名的四元组理论和对复数系统的归纳。四元组理论奠定了抽象代数的发展基础。还据此提出了矢量概念。在理论物理学里，有著名的哈密顿动力学系统。定义1.Hamilton路 圈 图 设G(V,E)是简单图。则(1)H-路是一条初级路，它穿过图中每个结点一次且仅一次；(2)H-圈是一条初级圈，它穿过图中每个结点一次且仅一次；(3)H-图是含有H-圈的图。,33,离散数学,注：需要指出的是，尽管从表面上看Hamilton问题和Euler问题似乎很相似，但它们之间并无必然的联系。E-圈(E-图)未必是H-圈(H-图)；H-圈(H-图)也未必是E-圈(E-图)。因为，H-圈是初级圈，强调的是穿过每个结点一次且仅一次；而E-圈是简单圈，强调的是穿过每条边一次且仅一次。下面的图3和图4可以说明这点。,34,离散数学,判定E-圈(E-图)的充要条件(等价性条件)已经得到，它就是Euler定理。所以Euler 问题在理论上已经彻底解决；而判定H-圈(H-图)的充要条件(等价性条件)迄今为止人们还未提出，人们只是得到一些是必要性条件或者是充分性条件的单边(单方向)判定方法。所以Hamilton问题在理论上远未得到彻底解决。判定H-圈(H-图)的充分性条件只能用来肯定，不能用来否定。即只能在满足条件时用来证明有H-圈(是H-图)；而不能在不满足条件时用来证明没有H-圈(不是H-图)。判定H-圈(H-图)的必要性条件只能用来否定，不能用来肯定。即在不满足条件时用来证明没有H-圈(不是H-图)；而不能在满足条件时用来证明有H-圈(是H-图)。近年来，人们对Hamilton问题的研究一直没有停止，不断的有新成果面世。判定H-图(H-圈)的必要性定理(必要性条件),35,离散数学,定理1.(必要性定理)设G(V,E)是简单无向图。则 G是H图(SV)(S w(GS)|S|)。其中：w(G)表示图G的连通支数(分图个数)。证.由于G是H图，故G中含有H-圈，设其为C。(1)先证w(CS)|S|：对于结点集V的任一个非空子集S，在H-圈C中删去S中的|S|个结点，由归纳法易于证明(见注)：CS的分图个数不会超过所删去的结点个数|S|，即w(CS)|S|。(2)次证w(GS)w(CS)：由于CS是GS的一个生成子图，故此GS的边要比CS的边多，因而GS的连通性要比CS的连通性强，所以GS的分图个数不会超过CS的分图个数，即 w(GS)w(CS)。最后，根据(1)和(2)，我们得到：w(GS)|S|。,36,离散数学,注：w(CS)|S|的数学归纳法证明.(1)基始当|S|=1时，在圈C中删去一个结点，所得子图CS是一条连通的路，故有w(CS)=11=|S|；(2)归纳假设当|S|=k时，假设有w(CS)|S|=k；(3)归纳当|S|=k+1时，设v是S中的任一结点，我们令S:=Sv，则有|S|=k。于是根据归纳假设有w(CS)|S|；而S=Sv，在圈C上删去S的k+1个结点，可分为两步：先在圈C上删去S的k个结点，将圈C分成w(CS)段；然后在这些段的某一段上删去结点v；若结点v在该段的头上，则删去结点v，不会增加分图的个数，即有 w(CS)=w(CS)；若结点v不在该段的头上(在中间)，则删去结点v，该段一分为二，分图的个数会增加一，即有 w(CS)=w(CS)+1；于是，综合和的结果，总有w(CS)w(CS)+1|S|+1=|S|。定理1实际上是将关于图G的讨论转化到其H-圈C上的讨论。这其实就是用了蹦圈法。,37,离散数学,例1.图5(a)所示的图G不是H-图。在图5(a)中，有9个结点。当将中间层上的三个结点删去时(即S=v4,v5,v6,|S|=3)，此时图5(a)变为图5(b)，而图5(b)的分图个数为4，即 w(GS)=43=|S|，不满足定理1的必要性条件，故由定理1知它不是H-图。,38,离散数学,例2.图6(a)所示的Petersen图P满足定理1的必要性条件，但却不是H-图。Chvatalv在1973 年用穷举法证明了P-图不是H-图。但P-图满足定理1的必要性条件。这点可利用P-图的轴对称性，同样用穷举法来加以证明：在P-图中，若删去一个或两个结点，都不可能使原图不连通；若删去三个结点，最多只能得到具有两个连通支的子图(一种情况如图6(b)所示)；若删去四个结点，最多只能得到具有三个连通支的子图(一种情况如图6(c)所示)；若删去五个或五个以上的结点，余下子图的结点数都不超过5，故其连通支数必不会超过5；所以Petersen图满足定理1的必要性条件。,39,离散数学,注：其余类似情况是对称的。判定无向图是H-图的必要条件除了定理1外，还有两个：一个是标记法(着色法)。它是基于偶图理论的，所以我们放在8.二分图来讲；另一个是格林贝格柯车列夫定理。它是基于平面图理论的，所以我们放在9.平面图来讲。判定H-图(H-圈)的充分性定理(充分性条件),40,离散数学,定理2.(DKnig定理(充分性定理)设G(V,E)是简单无向图，且|V|=n。则 对任意一对结点u,vV，均有 deg(u)+deg(v)n-1(*)G中必有一条H-路。证.先证：G是连通的(采用反证法)；假若不然，则在图G中至少有两个分图G1，G2(此间当然无边相连)。设G1有n1个结点，G2有n2个结点。任取结点u0G1，v0G2。注意到：n1+n2n，deg(u0)n1-1，deg(v0)n2-1，从而 deg(u0)+deg(v0)(n1-1)+(n2-1)=n1+n2-2n-2n-1 这就与条件(*)矛盾了。故图G是连通的。次证：图G中必有一条H-路；Knig算法：(用此算法必可求得图G中的一条H-路),41,离散数学,No1.从G中任一结点v出发，走出一条初级路，并将此路的两端尽量延伸到尽头。不妨设此路为 P=(v1,v2,vp)，|P|=p-1。注：所谓将路的两端已延伸到尽头是指：(v0V)(v0,v1)E(v0,v1)P)(vp+1V)(vP,vp+1)E(vp,vp+1)P)。即路P的两个端点和不在路P上的任何结点都不相邻。若有相邻，那么就立即向两端延伸路P，使它包含这些结点。也就是说：这里得到的初级路P，它的两端只与路中的某些结点相邻，而不与路P之外的任何结点相邻。No2.若p=n，则此路P已是H-路。exit；否则pn(故pn-1)，兹证明初级路P必可被改造成一初级圈C，且有|C|=|P|+1。,42,离散数学,No3.若端点v1与端点vp相邻，我们将边(v1,vp)并入路P，则立即得到一初级圈C=(v1,v2,vp,v1)，并且|C|=|P|+1。go to No5。No4.若端点v1与端点vp不相邻，我们设与端点v1相邻的结点有k个，不妨设它们是vi1,vi2,vik，而且这些结点全都在路P上(否则，路没有走到尽头)。这时，端点vp必至少与k个结点vi1-1,vi2-1,vik-1中的某一个相邻(是指结点vi1,vi2,vik在路P上的前一个结点)。假若不然，由于deg(v1)=k，则deg(vp)p-1-k(与端点vp相邻的结点全都在路P上(否则，路没有走到尽头)。路P上共有p个结点，与结点vp相邻的结点，应该去掉结点vp自己以及已设不于它相邻的k个结点vi1-1,vi2-1,vik-1，不会超过p-1-k个结点)。于是，deg(v1)+deg(vp)k+(p-1-k)=p-1n-1(因pn)这与条件(*)矛盾。,43,离散数学,从而不妨设结点vp与结点vij-1(1jk)相邻，我们就立即得到一个通过结点v1,v2,vp的初级圈：C=(v1,v2,vij-1,vp,vp-1,vij,v1),且|C|=|P|-1+2=|P|+1(如图8所示)。注：由No3,No4可知：不管v1是vp否与相邻，总可将No1中得到的初级路变为初级圈。,44,离散数学,No5.最后，兹证明初级圈C必可被改造成一初级路P(新)，且有|P|(新)=|C|=|P|(老)+1。由于初级圈C=(u1,u2,up,u1)(重新命名)上只有p个结点且pn，故在圈C外应该还有图G的结点。这些结点中必至少有一个(不妨设是w)与C上的某个结点(不妨设是uk(1kp)相邻(否则，图G不连通)，延伸uk到w，,45,离散数学,并拆去uk的一个邻边(uk,uk+1)，这样就得到了一条更长的初级路：P=(uk-1,uk-2,u1,u2,up,up-1,uk,w)，且|P|(新)=|C|-1+1=|C|=|P|(老)+1(如图9所示)。将P的两端延伸到尽头，go to No2。注：Knig算法一定会在有限步停止。因为算法每进入循环一次，初级路P上结点的个数都会至少增一，而任何图G中结点的个数都是有限的；Knig算法的操作实际上是三步：(1)任走出一条初级路P，并延伸到尽头；(2)改初级路P为初级圈C；(3)改初级圈C为初级路P(新)，并延伸到尽头；路长至少增1。容易看出，定理2中的条件(*)对图中是否存在着H-路是充分的而不是必要的。,46,离散数学,如图10中所示的六边形图G，虽然其任意两个结点度数之和=45=6-1，不满足定理2中的条件(*)，但G中显然有H-路存在(实际上G是H-图,有H-圈)。定理3.(DKnig定理(充分性定理)设G(V,E)是简单无向图，且|V|=n。则 对任意一对结点u,vV，均有deg(u)+deg(v)n(*)G必是H-图。,47,离散数学,证.图G若满足条件(*)，则显然满足条件(*)，故定理2成立。因此图G中必存在着一条H-路P，不妨设：P=(v1,v2,vn)。现在我们来证图G中必含有H-圈：(1)若端点v1与端点vn相邻，我们将边(v1,vn)并入路P，则立即得到一H-圈：C=(v1,v2,vn,v1)；(2)若端点v1与端点vn不相邻，我们设与端点v1相邻的结点有k个，不妨设它们是vi1,vi2,vik，这些结点全都在路P上(因为路P是H-路，包含了图G中的所有结点)。这时，端点vn必至少与k个结点vi1-1,vi2-1,vik-1中的某一个相邻(是指结点vi1,vi2,vik在路P上的前一个结点)。假若不然，由于deg(v1)=k，则deg(vn)n-1-k(与端点vn相邻的结点全都在路P上(因为路P是H-路)。路P上共有n个结点，与结点vn相邻,48,离散数学,的结点，应该去掉结点vn自己以及已设不于它相邻的k个结点vi1-1,vi2-1,vik-1，不会超过n-1-k个结点)。于是，deg(v1)+deg(vn)k+(n-1-k)=n-1n 这与条件(*)矛盾。从而不妨设结点vn与结点vij-1(1jk)相邻，我们就立即得到一H-圈：C=(v1,v2,vij-1,vn,vn-1,vij,v1)(如图11所示)。,49,离散数学,根据(1)和(2)可知：图G中必含有一H-圈，故图G必是H-图。注：定理3证明中的(1)和(2)实际上是Knig算法的No3和No4步的翻版；Knig在定理3证明中的证明思想，据传来源于英国亚瑟王的谋士摩尔林，在解决著名的“圆桌会议”座位排名方案时所用的方法：相传亚瑟王有2n名骑士，每名骑士都有n-1名骑士是他的仇人。而大谋士摩尔林每当在亚瑟王召开“圆桌会议”时，却都能够预先排定那张享有盛名的圆桌的座位名次，以便使每名骑士都不与他的仇人相邻。定理2实际上是用了抻路法和蹦圈法；定理3实际上是用了蹦圈法。问题：你能给出摩尔林在解决“圆桌会议”座位排名方案时所采用的方法吗？并证明你的结论。,50,离散数学,推论1.(GADirac定理(1952)(充分性定理)设G(V,E)是简单无向图，且|V|=n。则 对任意结点vV，均有deg(v)(*)G必是H-图。证.图G满足条件(*)图G满足条件(*)图G必是H-图(根据定理3)。定理4.(充分性定理)设G(V,E)是简单无向图，且|V|=n，|E|=m。则 m(n-1)(n-2)+2(4*)G必是H-图。证.省略。,51,离散数学,提示：图G满足条件(4*)图G满足条件(*)(采用反证法)图G必是H-图(根据定理3)。注：定理4是第一个用边数作为考虑H-图充分条件依据的定理；而Knig定理等都是用结点的度数作为考虑H-图充分条件的依据；H-图充分条件无论是用结点的度数，还是用边数，都是说当图的连通性强到一定程度，就能保证图中必含有H-圈。图必是H-图。定义2.图的闭包(closure)一个简单无向图G=(V,E)(且|V|=n)的闭包是一个图Gc=(V,Ec)。其中：边集Ec的递归定义如下Ec:=E；Ec:=Ec(u,v)(u,v)Ec(u)+(v)n。例3.图12给出了几个图的闭包及其产生过程。,52,离散数学,53,离散数学,注：图的闭包未必都是完全图；例如，下图的闭包不是完全图。图的闭包是唯一存在的。,54,离散数学,定理5.(Bondy及Chvatal定理(1969)简单无向图G是H-图图G 的闭包Gc是H-图。证.)方向是显然的；)方向的证明省略。留给读者。提示：只需证明如下的一步性引理即可得证充分性：引理1.对于简单无向图G，且|V|=n。则图G是H-图图G是H-图。其中：G=(V,E),E=E(u0,v0)(这里：(u0,v0)EdegG(u0)+degG(v0)n)(证明方法参见定理3的证明)。注：定理5好似已经得到判定H-图的充要条件，其实不然。因为它只不过是将判定一个图G 是H-图转化为判定它的闭包图Gc是H-图；而判定闭包图Gc是H-图的充要条件仍未得到。,55,离散数学,有向图之Hamilton问题下面我们来讨论一类一定含有H-路的有向图竞赛图。定义3.竞赛图(race-graph)无向完全图的定向图称为竞赛图。注：竞赛图中任何两个结点间都有且仅有一条有向边。即(uV)(vV)(u,v)E(v,u)E)(u,v)E(v,u)E)。例4.图14给出了三个4个结点的竞赛图。,56,离散数学,定理6.(Redei(1934)设G=(V,E)是竞赛图，且|V|=n。则 竞赛图G中必存在着一条有向H-路。证.(采用翻边法)算法：从竞赛图G中求得一条H-路No1.从G中任意一点出发，走出一条有向初级路P，并将其两端延伸到尽头。设此有向初级路 P=(v1,v2,vp)，其路长|P|=p-1；No2.若p=n，则初级路P就是竞赛图G中的一条有向H-路。exit；No3.若pn，则竞赛图G中必存在着初级路P外的一个结点w，使得下式成立：(k)(1k p-1)(vk,w)E(w,vk+1)E)(如图15所示)。将结点w插入初级路P中，我们就得到一条新的更长的,57,离散数学,初级路：P=(v1,v2,vk,w,vk+1,vp),|P|=|P|-1+2=|P|+1，并将其两端延伸到尽头，仍将其记为P。go to No2。否则，若不存在这样的结点w，即(k)(1kp-1)(vk,w)E(w,vk+1)E)(k)(1kp-1)(vk,w)E(w,vk+1)E)(量词对偶)(k)(1kp-1)(vk,w)E(w,vk+1)E)(de Morgan律)(k)(1kp-1)(vk,w)E(w,vk+1)E)(1*)(联结词归约律)(k)(1kp-1)(w,vk+1)E(vk,w)E)(2*)(联结词归约律)于是，我们可得如下两个矛盾：,58,离散数学,(1)若(w,v1)E，则这与结点v1是路P的尽头矛盾！否则(w,v1)E(v1,w)E(根据竞赛图定义的注)(w,v2)E(根据(1*)式)(v2,w)E(根据竞赛图定义的注)(w,v3)E(根据(1*)式)(v3,w)E(根据竞赛图定义的注)(w,vp)E(根据(1*)式)(vp,w)E(根据竞赛图定义的注)这又与结点vp是路P的尽头矛盾！(2)若(vp,w)E，则这与结点vp是路P的尽头矛盾！否则(vp,w)E(w,vp)E(根据竞赛图定义的注)(vp-1,w)E(根据(2*)式)(w,vp-1)E(根据竞赛图定义的注)(vp-2,w)E(根据(2*)式)(w,vp-2)E(根据竞赛图定义的注),59,离散数学,(v1,w)E(根据(2*)式)(w,v1)E(根据竞赛图定义的注)这又与结点v1是路P的尽头矛盾！注：此算法一定会在有限步停止。因为算法每进入循环一次，初级路P上结点的个数都会至少增一，而任何图G中结点的个数都是有限的；竞赛图概念源于体育比赛。竞赛图用来表示单循环赛的战绩；其有向H-路用于决定比赛的名次排序(排序不是唯一的)；但是若加强到有向H-圈，则不能决定比赛名次，需要重赛。有向H-图一定是强连通的；但强连通图未必是有向H-图；有向图是有向H-图的判定定理也有许多，不过都很复杂，我们不再论述；有兴趣者，可参见清华马仲蕃等人合著之运筹学讲义(上)。,60,离散数学,货郎担问题(The Travelling Salesman Problem)货郎担问题又称为旅行商问题。一个货郎需穿过已知的若干村镇一次且仅一次，然后回到出发点，问应如何选择行动路线，使其总的行程最短？抽象成图论语言：就是在带权图G=(V,E,w)中寻求最优H-圈问题。这里图G的结点代表村镇；边代表两村镇间的(直达)路程；边上的权代表两村镇间路程的长度。寻求穿过每个村镇一次且仅一次，然后回到出发点的行动路线，就是要在图G中寻求穿过每个结点一次且仅一次的初级圈H-圈；使行动路线的总行程最短，就是要使H-圈的圈长(圈上边的总权和)达到最小(最优)。,61,离散数学,因此，带权图G=(V,E,w)的货郎担问题有解C0和w(C0)，当且仅当 1 C0是图G的一条H-圈(因此图G必须是H-图)；2 H-圈C0的圈长w(C0)=达到最小(最优)。其中：C0我们称为最优H-圈，或称C0是最优的；圈长w(C0)称为最优解。注：求解货郎担问题是很困难的，迄今为止，人们还未得到经典的完全求解算法。因为首先H-图的判定问题从前边知就没有得到彻底解决，而它又是解决货郎担问题的首要条件；其次，就是对有些肯定有H-圈的图(比如完全图)，求其最优解C0和w(C0)仍是很困难的。即是使用大型超高速电子计算机许多有名的货郎担问题也没能得到完全解决；现在人们在经典方法(即传统方法)上仅是得到了一些近似求解算法。下面我们给出两种近似算法。,62,离散数学,求解货郎担问题的近似算法：(一)近邻法No1.在G中任选一个结点vi1，从vi1出发，寻找距vi1最近的一个结点vi2，得到一条初级路C:=(vi1,vi2)，j:=2；No2.从vij出发，在Vvi1,vi2,vij中，寻找一个距vij最近的结点vij+1，并将C延至vij+1，即C:=C(vij,vij+1)，j:=j+1；No3.若j=n，则将C从vin延至vi1，得到一条H-圈 C:=(vi1,vi2,vin,vi1)，算法终止，exit；否则jn，go to No2。,63,离散数学,例5.在图16(a)所示的图G中寻求(近似)最优H-圈C。图G实际上是五个结点的完全图K5，故必有H-圈。选择起点v1。采用近邻法，其步骤如图16(b)-(f)所示，可以得到一条H-圈C=(v1,v3,v5,v4,v2,v1)，圈长w(C)=40。注：事实上，下面我们用交换法可求得一如图18(b)中所示的H-圈C，其圈长为w(C)=37。由此可知：在带权完全图中，近邻法仅提供了一个求最优H-圈的近似算法。,64,离散数学,65,离散数学,(二)交换法(Lin(1965);Held,Karp(1970,1971)交换法就是两两交换的启发式算法：No1.在图G中任找一条H-圈(可用近邻法)C:=(v1,v2,vi,vi+1,vj,vj+1,vn,v1)；,66,离散数学,No2.若 vi,vi+1,vj,vj+1V，1i i+1jj+1 n，使得w(vi,vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)，则令 C:=(v1,v2,vi,vj,vj-