第15章欧拉图与哈密顿图

1、1第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图主要内容主要内容l 欧拉图欧拉图l 哈密顿图哈密顿图l 带权图与货郎担问题带权图与货郎担问题215.1 欧拉图欧拉图历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图要求边不重复地一笔画出整个图要求边不重复地一笔画出整个图3欧拉图定义欧拉图定义定义定义15.1 (1) 欧拉通路欧拉通路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的通路点的通路. (2) 欧拉回欧拉回路路经过图中每条边一次且仅一次行遍所有顶经过图中每条边一次且仅一次行遍所有顶点的回路点的回路.(3) 欧拉图欧拉图具有欧拉回路的图具

2、有欧拉回路的图.(4) 半欧拉图半欧拉图具有欧拉通路而无欧拉回路的图具有欧拉通路而无欧拉回路的图.几点说明：几点说明：规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性环不影响图的欧拉性.4上图中，上图中，(1) ,(4) 为欧拉图，为欧拉图，(2),(5)为半欧拉图，为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图既不是欧拉图，也不是半欧拉图. 在在(3),(6)中各至少加几条边才能成为欧拉图？中各至少加几条边才能成为欧拉图？ 欧拉图实例欧拉图实例5无向欧拉图的判别法无向欧拉图的

3、判别法定理定理15.1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G连通且无奇度数顶点连通且无奇度数顶点.证证 若若G 为平凡图为平凡图,显然成立，无问题显然成立，无问题. 下设下设G为为 n 阶阶 m 条边的无向图条边的无向图.必要性必要性 因因G是欧拉图，所以是欧拉图，所以G中存在欧拉回路，设中存在欧拉回路，设C 为为G 中中一条欧拉回路一条欧拉回路.(1) G 连通显然连通显然.(2) vi V(G)，vi在在C上每出现一次获上每出现一次获2度，所以度，所以vi为偶度顶点为偶度顶点. 由由vi 的任意性，结论为真的任意性，结论为真. 充分性充分性 对边数对边数m做归纳法（第二数学归纳

4、法）做归纳法（第二数学归纳法）.(1) m=1时，时，G为一个环，则为一个环，则G为欧拉图为欧拉图.(2) 设设m k（k 1）时结论为真，）时结论为真，m=k+1时如下证明：时如下证明：6无向欧拉图的判别法无向欧拉图的判别法（a）制造满足归纳假设的若干个小欧拉图）制造满足归纳假设的若干个小欧拉图. 由连通及无奇度数顶点可知，由连通及无奇度数顶点可知， (G) 2， 用扩大路径法可得用扩大路径法可得G中长度中长度 3的圈的圈C1. 删除删除C1上所有的边（不破坏上所有的边（不破坏G中顶点度数的奇偶性）得中顶点度数的奇偶性）得G的的生成子图生成子图G ，则，则G 无奇度顶点，无奇度顶点， 设它有

5、设它有s（s 1）个连通分支）个连通分支G1 , G2 , , Gs , 它们的边数均它们的边数均 k，且无且无奇度数顶点奇度数顶点，由归纳法假设，因而它们都是小欧由归纳法假设，因而它们都是小欧拉图拉图. 设设C1 , C2 , , Cs 是是G1 , G2 , , Gs 的欧拉回路的欧拉回路. （b）将）将C1上被删除的边还原，从上被删除的边还原，从C1上某一顶点出发走出上某一顶点出发走出G的的一条欧拉回路一条欧拉回路C.例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题4个奇度顶点个奇度顶点, 不存在不存在 欧拉通路欧拉通路, 更不存在欧拉回路更不存在欧拉回路。7PLAY从以上证明不难看出：欧拉图是

6、若干个边不重的圈之从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图并，见示意图3. 8欧拉图的判别法欧拉图的判别法定理定理15.2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G 连通且恰有两个奇度连通且恰有两个奇度顶点顶点.证证 必要性简单必要性简单. 设设G是是m条边的条边的n阶无向图，因阶无向图，因G是半欧拉图，是半欧拉图，存在欧拉通回存在欧拉通回(但不存在欧拉回路但不存在欧拉回路)， 设为设为 ， (1) 若若v不是不是 的端点，设它在的端点，设它在 中出现中出现k次，每次获得次，每次获得2度，故度，故d(v)=2k, (2)若若v是是 的端点，的端点， 由于由于2个端

