第十五章欧拉图与哈密顿图15.1欧拉图欧拉图定义上图中，(1),(4)为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图？无向欧拉图的判别法无向欧拉图的判别法欧拉图的判别法有向欧拉图的判别法例题Fleury算法15.2哈密顿图哈密顿图与半哈密顿图实例无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件几点说明无向哈密顿图的一个充分条件证明推论几点说明应用实例竞赛图竞赛图(续)n（n2）阶竞赛图中存在哈密顿通路定理15.9若D为n（n2）阶竞赛图，则D中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图.对n（n2）做归纳.只需观察下面两个图.证明：设D为n阶竞赛图，当n=2时，D的基图为K2，结论成立。设n=k时成立，现设n=k+1，设V(D)={v1,v2,…,vk,vk+1}.令D1=D-vk+1，易知D1为k阶竞赛图，由归纳法假设，D1存在哈密顿通路1=v'1v'2…v'k,下面证明可以扩到1中去。若存在v'r(1rk)使得<v'r,v'k+1>E(D),i=1,2,...,r-1.且<v'k+1,v'r>E(D)，如图(a)所示，则=v'1v'2…vk+1v'r…v'k,为D中哈密顿通路.否则，对任意i{1,2,...,k}，均有<v'i,vk+1>E(D)，如图(b)所示，则=v'1v'2…v'kv'k+1,为D中哈密顿通路.判断某图是否为哈密顿图方法2．满足定理15.7推论的条件（）.例4完全图Kn(n3)中任何两个顶点u,v，均有d(u)+d(v)=2(n1)n（n3），所以Kn为哈密顿图.3．破坏定理15.6的条件的图不是哈密顿图.例5在四分之一国际象棋盘（44方格组成）上跳马无解.在88国际象棋盘上跳马有解.令V1={a,b,c,d},则p(GV1)=6>4，由定理15.6可知图中无哈密顿回路.在88国际象棋盘上跳马有解，试试看.设GG，称为G的权，并记作W(G)，即最短路问题34Dijkstra标号法实例Dijkstra标号法实例P304货郎担问题第十五章习题课1.设G为n（n2）阶无向欧拉图，证明G中无桥(见例1思考题)2.证明下图不是哈密顿图.(破坏必要条件)3．某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都与两边的人交谈？4.距离(公里)如图所示.他如何走行程最短？