文档介绍：第十五章
欧拉图与哈密顿图
欧拉图
、欧拉回路、欧拉图、半欧拉图的定义
通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图,具有欧拉通路而无
欧拉回路的图称为半欧拉图。
从定义不难看出,欧拉通路是图中经
过所有边的简单的生成通路(经过所有顶
点的通路称为生成通路),类似地,欧拉
回路是经过所有边的简单的生成回路。
在这里做个规定,即平凡图N1是欧拉图。
,e1e2e3e4e5为
(1)中的欧拉回路,所以(1)图为欧拉
图。e1e2e3e4e5为(2)中的一条欧拉通路,
但图中不存在欧拉回路,所以(2)为半欧
拉图。(3)中既没有欧拉回路,也没有欧
拉通路,所以(3)不是欧拉图,也不是半
欧拉图。e1e2e3e4为(4)图中的欧拉回路,
所以(4)图为欧拉图。(5),(6)图中
都既没有欧拉回路,也没有欧拉通路
二、判别定理
无向图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时,由G的连通性及无奇度顶
点可知,G只能是一个环,因而G为欧拉图。
(2)设m≤k(k≥1)时结论成立,要证明
m=K+1时,结论也成立。由G的连通性及
无奇度顶点可知,δ(G)≥
,用扩大路径法可以证明G中存在
长度大于或等于3的圈,设C为G中一个
圈,删除C上的全部边,得G的生成子
图G’,设G’有s个连通分支G’1,G’2,…,
G‘s,每个连通分支至多有k条边,且无
奇度顶点,并且设G‘i与C的公共顶点为
,i=1,2,…,s,由归纳假设可知,G'1,
G'2,…,G's都是欧拉图,因而都存在欧拉
回路C‘i,i=1,2,…,(即将
删除的边重新加上),并从C上的某顶点
vr开始行遍,每遇到,就行遍G’ i中的
欧拉回路C’ i,i=1,2,…,s,最后回到vr,得
回路
vr…………………vr,
此回路经过G中每条边一次且仅一次并行
遍G中所有顶点,因而它是G中的欧拉回
路,故G为欧拉图。
,
个无向图中,只有(1)中无奇度顶点,
因而(1)是欧拉图,而(2)、(3)都
有奇度顶点,因而它们都不是欧拉图。
: 无向图G是半欧拉图当且仅
当G是连通的,且G中恰有两个奇度顶点。
证: 必要性设G是m条边的n阶无向图,
因为G为半欧拉图,因而G中存在欧拉通路