7、点是不同的且不相个端点是不同的且不相邻，邻，v作为端点只能出现一次，获得作为端点只能出现一次，获得1度，它还可能作为非端度，它还可能作为非端点出现若干次，每次获得点出现若干次，每次获得2度，故度，故d(v)为奇数。为奇数。充分性（利用定理充分性（利用定理15.1）设设u,v为为G 中的两个奇度顶点，令中的两个奇度顶点，令 G =G (u,v)则则G 连通且无奇度顶点，由定理连通且无奇度顶点，由定理15.1知知G 为欧拉图，因而为欧拉图，因而存在欧拉回路存在欧拉回路C，令，令 =C (u,v)，则，则 为为 G 中欧拉通路中欧拉通路.9有向欧拉图的判别法有向欧拉图的判别法定理定理15.3 有向图

8、有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连通的且每个顶是强连通的且每个顶点的入度都等于出度点的入度都等于出度.本定理的证明类似于定理本定理的证明类似于定理15.1. 定理定理15.4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单向连通的，且是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大中恰有两个奇度顶点，其中一个的入度比出度大1，另一个，另一个的出度比入度大的出度比入度大1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度. 本定理的证明类似于定理本定理的证明类似于定理15.1. 定理定理15.5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连通

9、的且为若干是连通的且为若干个边不重的圈之并个边不重的圈之并. 可用归纳法证定理可用归纳法证定理15.5. 10例题例题例例15.1 设设G是欧拉图，但是欧拉图，但G不是平凡图，也不是一个环，则不是平凡图，也不是一个环，则 (G) 2.证证 只需证明只需证明G中不可能有桥（如何证明？）中不可能有桥（如何证明？）上图中，上图中，(1),(2)两两图都是欧拉图，均从图都是欧拉图，均从A点出发，如何点出发，如何一次成功地走出一条欧拉回路来？一次成功地走出一条欧拉回路来？ (1) (2)11Fleury算法算法算法：算法：(1) 任取任取v0 V(G)，令，令P0=v0. (2) 设设Pi = v0e1

10、v1e2eivi 已经行遍，按下面方法从已经行遍，按下面方法从 E(G) e1,e2,ei 中选取中选取ei+1： (a) ei+1与与vi 相关联；相关联； (b) 除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1不应该为不应该为 Gi = G e1,e2,ei 中的桥中的桥. (3) 当当 (2)不能再进行时，算法停止不能再进行时，算法停止.可以证明算法停止时所得简单通路可以证明算法停止时所得简单通路 Pm = v0e1v1e2emvm(vm=v0)为为G 中一条欧拉回路中一条欧拉回路. 用用Fleury算法走出上一页图算法走出上一页图(1),(2)从从A出发（其实从任何一点出

11、发（其实从任何一点出发都可以）的欧拉回路各一条出发都可以）的欧拉回路各一条. 1215.2 哈密顿图哈密顿图历史背景：哈密顿周游世界问题与哈密顿图历史背景：哈密顿周游世界问题与哈密顿图 (1) (2) 每个顶点是一个城市每个顶点是一个城市, , 有有20个城市个城市, , 要求从一个城市出要求从一个城市出发发, , 恰好经过每一个城市一次恰好经过每一个城市一次, , 回到出发点回到出发点. .13哈密顿图与半哈密顿图哈密顿图与半哈密顿图定义定义15.2 (1) 哈密顿通路哈密顿通路经过图中所有顶点一次仅一次的通路经过图中所有顶点一次仅一次的通路.(2) 哈密顿回路哈密顿回路经过图中所有顶点一次

12、仅一次的回路经过图中所有顶点一次仅一次的回路.(3) 哈密顿图哈密顿图具有哈密顿回路的图具有哈密顿回路的图.(4) 半哈密顿图半哈密顿图具有哈密顿通路且无哈密顿回路的图具有哈密顿通路且无哈密顿回路的图.几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上哈密顿图的实质是能将图中的所有顶点排在同一个圈上14实例实例在上图中，在上图中，(1),(2) 是哈密顿图是哈密顿图;(3)是半哈密顿图是半哈密顿图;(4)既不

