第11章-特殊图.ppt

离散数学
电子科技大学
计算机科学与工程学院
示范性软件学院
16 十月 2018
第11章特殊图
偶图
3
平面图
4
欧拉图
1
集合的表示方法
2
哈密顿图
2
内容提要
几个特殊图的概念:欧拉图、哈密顿图、偶图、平面图;
欧拉图、哈密顿图、偶图、平面图的判定;
偶图的匹配、图的着色;
欧拉图、哈密顿图、偶图、平面图的应用
本章学****要求
重点掌握
一般掌握
了解
1
1 各个特殊图相关基本概念
2 各个特殊图的性质
3 各个特殊图的判定方法
3
1 各个特殊图的应用
2 图的着色
2
1 哈密顿图、平面图的判断
2 证明方法
欧拉图
欧拉图的引入与定义
A
B
C
D
b5
b2
b1
b3
b4
b7
b6
B
C
A
D
b6
b2
b5
b7
b4
b1
b3

设G是无孤立结点的图,若存在一条通路(回路),经过图中每边一次且仅一次,则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。
规定:平凡图为欧拉图。
以上定义既适合无向图,又适合有向图。
欧拉通路和欧拉回路的特征
欧拉通路是经过图中所有边的通路中长度最短的通路,即为通过图中所有边的简单通路;
欧拉回路是经过图中所有边的回路中长度最短的回路,即为通过图中所有边的简单回路。
如果仅用边来描述,欧拉通路和欧拉回路就是图中所有边的一种全排列。

判断下面的6个图中,是否是欧拉图?是否存在欧拉通路?
v3
v1
v2
v4
(c)
v3
v1
v2
v4
(a)
v3
v1
v2
v4
(b)
v3
v1
v2
v4
(f)
v3
v1
v2
v4
(d)
v3
v1
v2
v4
(e)
欧拉图
欧拉图
不是欧拉图,但存在欧拉通路
不存在欧拉通路
不存在欧拉通路
不是欧拉图,但存在欧拉通路
欧拉图的判定
无向图G = <V, E>具有一条欧拉通路,当且仅当G是连通的,且仅有零个或两个奇度数结点。
分析只要找到了,就是存在的。我们具体找一条欧拉通路。对于结点的度数,我们在通路中去计算。
证明若G为平凡图,则定理显然成立。故我们下面讨论的均为非平凡图。
必要性:
设G具有一条欧拉通路L = ,则L经过G中的每条边,由于G中无孤立结点,因而L经过G的所有结点,所以G是连通的。
对欧拉通路L的任意非端点的结点,在L中每出现一次,都关联两条边和,而当重复出现时,它又关联另外的两条边,由于在通路L中边不可能重复出现,因而每出现一次都将使获得2度。若在L中重复出现p次,则deg( )= 2p。