1、1第十一章 几种特殊的图主要内容l 欧拉图l 哈密顿图l 二部图与匹配l 平面图l 着色211.1 欧拉图历史背景：哥尼斯堡七桥问题3欧拉图定义定义 11.1 图 (无向 图 或有向 图 )中所有 边 恰好通 过 一次且 经过所有 顶 点的通路称 为 欧拉通路 . 图 中所有 边 恰好通 过 一次且经过 所有 顶 点的回路称 为 欧拉回路 具有欧拉回路的 图 称为欧拉 图 . 具有欧拉通路而无欧拉回路的 图 称 为 半欧拉 图 说明：规定平凡图为欧拉图 .环不影响图的欧拉性 .4欧拉图实例欧拉图 不是半欧拉图欧拉图 不是半欧拉图5欧拉图的判别法定理 11.1 (1) 无向 图 G是欧拉 图 当
2、且 仅 当 G是 连 通的且没有奇度 顶 点(2) 无向 图 G是半欧拉 图 当且 仅 当 G是 连 通的且恰有两个奇度顶 点(3) 有向 图 D是欧拉 图 当且 仅 当 D是 强 连 通的且每个 顶 点的入度等于出度(4) 有向 图 D是半欧拉 图 当且 仅 当 D是 单 向 连 通的且恰有两个奇度 顶 点 , 其中一个 顶 点的入度比出度大 1, 另一个 顶 点出度比入度大 1, 其余 顶 点的入度等于出度例 1 设 G是非平凡的欧拉图，则 (G)2.证 只需 证 明 G的任意一条 边 e都不是 桥 . 设 C是一条欧拉回路, e在 C上，因而 Ge仍是 连 通的，故 e不是 桥 6Fle
3、ury算法算法：(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不应为 Ge1,e2, ei 中的桥 .设 ei+1=(vi,vi+1), 把 ei+1vi+1加入 Pi. (3) 令 i=i+1, 返回 (2).7实例一笔画出一条欧拉回路8实例一笔画出一条欧拉回路911.2 哈密顿图历史背景：哈密顿周游世界问题 (1) (2) 10哈密顿图与半哈密顿图定义 11.2 经过图中所有顶点一次且仅一次的通路称作 哈密顿通路 . 经过图中所有顶点一次且仅一次的回路称作 哈密顿回路 . 具有哈密顿回路的图称作 哈密顿图 . 具有哈密顿通路且无哈密顿回路的图称作 半哈密顿图 .规定 : 平凡图是哈密顿图 .哈密顿图 半哈密顿图哈密顿图例不是