13、是哈密顿图，也不是半哈密顿图，为什么？既不是哈密顿图，也不是半哈密顿图，为什么？15无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件定理定理15.6 设无向图设无向图G=是哈密顿图，对于任意是哈密顿图，对于任意V1 V且且V1，均有，均有 p(G V1) |V1|证证 设设C为为G中一条哈密顿回路，当中一条哈密顿回路，当V1中顶点在中顶点在C上均不相邻时，上均不相邻时， p(C V1)达到最大值达到最大值|V1|，而当，而当V1中顶点在中顶点在C上有彼此相邻的上有彼此相邻的情况时，均有情况时，均有 p(C V1)|V1|，从而，从而(1) p(C V1) |V1| 而而C是是G的生成子图，

14、所以的生成子图，所以(2) p(G V1) p(C V1) |V1| （因为（因为C G）定理定理15.6中的条件是哈密顿图的必要条件，但不是充分条件中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）（彼得松图）16无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件推论推论 设无向图设无向图G=是半哈密顿图，对于任意的是半哈密顿图，对于任意的V1 V且且V1均有均有 p(G V1) |V1|+1证证 令令 uv为为G中哈密顿通路，令中哈密顿通路，令G = G (u,v)，则，则G 为哈为哈密顿图密顿图. 于是于是 p(G V1) = p(G V1 (u,v) |V1|+117几点说明几

15、点说明l 由定理由定理15.6立刻可知，立刻可知，Kr,s当当s r+1时不是哈密顿图时不是哈密顿图. 易知易知Kr,r（r 2）时都是哈密顿图，）时都是哈密顿图，Kr,r+1都是半哈密顿图都是半哈密顿图. l 常利用定理常利用定理15.6判断某些图判断某些图不是不是哈密顿图哈密顿图.例例2 设设G为为n阶无向连通简单图，若阶无向连通简单图，若G中有割点或桥，则中有割点或桥，则G不不 是哈密顿图是哈密顿图.证证 设设v为割点，则为割点，则 p(G v) 2|v|=1. K2有桥，它显然不是哈密顿图有桥，它显然不是哈密顿图. 除除K2外，其他有桥的图外，其他有桥的图（连通的）均有割点（连通的）均

16、有割点.其实，本例对非简单连通图也对其实，本例对非简单连通图也对.18例15.3 ，为了应用定理定理15.6及推论，及推论，问顶点V1是如何得到的呢？一般地：设二部图G=,|V1|V2|,且|V1|2, |V2|2,由定理15.6及其他推论可以得出下面结论：(1)若G是哈密顿图哈密顿图,则则 |V1|=|V2|,(2)若若G半哈密顿图半哈密顿图,则则 |V2|=|V1|+1(3)若|V2| |V1|+2,则G不是哈密顿图哈密顿图,也不是半哈密顿图也不是半哈密顿图19无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件定理定理15.7 设设G是是n阶无向简单图，若对于任意不相邻的顶点阶无向简单图

17、，若对于任意不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj) n 1 ( )则则G 中存在哈密顿通路中存在哈密顿通路. 证明线索：证明线索：(1) 由由( )证证G连通连通(2) = v1v2vl 为为G中极大路径中极大路径. 若若l = n, 证毕证毕. (3) 否则，证否则，证G 中存在过中存在过 上所有顶点的圈上所有顶点的圈C，由，由(1) 知知C外顶外顶点存在与点存在与C上某顶点相邻顶点，从而得比上某顶点相邻顶点，从而得比 更长的路径，重更长的路径，重复复(2) (3) ，最后得，最后得G中哈密顿通路中哈密顿通路. 20证明证明证（着重关键步骤）证（着重关键步骤）(1) 由由

