欧拉图与哈密顿图.ppt

《欧拉图与哈密顿图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第15章欧拉图与哈密顿图离散数学中国地质大学本科生课程本章内容15.1欧拉图15.2哈密顿图15.1欧拉图历史背景－－哥尼斯堡七桥问题欧拉图是一笔画出的边不重复的回路。通路:设G为无向标定图，G中顶点与边的交替序列Г＝vi0ej1vi1ej2vi2…ejivil称为vi0到vil的通路，其中，vi0，vil分别称为Г的始点与终点。回路:若vi0＝vil，则称通路为回路。简单通路:通路中，若Г的所有边各异;简单回路:简单通路中，若vi0＝vil；初级通路或路径：若Г的所有顶点(除vi0与vij可能相同外)各异，所有边也各异；初级回

2、路或圈：初级通路或路径中，若vi0＝vil，15.1欧拉图欧拉图欧拉通路:通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路;欧拉回路:通过图中所有边一次并且仅一次行遍所有顶点的回路。欧拉图:具有欧拉回路的图;半欧拉图:具有欧拉通路而无欧拉回路的图。举例欧拉图半欧拉图无欧拉通路欧拉图无欧拉通路无欧拉通路无向欧拉图的判定定理定理15.1无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。无向欧拉图的判定定理定理15.1无向图G是欧拉图当且

3、仅当G是连通图，且G中没有奇度顶点。证明若G是平凡图，结论显然成立。下面设G为非平凡图，设G是m条边的n阶无向图，并设G的顶点集V＝{v1,v2,…,vn}。必要性。因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上，因而vi,vj连通，所以G为连通图。又vi∈V，vi在C上每出现一次获得2度，若出现k次就获得2k度，即d(vi)＝2k，所以G中无奇度顶点。定理15.1的证明定理15.1无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。充分性。由于G为非平凡的连通图可知

4、，G中边数m≥1。对m作归纳法。(1)m＝1时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。(2)设m≤k(k≥1)时结论成立，要证明m＝k+1时，结论也成立。由G的连通性及无奇度顶点可知，δ(G)≥2。无论G是否为简单图，都可以用扩大路径法证明G中必含圈。定理15.1的证明设C为G中一个圈，删除C上的全部边，得G的生成子图G，设G有s个连通分支G1,G2,…,Gs，每个连通分支至多有k条边，且无奇度顶点，并且设Gi与C的公共顶点为v*ji，i＝1,2,…,s，由归纳假设可知，G1,G2,…,G

5、s都是欧拉图，因而都存在欧拉回路Ci，i＝1,2,…,s。最后将C还原（即将删除的边重新加上），并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍Gi中的欧拉回路Ci，i＝1,2,…,s，最后回到vr，得回路vr…v*j1…v*j1…v*j2…v*j2…v*js…v*js…vr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路，故G为欧拉图。定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。证明必要性。设G是m条边的n阶无向图，因为G为半欧拉图，因而G中存在欧拉通路(但

6、不存在欧拉回路)，设Г＝vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路，vi0≠vim。v∈V(G)，若v不在Г的端点出现，显然d(v)为偶数，若v在端点出现过，则d(v)为奇数，因为Г只有两个端点且不同，因而G中只有两个奇数顶点。另外，G的连通性是显然的。半欧拉图的判定定理定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。证明充分性。设G的两个奇度顶点分别为u0和v0，对G加新边（u0,v0），得G＝G∪(u0,v0)，则G是连通且无奇度顶点的图，由定理15.1可知，G为欧拉图，因

7、而存在欧拉回路C，而C＝C-(u0,v0)为G中一条欧拉通路，所以G为半欧拉图。半欧拉图的判定定理有向欧拉图的判定定理定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。举例有向欧拉图的判定定理定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。例15.1例15.1设G是非平凡的且非环的欧拉图，证明：(1)λ(G)≥2。(2)

8、对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。证明(1)由定理15.5可知，e∈E(G)，存在圈C，e在C中，因而p(G-e)＝p(G)，故e不是桥。由e的任意性λ(G)≥2，即G是2边-连通图。例15.1例15.1设G是非平凡的且非环的欧拉图，证