PDF《欧拉图与汉密尔顿图》

欧拉图与汉密尔顿图

1 ? 通路与回路 ? 无向图的连通性 ? 连通度 ? 2-连通图 ? 有向图的连通性 ? 无向图的定向

2 回顾 ? 欧拉通路/回路 ? 欧拉图的充要条件 ? 构造欧拉回路的Fleury算法 ? 哈密尔顿通路/回路 ? 哈密尔顿图的必要和充分条件 ? 哈密尔顿图的应用 提要 ? 邮递员从邮局出发,走过辖区内每条街道至少一次, 再回邮局,如何选择最短路线? ? n个城市间均有道路,但距离不等,旅行商从某地 出发,走过其它n-1个城市,且只经过一次,最后 回到原地,如何选择最短路线?

4 回顾 ? 问题的抽象: ? 用顶点表示对象- 地块 ? 用边表示对象之间的关系- 有桥相连 ? 原问题等价于: 右边的图中是否存在包含每条边 一次且恰好一次的回路? C D A B A C B D K?nigsberg七桥问题(回顾) 一笔划 问题 ? 欧拉通路和欧拉回路 ? 定义:包含图(无向图或有向图)中每条边的简单通 路称为欧拉通路.

注意:欧拉通路是简单通路(边不重复),但顶点可重复 ? 定义:包含图中每条边的简单回路称为欧拉回路. ? 如果图G中含欧拉回路,则G称为欧拉图.如果图G中 有欧拉通路,但没有欧拉回路,则G称为半欧拉图. //备注:通常假设G是连通的. ? 连通图G是欧拉图 当且仅当 G中每个顶点的度数均 为偶数. ? 证明: ?设C是G中的欧拉回路,则?v?VG, d(v)必等于v在C上出现 数的2倍(起点与终点看成出现一次). ?可以证明: (1)G中所有的边可以分为若干边不相交的初级回路. (2)这些回路可以串成一个欧拉回路. 欧拉图的充要条件 ? (1) 若图G中任一顶点均为偶度点,则G中所有的边包含在若 干边不相交的简单回路中. ? 证明:对G的边数m施归纳法. ? 当m=1, G是环,结论成立. ? 对于k?1,假设当m?k时结论成立. ? 考虑m=k+1的情况:注意?G?2, G中必含简单回路,记为 C,令G'

=G-EC, 设G'

中含s个连通分支,显然,每个 连通分支内各点均为偶数(包括0),且边数不大于k.则根 据归纳假设,每个非平凡的连通分支中所有边含于没有 公共边的简单回路中,注意各连通分支以及C两两均无公 共边,于是,结论成立. 欧拉图的充要条件 欧拉图的充要条件 ? (2) 若连通图G中所有的边包含在若干边不相交的简单回路中, 则G中含欧拉回路. ? 证明:对G中简单回路个数d施归纳法.当d=1时显然. ? 假设d?k(k?1)时结论成立.考虑d=k+1. ? 按某种方式对k+1个简单回路排序,令G'

=G-E(Ck+1),设G'

中含s个连通分支,则每个非平凡分支所有的边包含在相互 没有公共边的简单回路中,且回路个数不大于k.由归纳假 设,每个非平凡连通分支Gi均为欧拉图,设其欧拉回路是 Ci'

.因G连通,故Ck+1与诸Ci'

都有公共点. ? G中的欧拉回路构造如下:从Ck+1上任一点(设为v0)出发遍历 Ck+1上的边,每当遇到一个尚未遍历的Ci'

与Ck+1的交点(设为 vi'

), 则转而遍历Ci'

上的边,回到vi'