18、( )及简单图的性质，用反证法证明及简单图的性质，用反证法证明G连通连通.(2) = v1v2vl 为极大路径，为极大路径，l n, 若若l = n（结束）（结束）.下面讨论下面讨论ln的情况，即要证的情况，即要证G中存在过中存在过 上所有顶点的圈上所有顶点的圈. 若若(v1,vl)在在G中，则中，则(u,v)为为G中圈中圈 否则，设否则，设v1与与 上上 相邻，则相邻，则k 2 (否则由否则由极大路径端点性质及极大路径端点性质及( )，会得到，会得到d(v1)+d(vl) 1+l 2n 1)，又又vl 至少与至少与 左边相邻顶点之一相邻左边相邻顶点之一相邻(写出理由写出理由)，设设 与与vl

19、相邻，见图中相邻，见图中(1) ，于是得，于是得G中回路中回路C (1)中图去中图去掉边掉边( ) ) kiiivvv,.,32kiiivvvv,.,2121rivrriivv,121 证明证明图图(1)图图(2)(3) 由连通性，可得比由连通性，可得比 更长的路径（如图更长的路径（如图(2) 所示），所示），对它再扩大路径，重复对它再扩大路径，重复(2) ，最后得哈密顿通路，最后得哈密顿通路.22推论推论推论推论 设设G为为n (n 3) 阶无向简单图，若对于阶无向简单图，若对于G中任意两个中任意两个不相邻的顶点不相邻的顶点vi,vj，均有，均有 d(vi)+d(vj) n （）则则G中存在

20、哈密顿回路，从而中存在哈密顿回路，从而G为哈密顿图为哈密顿图.证明线索：由定理证明线索：由定理15.7得得 = v1v2vn 为为G中哈密顿通路中哈密顿通路. 若若(v1,vn) E(G)，得证，得证. 否则利用（否则利用（）证明存在过）证明存在过v1, v2, vn的圈的圈(此圈即为哈密顿回路此圈即为哈密顿回路). 定理定理15.8 设设u,v为为n阶无向简单图阶无向简单图G中两个不相邻的顶点，中两个不相邻的顶点，且且d(u)+d(v) n，则，则G为哈密顿图当且仅当为哈密顿图当且仅当G (u,v)为哈密顿为哈密顿图图. 23几点说明几点说明定理定理15.7是半哈密顿图的充分条件，但不是必要

21、条件是半哈密顿图的充分条件，但不是必要条件. 长度长度为为n 1（n 4）的路径构成的图不满足（）的路径构成的图不满足（ ）条件，但它显）条件，但它显然是半哈密顿图然是半哈密顿图.定理定理15.7的推论同样不是哈密顿图的必要条件，的推论同样不是哈密顿图的必要条件，G为长为为长为n的的圈，不满足（圈，不满足（）条件，但它当然是哈密顿图）条件，但它当然是哈密顿图.由定理由定理15.7的推论可知，的推论可知，Kn（n 3）均为哈密顿图）均为哈密顿图.24应用实例应用实例例例15.4 某次国际会议某次国际会议8人参加，人参加，他们来自不同的他们来自不同的国家。已知他们中任何两人无共同语言的人，国家。已

22、知他们中任何两人无共同语言的人，与其余有与其余有共同语言共同语言的人数之和大于或等于的人数之和大于或等于8，试证明：能将这试证明：能将这8 人人排在同一张圆桌就座，使排在同一张圆桌就座，使得每个人都能与两边的人交谈？得每个人都能与两边的人交谈？解解 作无向图作无向图G=, 其中其中V=v|v为与会者为与会者， E=(u,v) | u,v V, u与与v有共同语言有共同语言, 且且u v. G为为8阶无向简单图阶无向简单图. d(v)为与为与v有共同语言的人数有共同语言的人数. 根据已知条件根据已知条件, u,v V, 有有d(u)+d(v) 8. 由定理由定理15.7的推论的推论 ，可知，可知

