《离散数学》课程教学课件（PPT讲稿）11 几种特殊的图

几种特殊的图

几种特殊的图

11.1欧拉图历史背景：哥尼斯堡七桥问题BBAD2

2 11.1 欧拉图 历史背景：哥尼斯堡七桥问题

欧拉图定义定义11.1图（无向图或有向图）中所有边恰好通过一次且经过所有顶点的通路称为欧拉通路图中所有边恰好通过一次且经过所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图具有欧拉通路而无欧拉回路的图称为半欧拉图。说明：规定平凡图为欧拉图环不影响图的欧拉性3

3 欧拉图定义 定义11.1 • 图(无向图或有向图)中所有边恰好通过一次且经过所有顶点的通 路称为欧拉通路. • 图中所有边恰好通过一次且经过所有顶点的回路称为欧拉回路． • 具有欧拉回路的图称为欧拉图. • 具有欧拉通路而无欧拉回路的图称为半欧拉图． 说明： 规定平凡图为欧拉图. 环不影响图的欧拉性

欧拉图实例e6eteteieese2e4e2e4ee4eseses不是半欧拉图欧拉图eieieiese2e2e4ese2e4e:eses不是欧拉图半欧拉图4

4 欧拉图实例 欧拉图 半欧拉图 不是 欧拉图 半欧拉图 不是

欧拉图的判别法定理11.1（1）无向图G是欧拉图当且仅当G是连通的且没有奇度项点：(2）无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点.5

5 欧拉图的判别法 定理11.1 (1) 无向图G是欧拉图当且仅当G是连通的且没有奇度顶点． (2) 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点．

实例一笔画出一条欧拉回路6

6 实例 一笔画出一条欧拉回路

实例一笔画出一条欧拉回路

7 实例 一笔画出一条欧拉回路

11.2哈密顿图历史背景：哈密顿周游世界问题(1)(2)8

8 11.2 哈密顿图 历史背景：哈密顿周游世界问题 (1) (2)

哈密顿图与半哈密顿图定义11.2经过图中所有项点一次且仅一次的通路称作哈密顿通路.经过图中所有顶点一次且仅一次的回路称作哈密顿回路·具有哈密顿回路的图称作哈密顿图·具有哈密顿通路且无哈密顿回路的图称作半哈密顿图规定：平凡图是哈密顿图：

9 哈密顿图与半哈密顿图 定义11.2 经过图中所有顶点一次且仅一次的通路称作哈密顿 通路. 经过图中所有顶点一次且仅一次的回路称作哈密顿回 路. 具有哈密顿回路的图称作哈密顿图. 具有哈密顿通路且无 哈密顿回路的图称作半哈密顿图. 规定: 平凡图是哈密顿图

哈密顿图与半哈密顿图例不是哈密顿图哈密顿图半哈密顿图10

10 哈密顿图与半哈密顿图 哈密顿图 哈密顿图 半哈密顿图 例 不是