第15章-欧拉图与哈密顿图(PPT文档).pptVIP

第十五章欧拉图与哈密顿图主要内容欧拉图哈密顿图带权图与货郎担问题欧拉图定义定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.无向欧拉图的判别法定理15.1无向图G是欧拉图当且仅当G连通且无奇度数顶点.证若G为平凡图,显然成立，无问题.下设G为n阶m条边的无向图.必要性因G是欧拉图，所以G中存在欧拉回路，设C为G中一条欧拉回路.(1)G连通显然.(2)?vi?V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点.由vi的任意性，结论为真.充分性对边数m做归纳法（第二数学归纳法）.(1)m=1时，G为一个环，则G为欧拉图.(2)设m?k（k?1）时结论为真，m=k+1时如下证明：无向欧拉图的判别法（a）制造满足归纳假设的若干个小欧拉图.由连通及无奇度数顶点可知，?(G)?2，用扩大路径法可得G中长度?3的圈C1.删除C1上所有的边（不破坏G中顶点度数的奇偶性）得G的生成子图G?，则G?无奇度顶点，设它有s（s?1）个连通分支G1?,G2?,…,Gs?,它们的边数均?k，且无奇度数顶点，由归纳法假设，因而它们都是小欧拉图.设C1?,C2?,…,Cs?是G1?,G2?,…,Gs?的欧拉回路.（b）将C1上被删除的边还原，从C1上某一顶点出发走出G的一条欧拉回路C.欧拉图的判别法定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证必要性简单.设G是m条边的n阶无向图，因G是半欧拉图，存在欧拉通回(但不存在欧拉回路)，设为?，(1)若v不是?的端点，设它在?中出现k次，每次获得2度，故d(v)=2k,(2)若v是?的端点，由于2个端点是不同的且不相邻，v作为端点只能出现一次，获得1度，它还可能作为非端点出现若干次，每次获得2度，故d(v)为奇数。充分性（利用定理15.1）设u,v为G中的两个奇度顶点，令G?=G?(u,v)则G?连通且无奇度顶点，由定理15.1知G?为欧拉图，因而存在欧拉回路C，令?=C?(u,v)，则?为G中欧拉通路.有向欧拉图的判别法定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.例题例15.1设G是欧拉图，但G不是平凡图，也不是一个环，则?(G)?2.证只需证明G中不可能有桥（如何证明？）Fleury算法算法：(1)任取v0?V(G)，令P0=v0.(2)设Pi=v0e1v1e2…eivi已经行遍，按下面方法从E(G)?{e1,e2,…,ei}中选取ei+1：(a)ei+1与vi相关联；(b)除非无别的边可供行遍，否则ei+1不应该为Gi=G?{e1,e2,…,ei}中的桥.(3)当(2)不能再进行时，算法停止.可以证明算法停止时所得简单通路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路.用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条.15.2哈密顿图历史背景：哈密顿周游世界问题与哈密顿图哈密顿图与半哈密顿图定义15.2(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上实例在上图中，(1),(2)是哈密顿图;(