23、G中存在哈密顿回路中存在哈密顿回路. 服务员在服务员在G中找一条哈密顿回路中找一条哈密顿回路C，按，按C中相邻关中相邻关系安排座位即可系安排座位即可. 25竞赛图竞赛图竞赛图竞赛图: 任意两个顶点之间恰好有一条有向边任意两个顶点之间恰好有一条有向边.在循环赛中在循环赛中, n个参赛队中的任个参赛队中的任意两个队比赛一次意两个队比赛一次, 假设没有假设没有平局平局, 用有向图描述比赛结果用有向图描述比赛结果: 顶点表示参赛队顶点表示参赛队, A到到B有一条有一条边当且仅当边当且仅当A队胜队胜B队队. 25ABCD26竞赛图竞赛图(续续)定理定理 在在n(n2)阶有向图阶有向图D中中, 如果所有有

24、向边如果所有有向边均用无向边代替均用无向边代替, 所得无向图中含生成子所得无向图中含生成子图图Kn, 则有向图则有向图D中存在哈密顿通路中存在哈密顿通路.根据定理根据定理, 竞赛图中一定有哈密顿通路竞赛图中一定有哈密顿通路, 当然当然也可能有哈密顿回路也可能有哈密顿回路. 当没有哈密顿回路时当没有哈密顿回路时, 通常只有一条哈密顿通常只有一条哈密顿通路通路, 这条通路给出参赛队的惟一名次这条通路给出参赛队的惟一名次. 例如例如, DABC是一条哈密顿通路是一条哈密顿通路, 它没有哈密它没有哈密顿回路顿回路, 比赛结果是比赛结果是D第一第一, A第二第二, B第三第三, C第四第四.26ABCD

25、27n（n 2）阶竞赛图中存在哈密顿通路）阶竞赛图中存在哈密顿通路定理定理15.9 若若D为为n（n 2）阶竞赛图，则）阶竞赛图，则D中具有哈密顿通路中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图证明思路：注意，竞赛图的基图是无向完全图. 对对n（n 2）做归纳做归纳. 只需观察下面两个图只需观察下面两个图. 无向哈密顿图的充分条件无向哈密顿图的充分条件28证明：证明：设设D为为n阶阶竞赛图竞赛图，当，当n=2时，时，D的基图的基图为为K2，结论成立。，结论成立。 设设n=k时成立，现设时成立，现设n=k+1，设，设V(D)=v1,v2 ,vk,vk+1.令令D1=D-vk+1，易知

26、易知D1为为k阶阶竞赛图竞赛图，由，由归纳归纳法假设，法假设，D1存在存在哈密顿通路哈密顿通路 1 = v1v2vk , 下面证明可以扩到下面证明可以扩到 1中去。中去。若存在若存在vr(1 r k)使得使得E(D),i=1,2,.,r-1.且且E(D)，如图如图(a)所示，则所示，则 = v1v2vk+1 vrvk ,为为D中中哈密顿通路哈密顿通路.否则，对任意否则，对任意i1,2, . ,k，均有，均有E(D)，如图，如图(b)所示，所示，则则 = v1v2vkvk+1 ,为为D中中哈密顿通路哈密顿通路.无向哈密顿图的充分条件无向哈密顿图的充分条件29判断某图是否为哈密顿图方法判断某图是否

27、为哈密顿图方法 判断某图是否为哈密顿图至今还是一个判断某图是否为哈密顿图至今还是一个NP难题难题.总结判断某图是哈密顿图或不是总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法哈密顿图的某些可行的方法.1. 观察出哈密顿回路观察出哈密顿回路.例例15.5 下图下图(周游世界问题周游世界问题)是哈密顿图是哈密顿图易知易知a b c d e f g h i j k l m n p q r s t a为图中的一条哈密顿回路为图中的一条哈密顿回路.注意，此图不满足定理注意，此图不满足定理15.7推论条件推论条件.302满足定理满足定理15.7推论的条件（推论的条件（）.例例4 完全图完全图Kn (n

28、 3) 中任何两个顶点中任何两个顶点u,v，均有，均有 d(u)+d(v) = 2(n 1) n（n 3），），所以所以Kn为哈密顿图为哈密顿图. 3破坏定理破坏定理15.6的条件的图不是哈密顿图的条件的图不是哈密顿图.例例5 在四分之一国际象棋盘（在四分之一国际象棋盘（4 4方格组成）上跳马无解方格组成）上跳马无解.在在8 8国际象棋盘上跳马有解国际象棋盘上跳马有解. 判断某图是否为哈密顿图方法判断某图是否为哈密顿图方法 31令令V1=a, b, c, d, 则则 p(G V1) = 6 4，由定理，由定理15.6可知图可知图中无哈密顿回路中无哈密顿回路.在在8 8国际象棋盘上跳马有解，试试

