getresource-15

《getresource-15》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十五章欧拉图与哈密顿图主要内容欧拉图哈密顿图带权图与货郎担问题115.1欧拉图历史背景：哥尼斯堡七桥问题与欧拉图2欧拉图定义定义15.1(1)欧拉通路——经过图中每条边一次且仅经过一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅经过一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图(N1)为欧拉图.欧拉通路是简单通路，欧拉回路是简单回路.环不影响图的欧拉性.3无向欧拉图的判别法定理15.1无向图G是欧拉图当且仅当G连通且

2、无奇度数顶点.证若G为平凡图显然成立.下设G为n阶m条边的无向图.必要性设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时如下证明：4定理证明由G的连通性及无奇度顶点可知，(G)≥2。类似例14.8，用扩大路径法可以证明G中存在长度大于或等于3(+1)的圈，设C为G中一个圈，删除C上的全部

3、边，得G的生成子图G。设G’有s个连通分支G1,G2,…,Gs，Gi与C的公共顶点为vji*,i=1,2,…,s，则每个连通分支至多有k条边，并且无奇度顶点。由归纳假设可知，G1,G2,…,Gs都是欧拉图，因而都存在欧拉回路Ci，i=1,2,…,s。最后将C还原（把删除的边重新加上），并从C上的某顶点vr开始行走，每遇到vji*，就行遍G'i中的欧拉回路C'i，i=1,2,…,s，最后回到vr，得回路vr…vj1*…vj1*…vj2*…vj2*…vjs*…vjs*…vr，此回路经过G中每条边一次

4、且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路（演示这条欧拉回路），故G为欧拉图。5无向半欧拉图的判别法定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.证必要性简单.充分性（利用定理15.1）设u,v为G中的两个奇度顶点，令G=G(u,v)则G连通且无奇度顶点，由定理15.1知G为欧拉图，因而存在欧拉回路C，令=C(u,v)则为G中欧拉通路.6有向欧拉图的判别法定理15.3有向图D是欧拉图当且仅当D是强连通图且每个顶点的入度都等于出度.证明类似于定理15.1定理15.4有向图D是

5、半欧拉图当且仅当D是单向连通图，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.证明类似于定理15.2定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.（这里G泛指图，包括有向和无向）7上图中，(1),(4)为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图.在(3),(6)中各至少加几条边才能成为欧拉图？欧拉图实例8例题例1设G是欧拉图，但G不是平凡图，也不是一个环，则(G)2.证只需证明G中不可能有桥

6、（如何证明？）上图中，(1),(2)两图都是欧拉图，均从A点出发，如何一次成功地走出一条欧拉回路来？(1)(2)9Fleury算法算法：能不走桥就不走桥。(1)任取v0V(G)，令P0=v0.(2)设Pi=v0e1v1e2…eivi是第i步找到的通路，按下面方法从E(G){e1,e2,…,ei}中选取ei+1：(a)ei+1与vi相关联；(b)ei+1最好不是Gi=G{e1,e2,…,ei}中的桥.(3)当(2)不能完成时，算法停止；否则，i=i+1，返回(2)可以证明算法停止时所得简单回路Pm=v0e1v

7、1e2…emvm(vm=v0)为G中一条欧拉回路。用Fleury算法走出上一页图(1),(2)从A出发（其实从任何一点出发都可以）的欧拉回路各一条。1015.2哈密顿图历史背景：哈密顿周游世界问题与哈密顿图(1)(2)11哈密顿图与半哈密顿图定义15.2(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：规定平凡图(N1)是哈密顿图.哈密顿通路是初级通路，哈

8、密顿回路是初级回路.环与平行边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上12实例在上图中，(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是哈密顿图，也不是半哈密顿图13无向哈密顿图的必要条件定理15.6设无向图G=是哈密顿图，对于任意V1V且V1，均有p(GV1)

9、V1

10、证设C为G中一条哈密顿回路(1)p(CV1)

11、