继续沿Ck+1进行. 关于欧拉图的等价命题 ? 设G是非平凡连通图,以下三个命题等价: (1) G是欧拉图. (2) G中每个顶点的度数均为偶数. (3) G中所有的边包含在相互没有公共边的简单回路中. 半欧拉图的判定 ? 设G是连通图,G是半欧拉图 当且仅当 G恰有两个奇度点. ? 证明: ? 设P是G中的欧拉通路(非回路),设P的始点与终点分别 是u,v, 则对G中任何一点x, 若x非u,v,则x的度数等于在P 中出现次数的2倍,而u,v的度数则是它们分别在P中间位 置出现的次数的两倍再加1. ? 设G中两个奇度顶点是u,v, 则G+uv是欧拉图,设欧拉回 路是C, 则C中含uv边,?C-uv是G中的欧拉通路.(这表 明:如果试图一笔画出一个半欧拉图,必须以两个奇度 顶点为始点和终点.) 构造欧拉回路 思想:在画欧拉回路时,已经经过的边不能再用.因此, 在构造欧拉回路过程中的任何时刻,假设将已经经过的边 删除,剩下的边必须仍在同一连通分支当中. 构造欧拉回路-Fleury算法 ? 算法: ? 输入:欧拉图G ? 输出:简单通路P = v0e1v1e2,…,eiviei+1,…,emvm, 其中包含了 EG中所有的元素. 1. 任取v0?VG, 令P0=v0;

2. 设Pi=v0e1v1e2,…,eivi, 按下列原则从EG-{e1,e2,…,ei}中选择ei+1. (a) ei+1与vi相关联;

(b) 除非别无选择,否则ei+1不应是G-{e1,e2,…,ei}中的割边. 3. 反复执行第2步,直到无法执行时终止. Fleury算法的证明 ? 算法的终止性显然. ? 设算法终止时,Pm= v0e1v1e2,…,eiviei+1,…,emvm, ? 其中诸ei互异是显然的.只须证明: (1) Pm是回路,即v0=vm. (2) Pm包括了G中所有的边. 令Gi=G-{e1,e2,…,ei} (1) (证明是回路)假设v0?vm.由算法终止条件,在Gm中已没 有边与vm相关联.假设除最后一次外,vm在Pm中出现k次, 则vm的度数是2k+1, 与G中顶点度数是偶数矛盾. (2) (证明含所有边)假设Pm没有包括G中所有的边,令Gm中所有 非零度顶点集合为S(非空), 令S'

=VG-S, 则vm?S'

. 考察序列e1,e2,…ej,ej+1,…,em.假设j是满足vj?S, 而vj+1?S'

的最大下标. 如果没有这样的j,G就不连通,矛盾.因为Pm的终点在S'

中,因此ej+1 一定是Gj中的割边. 令e是在Gj中与vj相关联的异于ej+1的边(非零度点一定有), 根据算法选择 ej+1(割边)的原则,e也一定是割边.但是,Gm中任意顶点的度数必是偶 数,e在Gm中的连通分支是欧拉图,e在Gm的某个 欧拉回路中,不可能是Gj的割边.矛盾. vm S S'

vj vj+1 ej+1 v e Fleury算法的证明 有向欧拉图 ? 有向图中含所有边的有向简单回路称为有向欧拉回路. ? 含有向欧拉回路的有向图称为有向欧拉图. 下面的等价命题可以用于有向欧拉图的判定: ? 若G是弱连通的有向图,则下列命题等价: ? G中含有向欧拉回路. ? G中任一顶点的入度等于出度. ? G中所有的边位于若干个边互不相交的有向简单回路当中. (证明与无向欧拉图类似.) ? 沿着正十二面体的棱寻找一条旅行路线, 通过每个顶 点恰好一次又回到出发点. (Hamilton 1857)

18 周游世界的游戏 ? G中Hamilton通路 ? 包含G中所有顶点 ? 通路上各顶点不重复 ? G中Hamilton回路 ? 包含G中所有顶点 ? 除了起点与终点相同之外,通路上各顶点不重复. ? Hamilton回路与 Hamilton通路 ? Hamilton通路问题可转化为Hamilton回路问题

19 Hamilton通路/回路 ? Hamilton回路:无重复地遍历图中诸点, Euler回路:无重复地遍历图中诸边. ? 若图G中有一顶点的度为1, 则无Hamilton回路. ? 设图G中有一顶点的度大于2, 若有Hamilton回路, 则 只用其中的两条边. ? 若图中有n个顶点, 则Hamilton回路恰有n条边. ? 注:Hamilton回路问题主要针对简单图.

20 Hamilton回路的基本特性 Kn(n?3)有Hamilton回路 a c b e d a c b e d a c b e d K3 K4

21 Hamilton回路的存在性问题 ? 如果图G=(V, E)是Hamilton图,则对V的任一非空子 集S,都有 P(G-S)? |S| 其........