文档介绍：第15章欧拉图与哈密顿图
离散数学
本章内容
欧拉图
哈密顿图
带权图与货郎担问题
欧拉图
历史背景--哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的回路。
欧拉图
通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图,具有欧拉通路而无欧拉回路的图称为半欧拉图。
说明 欧拉通路是图中经过所有边的简单的生成通路(经过所有顶点的通路称为生成通路)。
欧拉回路是经过所有边的简单的生成回路。
规定:平凡图是欧拉图
举例
欧拉图
半欧拉图
无欧拉通路
欧拉图
无欧拉通路
无欧拉通路
无向欧拉图的判定定理
无向图G是欧拉图当且仅当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中无奇度顶点。
充分性。由于G为非平凡的连通图可知,G中边数m≥1。
对m作归纳法。
(1)m=1时,由G的连通性及无奇度顶点可知,
G只能是一个环,因而G为欧拉图。
(2)设m≤k(k≥1)时结论成立,要证明m=k+1时,结论也成立。
由G的连通性及无奇度顶点可知,δ(G)≥2。
无论G是否为简单图,都可以用扩大路径法证明G中必含圈。
设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 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为欧拉图。
欧拉图的判定定理
G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。
无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度顶点。
证明必要性。设G是m条边的n阶无向图,因为G为半欧拉图,
因而G中存在欧拉通路(但不存在欧拉回路),
设Г=vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路,vi0≠vim。
v∈V(G),若v不在Г的端点出现,显然d(v)为偶数,
若v在端点出现过,则d(v)为奇数,
因为Г只有两个端点且不同,因而G中只有两个奇数顶点。
另外,G的连通性是显然的。
半欧拉图的判定定理