资源描述：
《欧拉图与哈密顿图1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十五章欧拉图与哈密顿图第1节欧拉图第2节哈密顿图第3节带权图与货郎担问题第1节欧拉图一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义二、欧拉图的判别定理三、欧拉图的简单应用问题的提出ABCD哥尼斯堡七桥问题ABCD哥尼斯堡镇多重图模型定义15.1通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路;通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路；具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图.一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义从定义不难看出:欧拉通
2、路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），欧拉回路是经过所有边的简单的生成回路。在这里做个规定:平凡图是欧拉图.图15.1例1下列各图中是否有欧拉回路、欧位通路？解：e1e2e3e4e5为(1)中的欧拉回路，所以(1)图为欧拉图.e1e2e3e4e5为(2)中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以(2)为半欧拉图。（3）中既没有欧拉回路也没有欧拉通路(为什么？)，所以(3)不是欧拉图，也不是半欧拉图。e1e2e3e4为(4)图中的欧拉回路，所以(4)图为欧拉图.(5),(6)
3、图中都既没有欧拉回路，也没有欧拉通路（为什么？）定理15.1无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。二、欧拉图的判别定理证明要点：当图G具有欧拉回路时，图G中每个顶点在欧拉回路中出现一次就获得2度，所以每个顶点的度数是偶数.反过来当连通图G中的顶点度数都是偶数时，则①G中必有简单回路.②G中包含边数最多的简单回路就是欧拉回路.必要性.因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，vi,vj∈V，vi,vj都在C上，因而vi,vj连通，所以G为连通图.又vi∈V，vi在C上每出现一次获
4、得2度，若出现k次就获得2k度，即d(vi)=2k.所以G中无奇度顶点.证若G是平凡图，结论显然成立.下面设G为非平凡图，设G是m条边的n阶无向图,并设G的顶点集V={v1,v2,…,vn}.由于G为非平凡的连通图可知，G中边数m≥1.对m作归纳法。(1)m=1时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。(2)设m≤k(k≥1)时结论成立，要证明m=k+1时，结论也成立。充分性.由G的连通性及无奇度顶点可知，δ(G)≥2.类似于例14.8，用扩大路径法可以证明G中存在长度大于或等于3的圈，设C为G
5、中一个圈，删除C上的全部边，得G的生成子图G'，设G'有s个连通分支每个连通分支至多有k条边，且无奇度顶点，并且设G'i与C的公共顶点为，i=1,2,…,s.由归纳假设可知，都是欧拉图，因而都存在欧拉回路C'i，i=1,2,…,s.由定理15.1立刻可知，图15.1中（1）是欧拉图，而（2）、（3）都有奇度顶点，因而它们都不是欧拉图.最后将C还原(即将删除的边重新加上),并从C上的某顶点vr开始行遍，每遇到，就行遍G'i中的欧拉回路C'i，i=1,2,…,s，最后回到vr，得回路此回路经过G中每条边一次且仅一次并行遍G
6、中所有顶点，因而它是G中的欧拉回路,故G为欧拉图.(演示)定理15.2无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点.证:必要性.设G是m条边的n阶无向图，因为G为半欧拉图，因而G中存在欧拉通路（但不存在欧拉回路），设为G中一条欧拉通路，若v不在Г的端点出现，显然d(v)为偶数，若v在端点出现过，则d(v)为奇数，因为Г只有两个端点且不同，因而G中只有两个奇数顶点.另外，G的连通性是显然的.设G的两个奇度顶点分别为u0和v0，对G加新边（u0,v0），得G'=G∪(u0,v0)，则G'是连通且无奇度顶点的
7、图，由定理15.1可知，G'为欧拉图，因而存在欧拉回路C'，而C=C'－(u0,v0)为G中一条欧拉通路，所以G为半欧拉图.由定理15.2立即可知，图15.1中（2）是半欧拉图，但（3）不是半欧拉图。充分性.定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.由定理15.3和15.4立即可知，图15.1中所示3
8、个有向图中只有（4）是欧拉图，没有半欧拉图.图15.1图15.3由定理15.1立即可知，图15.3(1)图为欧拉图.本图既可以看成圈之并(为清晰起见，将4个圈画在(2)中)，也可看成圈与圈之并(两个圈画在(3)中)。将(1)分解成若干个边不重的圈的并不是(1)图特有的性质，任何欧拉图都有这个性质。定理15.5G是非平凡的欧拉图当且
