离散数学第十三章几种特殊的图 主要内容 ●欧拉图 ●哈密顿图 ●二部图与匹配 ●平面图 着色
1 第十三章 几种特殊的图 主要内容 ⚫ 欧拉图 ⚫ 哈密顿图 ⚫ 二部图与匹配 ⚫ 平面图 ⚫ 着色
离散数学 13.1欧拉图 历史背景:哥尼斯堡七桥问题 B
2 13.1 欧拉图 历史背景：哥尼斯堡七桥问题
离散数学 欧拉图定义 定义131图(无向图或有向图)中所有边恰好通过一次且经过 所有顶点的通路称为欧拉通路.图中所有边恰好通过一次且 经过所有顶点的回路称为欧拉回路.具有欧拉回路的图称为 欧拉图.具有欧拉通路而无欧拉回路的图称为半欧拉图 说明: 规定平凡图为欧拉图 环不影响图的欧拉性
3 欧拉图定义 定义13.1 图(无向图或有向图)中所有边恰好通过一次且经过 所有顶点的通路称为欧拉通路. 图中所有边恰好通过一次且 经过所有顶点的回路称为欧拉回路．具有欧拉回路的图称为 欧拉图. 具有欧拉通路而无欧拉回路的图称为半欧拉图． 说明： 规定平凡图为欧拉图. 环不影响图的欧拉性
离散数学 欧拉图实例 el el e e e3 欧拉图 半欧拉图 不是 e e e4 欧拉图 半欧拉图 不是
4 欧拉图实例 欧拉图 半欧拉图 不是 欧拉图 半欧拉图 不是
离散数学 欧拉图的判别法 定理131(1)无向图G是欧拉图当且仅当G是连通的且没有奇 度顶点 (2)无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点 (3)有向图D是欧拉图当且仅当D是强连通的且每个顶点的入 度等于出度 (4)有向图D是半欧拉图当且仅当D是单向连通的且恰有两个 奇度顶点,其中一个顶点的入度比出度大1,另一个顶点出度 比入度大1,其余顶点的入度等于出度 例1设G是非平凡的欧拉图,则G)≥2 证只需证明G的任意一条边e都不是桥设C是一条欧拉回路, e在C上,因而G-e仍是连通的,故e不是桥
5 欧拉图的判别法 定理13.1 (1) 无向图G是欧拉图当且仅当G是连通的且没有奇 度顶点． (2) 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点． (3) 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入 度等于出度． (4) 有向图D是半欧拉图当且仅当D是单向连通的且恰有两个 奇度顶点, 其中一个顶点的入度比出度大1, 另一个顶点出度 比入度大1, 其余顶点的入度等于出度． 例1 设G是非平凡的欧拉图，则(G)2. 证 只需证明G的任意一条边e都不是桥. 设C是一条欧拉回路, e在C上，因而G−e仍是连通的，故e不是桥．
离散数学 Fleury?算法 算法: (1)任取v∈G),令P=,=0 (2)设P1=We1v12…,eP, 如果E(O)-{e1,e2…,e}中没有与vn关联的边,则计算结束; 否则按下面方法从E(G)-{t1e2,}中选取e (a)eH1与v关联; (b)除非无别的边可供选择,否则en不应为G-{t1e2y,} 中的桥 设e#1=(v#1),把e种1v加入P (3)令计1,返回(2)
6 Fleury算法 算法： (1) 任取v0V(G), 令P0=v0 , i=0. (2) 设Pi = v0e1v1e2…eivi ， 如果E(G)-{e1 ,e2 ,…,ei }中没有与vi关联的边, 则计算结束; 否则按下面方法从E(G)−{e1 ,e2 ,…,ei }中选取ei+1： (a) ei+1与vi 关联； (b) 除非无别的边可供选择, 否则ei+1不应为 G−{e1 ,e2 ,…,ei } 中的桥. 设ei+1=(vi ,vi+1), 把ei+1vi+1加入Pi . (3) 令i=i+1, 返回(2)
离散数学 实例 笔画出一条欧拉回路
7 实例 一笔画出一条欧拉回路
离散数学 实例 笔画出一条欧拉回路
8 实例 一笔画出一条欧拉回路
离散数学 132哈密顿图 历史背景:哈密顿周游世界问题 (2)
9 13.2 哈密顿图 历史背景：哈密顿周游世界问题 (1) (2)
离散数学哈密顿图与半哈密顿图 定义132经过图中所有顶点一次且仅一次的通路称作哈密顿 通路经过图中所有顶点一次且仅一次的回路称作哈密顿回 路.具有哈密顿回路的图称作哈密顿图.具有哈密顿通路且无 哈密顿回路的图称作半哈密顿图. 规定:平凡图是哈密顿图. 例 哈密顿图哈密顿图半哈密顿图不是 10
10 哈密顿图与半哈密顿图 定义13.2 经过图中所有顶点一次且仅一次的通路称作哈密顿 通路. 经过图中所有顶点一次且仅一次的回路称作哈密顿回 路. 具有哈密顿回路的图称作哈密顿图. 具有哈密顿通路且无 哈密顿回路的图称作半哈密顿图. 规定: 平凡图是哈密顿图. 哈密顿图 哈密顿图 半哈密顿图 例 不是