29、看国际象棋盘上跳马有解，试试看. 解解 每个方格看作一个顶点每个方格看作一个顶点, 2个顶点之间有边当且仅当马可以个顶点之间有边当且仅当马可以从一个方格跳到另一个方格从一个方格跳到另一个方格, 得到得到16阶图阶图G, 如左图红边所示如左图红边所示. 32设设GG，称称 为为G 的权，并记作的权，并记作W(G )，即，即 ) ()(GEeeW ) ()() (GEeewGW定义定义15.3 给定图给定图G = ，(G为无向图或有向图为无向图或有向图)，设，设W:ER (R为实数集为实数集)，对，对G中任意边中任意边e = (vi,vj) (G为有向图为有向图时，时，e = )，设，设W(e)

30、= wij，称实数，称实数wij 为边为边e上的上的权权，并将，并将wij标注在边标注在边e上，称上，称G为为带权图带权图，此时常将带权图，此时常将带权图G记作记作 . 15.3 最短路问题最短路问题与货郎担问题与货郎担问题例例 P1=v0v1v3v5, W(P1)=10, P2=v0v1v4v5, W(P2)=12, P3=v0v2v4v5, P(P3)=11.33最短路问题最短路问题带权图带权图G=, 其中其中w:ER. e E, w(e)称作称作e的的权权.为非负实数，为非负实数， e=(vi,vj), 记记w(e)=wij . 若若vi,vj不相邻不相邻, 记记wij = .又规定又规

31、定 wii =0；通路通路L的的权权: L的所有边的权之和的所有边的权之和, 记作记作w(L).u和和v之间的之间的最短路径最短路径: u和和v之间权最小的通路之间权最小的通路.从从u到到v长度最短的路径称为从长度最短的路径称为从u到到v的的最短路径最短路径，称其长度为，称其长度为从从u到到v的距离，记作的距离，记作d(u,v).约定约定d(u,u)=0;当当u和和v不连通（不连通（u不可达不可达v）d(u,v)=+ ;最短路径最短路径问题：问题：给定给定带权图带权图G=及顶点及顶点u和和v,其中每一其中每一条边条边e的权为非负实数，求从的权为非负实数，求从u到到v的的 最短路径最短路径。不难

32、看出，如果不难看出，如果uvi1vi2,vikv是从是从u到到v的最短路径，则对每的最短路径，则对每一个一个t（kt1），），uvi1vi2,vit是从是从u到到vit的最短路径的最短路径.3434标号法标号法(E.W.Dijkstra, 1959)设带权图设带权图G=, 其中其中 e E, w(e) 0.设设V=v1,v2,vn, 求求v1到其余各顶点的最短路径到其余各顶点的最短路径1. 令令 l10, p1 , lj+ , pj , j=2,3,n, P=v1, T=V-v1, k1, t1. / 表示空表示空2. 对所有的对所有的vj T且且(vk,vj) E 令令lminlj, lk+

33、wkj, 若若l=lk+wkj, 则令则令ljl, pjvk.3. 求求li=minlj| vj T. 令令PP vi, TT-vi, ki.4. 令令tt+1, 若若tn, 则转则转2.35Dijkstra标号法实例标号法实例例例 求求v0到到v5的最短路径的最短路径 t v0 v1 v2 v3 v4 v5 1 (0, )* (+ , ) (+ , ) (+ , ) (+ , ) (+ , ) 2 (1,v0)* (4,v0) (+ , ) (+ , ) (+ , ) 3 (3,v1)* (8,v1) (6,v1) (+ , ) 4 (8,v1) (4,v2)* (+ , ) 5 (7,v4

34、)* (10,v4) 6 (9,v3)*v0到到v5的最短路径的最短路径: v0v1v2v4v3v5 , d(v0,v5)=936Dijkstra标号法实例标号法实例P304t v1 v2v3 v4 v5 v6 v71 (0, v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1) (+ , v1)2 (3, v1) (7, v1)(5, v1) (+ , v1) (+ , v1) (+ , v1)3 (5, v2) (5, v1) (9, v2) (+ , v1) (+ , v1)4(5, v1) (8, v3) (+ , v1) (+ , v1)5

35、 (8, v3) (7, v4) (13, v4)6 (8, v3) (9, v6)7 (9, v6)例：例： 求求v1到其余各点的最短到其余各点的最短路径和距离。路径和距离。v1到到v7的最短路径的最短路径: v1v4v6v7 , d(v1,v7)=9v1到到v5的最短路径的最短路径: v1v2v3v5 , d(v1,v5)=8*v1(0,v1)v2(3,v1)v3(5,v2)v4(5,v1)v5(8,v3)v7(9,v6)v6(7,v4)37货郎担问题货郎担问题 货郎担问题货郎担问题(旅行商问题旅行商问题): 有有n n个城市个城市, ,给定给定城市城市之间道路之间道路的长度（长度可以为的

36、长度（长度可以为 ，对应这两个，对应这两个城市城市之间无交通线），之间无交通线），一个一个旅行商从某个旅行商从某个城市出发城市出发, , 要要经过每个城市一次经过每个城市一次且仅且仅一次一次, , 最后最后回到出发回到出发的的城市城市, ,问如何走才能使他走的路线问如何走才能使他走的路线最短？最短？设设G=为一个为一个n阶完全带权图阶完全带权图Kn，各边的权非负，且，各边的权非负，且有的边的权可能为有的边的权可能为 . 求求G中的一条最短的哈密顿回路，这就中的一条最短的哈密顿回路，这就是货郎担问题的数学模型是货郎担问题的数学模型. 完全带权图完全带权图Kn（n 3）中不同的哈密顿回路数）中不同

37、的哈密顿回路数(1) Kn中有中有(n 1)! 条不同的哈密顿回路（定义意义下）条不同的哈密顿回路（定义意义下）(2) 完全带权图中有完全带权图中有(n 1)! 条不同的哈密顿回路条不同的哈密顿回路(3) 用穷举法解货郎担问题算法的复杂度为用穷举法解货郎担问题算法的复杂度为(n 1)！，当！，当n较大较大时，计算量惊人地大时，计算量惊人地大38 解解 C1= a b c d a, W(C1)=10 C2= a b d c a, W(C2)=11 C3= a c b d a, W(C3)=9可见可见C3 (见图中见图中(2) 是最短的，其权为是最短的，其权为9. 例例6 求图中求图中(1) 所示

38、带权图所示带权图K4中最短哈密顿回路中最短哈密顿回路. (1) (2) 39第十五章第十五章 习题课习题课 主要内容主要内容l 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法l 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图l 带权图、货郎担问题带权图、货郎担问题基本要求基本要求l 深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解欧拉图、半欧拉图的定义及判别定理l 深刻理解哈密顿图、半哈密顿图的定义深刻理解哈密顿图、半哈密顿图的定义. l 会用哈密顿图的必要条件判断某些图不是哈密顿图会用哈密顿图的必要条件判

39、断某些图不是哈密顿图. l 会用充分条件判断某些图是哈密顿图会用充分条件判断某些图是哈密顿图. 要特别注意的是，要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要不能将必要条件当作充分条件，也不要将充分条件当必要条件条件. 401. 设设G为为n（n 2）阶无向欧拉图，证明）阶无向欧拉图，证明G中无桥中无桥(见例见例1思考题思考题)方法二：反证法方法二：反证法. 利用欧拉图无奇度顶点及握手定理的推论利用欧拉图无奇度顶点及握手定理的推论. 否则，设否则，设e=(u,v)为为G中桥，则中桥，则G e产生两个连通分支产生两个连通分支G1, G2，不妨设不妨设u在在G1中，中，v在在G2中中. 由于从由于从G中删除中删除e时，只改变时，只改变u,v 的度数的度数(