离散数学--第十五章-欧拉图和哈密顿图.ppt

1第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图主要内容主要内容欧拉图欧拉图哈密顿图哈密顿图带权图与货郎担问题带权图与货郎担问题 215.1 欧拉图欧拉图历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图 3欧拉图定义欧拉图定义定义定义15.115.1 (1)(1)欧拉通路欧拉通路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的通路点的通路.(2)(2)欧拉回路欧拉回路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的回路点的回路.(3)(3)欧拉图欧拉图具有欧拉回路的图具有欧拉回路的图.(4)(4)半欧拉图半欧拉图具有欧拉通路而无欧拉回路的图具有欧拉通路而无欧拉回路的图.几点说明：几点说明：规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性环不影响图的欧拉性.4上图中，上图中，(1),(4)(1),(4)为欧拉图，为欧拉图，(2),(5)(2),(5)为半欧拉图，为半欧拉图，(3),(6)(3),(6)既不是欧拉图，也不是半欧拉图既不是欧拉图，也不是半欧拉图.在在(3),(6)(3),(6)中各至少加几条中各至少加几条边才能成为欧拉图？边才能成为欧拉图？欧拉图实例欧拉图实例 5无向欧拉图的判别法无向欧拉图的判别法定理定理15.1 15.1 无向图无向图G G是欧拉图当且仅当是欧拉图当且仅当G G连通且无奇度数顶点连通且无奇度数顶点.证证 :若若G G 为平凡图无问题为平凡图无问题.下设下设G G为为 n n 阶阶 m m 条边的无向图条边的无向图.必要性必要性 设设C C 为为G G 中一条欧拉回路中一条欧拉回路.(1)(1)G G 连通显然连通显然.(2)(2)v vi i V V(G G)，v vi i在在C C上每出现一次获上每出现一次获2 2度，所以度，所以v vi i为偶度顶为偶度顶点点.由由v vi i 的任意性，结论为真的任意性，结论为真.充分性充分性 对边数对边数m m做归纳法（第二数学归纳法）做归纳法（第二数学归纳法）.(1)(1)m m=1=1时，时，G G为一个环，则为一个环，则G G为欧拉图为欧拉图.(2)(2)设设m m k k（k k 1 1）时结论为真，）时结论为真，m m=k k+1+1时如下证明：时如下证明：6PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图，见示意图3.3.7欧拉图的判别法欧拉图的判别法定理定理15.2 15.2 无向图无向图G G是半欧拉图当且仅当是半欧拉图当且仅当G G 连通且恰连通且恰有两个奇度顶点有两个奇度顶点.证证:必要性简单必要性简单.充分性（利用定理充分性（利用定理15.115.1）设设u u,v v为为G G 中的两个奇度顶点，令中的两个奇度顶点，令 G G =G G(u u,v v)则则G G 连通且无奇度顶点，由定理连通且无奇度顶点，由定理15.115.1知知G G 为欧拉图，因而为欧拉图，因而存在欧拉回路存在欧拉回路C C，令，令 =C C(u u,v v)则则 为为 G G 中欧拉通路中欧拉通路.8有向欧拉图的判别法有向欧拉图的判别法定理定理15.3 15.3 有向图有向图D D是欧拉图当且仅当是欧拉图当且仅当D D是强连通的是强连通的且每个顶点的入度都等于出度且每个顶点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1.15.1.定理定理15.4 15.4 有向图有向图D D是半欧拉图当且仅当是半欧拉图当且仅当D D是单向连通的，且是单向连通的，且D D中恰有两个奇度顶点，其中一个的入度比出度大中恰有两个奇度顶点，其中一个的入度比出度大1 1，另一个，另一个的出度比入度大的出度比入度大1 1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1.15.1.定理定理15.5 15.5 G G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G G是连通的且为若干是连通的且为若干个边不重的圈之并个边不重的圈之并.可用归纳法证定理可用归纳法证定理15.5.15.5.9例题例题例例1 1 设设G G是欧拉图，但是欧拉图，但G G不是平凡图，也不是一个环，则不是平凡图，也不是一个环，则(G G)2.2.证证 只需证明只需证明G G中不可能有桥（如何证明？）中不可能有桥（如何证明？）上图中，上图中，(1),(2)(1),(2)两图都是欧拉图，均从两图都是欧拉图，均从A A点出发，如何一次成功地点出发，如何一次成功地走出一条欧拉回路来？走出一条欧拉回路来？(1)(2)(1)(2)10FleuryFleury算法算法算法：算法：(1)(1)任取任取v v0 0 V V(G G)，令，令P P0 0=v v0 0.(2)(2)设设P Pi i=v v0 0e e1 1v v1 1e e2 2e ei iv vi i 已经行遍，按下面方法从已经行遍，按下面方法从 E E(G G)e e1 1,e e2 2,e ei i 中选取中选取e ei i+1+1：(a)(a)e ei i+1+1与与v vi i 相关联；相关联；(b)(b)除非无别的边可供行遍，否则除非无别的边可供行遍，否则e ei i+1+1不应该为不应该为 G Gi i=G G e e1 1,e e2 2,e ei i 中的桥中的桥.(3)(3)当当 (2)(2)不能再进行时，算法停止不能再进行时，算法停止.可以证明算法停止时所得简单通路可以证明算法停止时所得简单通路 P Pm m =v v0 0e e1 1v v1 1e e2 2e em mv vm m(v vm m=v v0 0)为为G G 中一条欧拉回路中一条欧拉回路.用用FleuryFleury算法走出上一页图算法走出上一页图(1),(2)(1),(2)从从A A出发出发(其实从任何一点出发都可其实从任何一点出发都可以）的欧拉回路各一条以）的欧拉回路各一条.11英国数学家哈密顿于英国数学家哈密顿于18561856年提出周游世界的问题：年提出周游世界的问题：若要周游世界上的二十个名城，且城与城之间只若要周游世界上的二十个名城，且城与城之间只有一条路，则能否把每一个城走且只走一次，最有一条路，则能否把每一个城走且只走一次，最后返回到原地后返回到原地.该问题可以抽象为图论问题：用该问题可以抽象为图论问题：用2020个顶点分别表个顶点分别表示示2020个城市，两个顶点间的连线表示城市间的路，个城市，两个顶点间的连线表示城市间的路，要求找一条从某点出发，经过各个要求找一条从某点出发，经过各个顶点顶点一次且仅一次且仅一次，最后能否返回到出发点的路线一次，最后能否返回到出发点的路线?15.2 15.2 哈密顿图哈密顿图 12 (1)(2)13哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义15.215.2 (1)(1)哈密顿通路哈密顿通路经过图中所有顶点一次仅一次的通路经过图中所有顶点一次仅一次的通路.(2)(2)哈密顿回路哈密顿回路经过图中所有顶点一次仅一次的回路经过图中所有顶点一次仅一次的回路.(3)(3)哈密顿图哈密顿图具有哈密顿回路的图具有哈密顿回路的图.(4)(4)半哈密顿图半哈密顿图具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回路的图.几点说明：几点说明：1 1、平凡图是哈密顿图、平凡图是哈密顿图.2 2、哈密顿通路是初级通路，哈密顿回路是初级回路、哈密顿通路是初级通路，哈密顿回路是初级回路.3 3、环与平行边不影响哈密顿性、环与平行边不影响哈密顿性.4 4、哈密顿图的实质是能将图中的所有顶点排在同一个圈上、哈密顿图的实质是能将图中的所有顶点排在同一个圈上.14实例实例在上图中，在上图中，(1),(2)(1),(2)是哈密顿图是哈密顿图;(3)(3)是半哈密顿图是半哈密顿图;(4)(4)既不是哈密顿图，也不是半哈密顿图，为什么？既不是哈密顿图，也不是半哈密顿图，为什么？15无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理15.6 15.6 设无向图设无向图G G=是哈密顿图，对于任意是哈密顿图，对于任意V V1 1 V V且且V V1 1，均有，均有 p p(G G V V1 1)|V V1 1|证证 设设C C为为G G中一条哈密顿回路。中一条哈密顿回路。当当V1V1顶点在顶点在C C上均不相邻时，上均不相邻时，p p(C C V V1)1)达到最大值|V V1|1|，而当而当V1中顶点在C上有彼此相邻的情况时，均有p(CV1)|V1|，总之有 p p(C C V V1 1)|V V1 1|.|.而而C C是是G G的生成子图，所以有的生成子图，所以有 p p(G G V V1 1)p p(C C V V1 1)|V V1 1|说明：说明：本定理的条件只是哈密顿图的必要条件，但不是充分条件。本定理的条件只是哈密顿图的必要条件，但不是充分条件。可以验证彼得森图满足定理的条件，但它不是哈密顿图。可以验证彼得森图满足定理的条件，但它不是哈密顿图。16推论推论 设无向图设无向图G G=是半哈密顿图，对于任意的是半哈密顿图，对于任意的V V1 1 V V且且V V1 1均有均有 p p(G G V V1 1)|V V1 1|+1|+1证证:令令P P为为G G中起于中起于u u终于终于v v的哈密顿通路，令的哈密顿通路，令G G =G G(u u,v v)，则，则G G 为为哈密顿图，于是哈密顿图，于是 p p(GG V V1)1)|V V1|1|于是于是 p p(G G V V1 1)=)=p p(G G V V1 1(u u,v v)p p(GG V V1)+11)+1|V V1 1|+1|+1 17几点说明几点说明1 1、定理、定理15.615.6中的条件是哈密顿图的必要条件，但不是充分条件中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）（彼得松图）2 2、常利用定理、常利用定理15.615.6判断某些图不是哈密顿图判断某些图不是哈密顿图.例例2 2 设设G G为为n n阶无向连通简单图，若阶无向连通简单图，若G G中有割点或桥，则中有割点或桥，则G G不不 是哈密顿图是哈密顿图.证证 设设v v为割点，则为割点，则 p p(G G v v)2|2|v v|=1.|=1.K K2 2有桥，它显然不是哈密顿图有桥，它显然不是哈密顿图.除除K K2 2外，其他有桥的图（连通的）外，其他有桥的图（连通的）均有割点均有割点.其实，本例对非简单连通图也对其实，本例对非简单连通图也对.18无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件定理定理15.715.7 设设G G是是n n阶无向简单图，若对于任意不相邻的顶阶无向简单图，若对于任意不相邻的顶v vi i,v vj j，均有均有 d d(v vi i)+)+d d(v vj j)n n 1 1 ()则则G G 中存在哈密顿通路中存在哈密顿通路.证明：证明：(1)(1)由由()证证G G连通连通(2)(2)=v v1 1v v2 2v vl l 为为G G中极大路径中极大路径.若若l l=n n,证毕证毕.(3)(3)否则，证否则，证G G 中存在过中存在过 上所有顶点的圈上所有顶点的圈C C，由，由(1)(1)知知C C外顶外顶点存在与点存在与C C上某顶点相邻顶点，从而得比上某顶点相邻顶点，从而得比 更长的路径，重更长的路径，重复复(2)(3)(2)(3)，最后得，最后得G G中哈密顿通路中哈密顿通路.19证明证明证（着重关键步骤）证（着重关键步骤）(1)(1)由由()及简单图的性质，用反证法证明及简单图的性质，用反证法证明G G连通连通.(2)(2)=v v1 1v v2 2v vl l 为极大路径，为极大路径，l l n n,若若l l=n n（结束）（结束）.下面讨论下面讨论lnln的情况，即要证的情况，即要证G G中存在过中存在过 上所有顶上所有顶点的圈点的圈.若若(v v1 1,v vl l)在在G G中，则中，则(u u,v v)为为G G中圈中圈 否则，设否则，设v v1 1与与 上上 相相邻，则邻，则k k 2(2(否则由极大路径端点性质及否则由极大路径端点性质及()，会得到，会得到d d(v v1 1)+)+d d(v vl l)1+1+l l 22n n 1)1)，又又v vl l 至少与至少与 左边相邻顶点之一相邻左边相邻顶点之一相邻(写出理由写出理由)，设，设 与与v vl l相邻，见图中相邻，见图中(1)(1)，于是得，于是得G G中回路中回路C C(1)(1)中图去掉边中图去掉边()()20 证明证明图图(1)(1)图图(2)(2)(3)(3)由连通性，可得比由连通性，可得比 更长的路径（如图更长的路径（如图(2)(2)所示），所示），对它再扩大路径，重复对它再扩大路径，重复(2)(2)，最后得哈密顿通路，最后得哈密顿通路.21推论推论推论推论 设设G G为为n n(n n 3)3)阶无向简单图，若对于阶无向简单图，若对于G G中任意两中任意两个不相邻的顶点个不相邻的顶点v vi i,v vj j，均有，均有 d d(v vi i)+)+d d(v vj j)n n （）则则G G中存在哈密顿回路，从而中存在哈密顿回路，从而G G为哈密顿图为哈密顿图.定理定理15.815.8 设设u u,v v为为n n阶无向简单图阶无向简单图G G中两个不相邻的顶点，中两个不相邻的顶点，且且d d(u u)+)+d d(v v)n n，则，则G G为哈密顿图当且仅当为哈密顿图当且仅当G G(u u,v v)为哈密为哈密顿图顿图.22几点说明几点说明1 1、定理、定理15.715.7是半哈密顿图的充分条件，但不是必要条件是半哈密顿图的充分条件，但不是必要条件.长长度度为为n n 1 1（n n 4 4）的路径构成的图不满足（）的路径构成的图不满足（）条件，但它显）条件，但它显然是半哈密顿图然是半哈密顿图.2 2、定理、定理15.715.7的推论同样不是哈密顿图的必要条件，的推论同样不是哈密顿图的必要条件，G G为长为为长为n n的圈，不满足（的圈，不满足（）条件，但它当然是哈密顿图）条件，但它当然是哈密顿图.由定理由定理15.715.7的推论可知，的推论可知，K Kn n（n n 3 3）均为哈密顿图）均为哈密顿图.23n n（n n 2 2）阶竞赛图中存在哈密顿通路）阶竞赛图中存在哈密顿通路定理定理15.915.9 若若D D为为n n（n n 2 2）阶竞赛图，则）阶竞赛图，则D D中具有哈密顿通路中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图证明思路：注意，竞赛图的基图是无向完全图.对对n n（n n 2 2）做归纳做归纳.只需观察下面两个图只需观察下面两个图.无向哈密顿图的充分条件无向哈密顿图的充分条件 24判断某图是否为哈密顿图方法判断某图是否为哈密顿图方法 判断某图是否为哈密顿图至今还是一个难题判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.1.观察出哈密顿回路观察出哈密顿回路.例例3 3 下图下图(周游世界问题周游世界问题)是哈密顿图是哈密顿图易知易知a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t a a为图中的一条哈密顿回路为图中的一条哈密顿回路.注意，此图不满足定理注意，此图不满足定理15.715.7推论条件推论条件.252 2满足定理满足定理15.715.7推论的条件（推论的条件（）.例例4 4 完全图完全图K Kn n(n n 3)3)中任何两个顶点中任何两个顶点u u,v v，均有，均有 d d(u u)+)+d d(v v)=2()=2(n n 1)1)n n（n n 3 3），），所以所以K Kn n为哈密顿图为哈密顿图.判断某图是否为哈密顿图方法判断某图是否为哈密顿图方法 26设设G GG G，称，称 为为G G 的权，并记作的权，并记作W W(G G)，即即定义定义15.315.3 给定图给定图G G=，(G G为无向图或有向图为无向图或有向图)，设，设W W:E ER R (R(R为实数集为实数集)，对，对G G中任意边中任意边e e=(=(v vi i,v vj j)()(G G为有向图为有向图时，时，e e=)，设，设W W(e e)=)=w wijij，称实数，称实数w wij ij 为边为边e e上的上的权权，并将并将w wijij标注在边标注在边e e上，称上，称G G为为带权图带权图，此时常将带权图，此时常将带权图G G记作记作 .15.3 15.3 最短路问题与货郎担问题最短路问题与货郎担问题 27货郎担问题货郎担问题设设G G=为一个为一个n n阶完全带权图阶完全带权图K Kn n，各边的权非负，且，各边的权非负，且有的边的权可能为有的边的权可能为.求求G G中的一条最短的哈密顿回路，这就中的一条最短的哈密顿回路，这就是货郎担问题的数学模型是货郎担问题的数学模型.完全带权图完全带权图K Kn n（n n 3 3）中不同的哈密顿回路数）中不同的哈密顿回路数(1)(1)K Kn n中有中有(n n 1)!1)!条不同的哈密顿回路（定义意义下）条不同的哈密顿回路（定义意义下）(2)(2)完全带权图中有完全带权图中有(n n 1)!1)!条不同的哈密顿回路条不同的哈密顿回路(3)(3)用穷举法解货郎担问题算法的复杂度为用穷举法解货郎担问题算法的复杂度为(n n 1)1)！，当！，当n n较大时，计算量惊人地大较大时，计算量惊人地大 28 解解 C C1 1=a a b b c c d d a a,W W(C C1 1)=10)=10 C C2 2=a a b b d d c c a a,W W(C C2 2)=11)=11 C C3 3=a a c c b b d d a a,W W(C C3 3)=9)=9可见可见C C3 3(见图中见图中(2)(2)是最短的，其权为是最短的，其权为9.9.例例6 6 求图中求图中(1)(1)所示带权图所示带权图K K4 4中最短哈密顿回路中最短哈密顿回路.(1)(1)(2)(2)29第十五章第十五章 习题课习题课 主要内容主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题带权图、货郎担问题基本要求基本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图会用充分条件判断某些图是哈密顿图.要特别注意的是，不要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件能将必要条件当作充分条件，也不要将充分条件当必要条件.301.1.设设G G为为n n（n n 2 2）阶无向欧拉图，证明）阶无向欧拉图，证明G G中无桥中无桥(见例见例1 1思考题思考题)方法二：反证法方法二：反证法.利用欧拉图无奇度顶点及握手定理的推利用欧拉图无奇度顶点及握手定理的推论论.否则，设否则，设e e=(=(u u,v v)为为G G中桥，则中桥，则G G e e产生两个连通分支产生两个连通分支G G1 1,G G2 2，不妨设，不妨设u u在在G G1 1中，中，v v在在G G2 2中中.由于从由于从G G中删除中删除e e时，只改时，只改变变u u,v v 的度数的度数(各减各减1)1)，因而，因而G G1 1与与G G2 2中均只含一个奇度顶点，中均只含一个奇度顶点，这与握手定理推论矛盾这与握手定理推论矛盾.练习练习1 1方法一：直接证明法方法一：直接证明法.命题命题 (*)(*)：设：设C C为任意简单回路，为任意简单回路，e e为为C C上任意一条边，则上任意一条边，则C C e e连通连通.证证 设设C C为为G G中一条欧拉回路，任意的中一条欧拉回路，任意的e e E E(C C)，可知可知C C e e是是G G e e的子图，由的子图，由()知知 C C e e 连通，所以连通，所以e e不为桥不为桥.312.证明下图不是哈密顿图证明下图不是哈密顿图.(破坏必要条件破坏必要条件)方法一方法一.利用定理利用定理15.6，取取 V1=a,c,e,h,j,l，则，则 p(G V1)=7|V1|=6 练习练习 2方法二方法二.G为二部图，互补顶点子集为二部图，互补顶点子集 V1=a,c,e,h,j,l,V2=b,d,f,g,i,k,m，|V1|=6 7=|V2|.方法三方法三.利用可能出现在哈密顿回路上的边至少有利用可能出现在哈密顿回路上的边至少有n(n为阶数为阶数)条条这也是哈密顿图的一个必要条件，记为这也是哈密顿图的一个必要条件，记为().此图中，此图中，n=13，m=21.由于由于h,l,j 均为均为4度顶点，度顶点，a,c,e为为3度顶点，且它们关联边互不相同度顶点，且它们关联边互不相同.而在哈密顿回路上，每个而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有顶点准确地关联两条边，于是可能用的边至多有21(3 2+3 1)=12.这达不到（这达不到（）的要求）的要求.323 3某次国际会议某次国际会议8 8人参加，已知每人至少与其余人参加，已知每人至少与其余7 7人中的人中的4 4人人有共同语言，问服务员能否将他们安排在同一张圆桌就座，有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？使得每个人都与两边的人交谈？解解 图是描述事物之间关系的最好的手段之一图是描述事物之间关系的最好的手段之一.做无向图做无向图G G=,其中其中 V V=v v|v v为与会者为与会者，E E=(=(u u,v v)|)|u u,v v V V且且u u与与v v有共同语言，且有共同语言，且u u v v.易知易知G G为简单图且为简单图且 v v V V,d d(v v)4 4，于是，于是，u u,v v V V,有有d d(u u)+)+d d(v v)8 8，由定理，由定理15.7 15.7 的推论可知的推论可知G G为哈密顿图为哈密顿图.服务员在服务员在G G中找一条哈密顿回路中找一条哈密顿回路C C，按，按C C中相邻关系安排座中相邻关系安排座位即可位即可.练习练习 3 3由本题想到的：哈密顿回图的实质是能将图中所有的顶点由本题想到的：哈密顿回图的实质是能将图中所有的顶点排在同一个圈中排在同一个圈中.334.4.距离距离(公里公里)如图所示如图所示.他如何走行程最短？他如何走行程最短？练习练习 4 4最短的路为最短的路为ABCDAABCDA，距离为，距离为3636公里，其余两条各为多少？公里，其余两条各为多少？