1、第十五章：欧拉图与哈密顿图,第一节：欧拉图 第二节：哈密顿图第三节：带权图与货郎担问题,2,15.1 欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图,欧拉图定义,定义15.1 (1) 欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路. (2) 欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路.(3) 欧拉图具有欧拉回路的图.(4) 半欧拉图具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.环不影响图的欧拉性.,3,4,上图中，(1) ,(4) 为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图. 在(3),(6)中各至少加几条边才能成为欧拉图？,欧拉图
2、实例,无向欧拉图的判别法,定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点.证明： 若G 为平凡图无问题. 下设G为 n 阶 m 条边的无向图.必要性 设C 为G 中一条欧拉回路.(1) G 连通显然.(2) viV(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）.(1) m=1时，G为一个环，则G为欧拉图.(2) 设mk（k1）时结论为真，m=k+1时证明,5,6,PLAY,从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图.,欧拉图的判别法,定理15.2 无向图G是半欧拉图当且仅当G 连通且
3、恰有两个奇度顶点.证 必要性简单. 充分性（利用定理15.1）设u,v为G 中的两个奇度顶点，令 G =G(u,v)则G 连通且无奇度顶点，由定理15.1知G 为欧拉图，因而存在欧拉回路C，令 =C(u,v)则 为 G 中欧拉通路.,7,有向欧拉图的判别法,定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G是非平凡的欧拉图当且
4、仅当G是连通的且为若干个边不重的圈之并. 可用归纳法证定理15.5.,8,例题,例1 设G是欧拉图，但G不是平凡图，也不是一个环，则(G)2.证 只需证明G中不可能有桥（如何证明？）,9,上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？,(1) (2),Fleury算法,算法：(1) 任取v0V(G)，令P0=v0. (2) 设Pi = v0e1v1e2eivi 已经行遍，按下面方法从 E(G)e1,e2,ei 中选取ei+1： (a) ei+1与vi 相关联； (b) 除非无别的边可供行遍，否则ei+1不应该为 Gi = Ge1,e2,ei 中的桥. (
5、3) 当 (2)不能再进行时，算法停止.可以证明算法停止时所得简单通路 Pm = v0e1v1e2emvm(vm=v0)为G 中一条欧拉回路. 用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条.,10,第十五章 欧拉图与哈密顿图,第一节：欧拉图 第二节：哈密顿图第三节：带权图与货郎担问题,15.2 哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,12,(1) (2),哈密顿图与半哈密顿图,定义15.2 (1) 哈密顿通路经过图中所有顶点一次仅一次的通路.(2) 哈密顿回路经过图中所有顶点一次仅一次的回路.(3) 哈密顿图具有哈密顿回路的图.(4
6、) 半哈密顿图具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上,13,实例,在上图中，(1),(2) 是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图,14,无向哈密顿图的必要条件,定理15.6 设无向图G=是哈密顿图，对于任意V1V且V1，均有 p(GV1) |V1|,15,推论 设无向图G=是半哈密顿图，对于任意的V1V且V1，均有p(GV1) |V1|+1,几点说明,定理15.6中的条件是哈密顿图的必要条件，但不是充分条件（彼得松图）由
7、定理15.6立刻可知，Kr,s 当s r+2时不是哈密顿图. 易知Kr,r（r2）时都是哈密顿图，Kr,r+1都是半哈密顿图. 常利用定理15.6判断某些图不是哈密顿图.例2 设G为n阶无向连通简单图，若G中有割点或桥，则G不 是哈密顿图.证 设v为割点，则 p(Gv) 2|v|=1. K2有桥，它显然不是哈密顿图. 除K2外，其他有桥的图（连通的）均有割点.其实，本例对非简单连通图也对.,16,无向哈密顿图的充分条件,定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有 d(vi)+d(vj) n1 ()则G 中存在哈密顿通路.,17,推论 设G为n (n3) 阶无向简
8、单图，若对于G中任意两个不相邻的顶点vi,vj，均有 d(vi)+d(vj) n （）则G中存在哈密顿回路，从而G为哈密顿图.,定理15.8 设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图.,无向哈密顿图的充分条件,n（n2）阶竞赛图中存在哈密顿通路定理15.9 若D为n（n2）阶竞赛图，则D中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图. 对n（n2）做归纳. 只需观察下面两个图.,18,判断某图是否为哈密顿图方法,判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.
9、观察出哈密顿回路.例3 下图(周游世界问题)是哈密顿图易知a b c d e f g h i j k l m n p q r s t a为图中的一条哈密顿回路.注意，此图不满足定理15.7推论条件.,19,判断某图是否为哈密顿图方法,2满足定理15.7推论的条件（）.例4 完全图Kn (n3) 中任何两个顶点u,v，均有 d(u)+d(v) = 2(n1) n（n3），所以Kn为哈密顿图. 3破坏定理15.6的条件的图不是哈密顿图.,20,21,例5 证明下图不是哈密顿图. (破坏必要条件),方法一. 利用定理15.6，取 V1 = a, c, e, h, j, l，则 p(GV1) = 7
10、|V1| = 6,练习 2,方法二. G为二部图，互补顶点子集 V1 = a, c, e, h, j, l, V2 = b, d, f, g, i, k, m， |V1| = 6 7 = |V2|.,22,例6 某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？,解 图是描述事物之间关系的最好的手段之一. 做无向图G=, 其中 V=v| v为与会者， E=(u,v) | u,vV且u与v有共同语言，且u v. 易知G为简单图且vV, d(v)4，于是，u,vV, 有d(u)+d(v) 8，由定理15.7 的推论可
11、知G为哈密顿图. 服务员在G中找一条哈密顿回路C，按C中相邻关系安排座位即可.,练习 3,由本题想到的：哈密顿回路的实质是能将图中所有的顶点排在同一个圈中.,第十五章 欧拉图与哈密顿图,第一节：欧拉图 第二节：哈密顿图第三节：带权图与货郎担问题,24,设GG，称 为G的长度，并记作W(G)，即,定义15.3 给定图G = ，(G为无向图或有向图)，设W:ER (R为实数集)，对G中任意边e = (vi,vj) (G为有向图时，e = )，设W(e) = wij，称实数wij 为边e上的权，并将wij标注在边e上，称G为带权图，此时常将带权图G记作 .,15.3 最短路问题与货郎担问题,最短路径
12、,25,从某源点到其余各顶点之间的最短路径求下面赋权图中顶点u0到其余顶点的最短路注:最短路径并不一定是经过边数最少的路径事实：最短路是一条路，且最短路的任一节也是最短路,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ，
13、 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个
14、，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,Dijkstra算法,1) 置 ，对 ， ， 且 .,2) 对每个 ，用,代替 ，计算 ，并
15、把达到这个最小值的,一个顶点记为 ，置,3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).,货郎担问题,设G=为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为. 求G中的一条最短的哈密顿回路，这就是货郎担问题的数学模型. 完全带权图Kn（n3）中不同的哈密顿回路数(1) 完全带权图中有(n1)! 条不同的哈密顿回路(2) 用穷举法解货郎担问题算法的复杂度为(n1)！，当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.,39,例6 求图中(1) 所示带权图K4中最短哈密顿回路.,(1) (2),作业,12111421,
