Microsoft PowerPoint - Slide10-EulerHamilton.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Slide10-EulerHamilton.pptx"

俨尧萧
5 years ago
Views:

1 目录欧拉图与哈密顿图 Euler and Hamilton Graph 高晓沨 (XiaofengGao) 1 2 欧拉道路与欧拉回路哈密顿道路与哈密顿回路 Department of Computer Science Shanghai Jiao Tong Univ. 2 欧拉回路欧拉道路与欧拉回路 Euler Path and Euler Circuit 定义定义给定无向连通图 G=(V,E),, 包含图 G 的所有边的简单道路称为的简单道路称为欧拉道路 ( 或欧拉通道通道欧拉迹 ), 包含图 G 的所有边的简单回路称为的简单回路称为欧拉回路 ( 或欧拉闭迹 ) 假设 G 没有孤立点, 若 G 含有欧拉回路, 则称 G 是欧拉图欧拉图 3 4

2 欧拉图定理定理定理图 G 是欧拉图的充要条件是 G 连通且没有奇点证必要性 : 若 G 中有欧拉回路 C, 则 C 过每一条边有且仅有一次对任一节点 v, 如果 C 由 e i 进入 v, 则一定通过另一条边 e j 从 v 离开因此 v 的度是偶数证明 (2) 充分性 : 由于 G 是有穷图, 因此可断定从 G 的任一节点 v 0 出发一定存在 G 的一条简单回路 C 这是因为各节点的度都是偶数, 所以这条简单回路不可能停留在 v 0 以外的某个节点, 而不能再向前伸延以构成闭通道 C 如果 E=C, 则 C 就是欧拉回路, 充分性得证否则在 G 中删去 C 的各边, 得到 G 1 =G C 5 6 证明 (3) G 1 可能是非连通图, 每个顶点的度保持为偶数这时,G 1 中一定存在某个度非零的节点 v i, 同时也是 C 中顶点否则 C 的顶点与 G 1 的顶点之间无边相连, 与 G 是连通图矛盾同理, 从 v i 出发,G 1 中所在的连通分量内存在一条简单回路 C 1 C C 1 仍然是 G 的一条简单回路, 但它包括的边数比 C 多继续构造, 最终有 C =C C 1 C k 是一条欧拉回路范例例判断下图是否欧拉图 : a b a b e d c d c G H 7 8

3 范例 (2) 例试找出下图的一条欧拉回路解解从任一点出发, 比如 v 1 开始, 可构造简单回路 C=(e 1,e 8,e 6,e 7,e 2 ) G 1 =G C 中的 v 2 v 5 度非零且是 C 中的节点从 v 2 开始 G 1 中有简单回路 C 1 =(e 3,e 5,e 4 ), 因此 C C 1 =(e 1,e 3,e 5,e 4,e 8,e 6,e 7,e 2 ) 包含了 G 的所有边, 是 G 的欧拉回路 9 10 其他解法有向连通图的欧拉回路推论推论若有向连通图 G 中各节点的正负度相等, 则 G 中存在有向欧拉回路. 证明方法类似之前定理, 由 G 是有穷图且每个节点正负度相等可以断定从 G 的任一节点 v 0 出发一定存在 G 的一条简单回路 C 若 C=E(G),, 则得证否则在 G 中删去 C 的各边, 找到新的简单回路 C 1, 并添加至 C 中重复该步骤直至 C 成为欧拉回路为止 11 12

4 欧拉道路 ( 欧拉迹 ) 推论推论若无向若无向连通图 G 中只有 2 个度为奇数的顶点则 G 中存在欧拉道路欧拉道路证明证明设 v i 和 v j 是两个奇点, 做 G =G+(v i,v j ) 则 G 中各顶点的度都是偶数由之前定理知,G 有欧拉回路, 它包含 (v i,v j ) 这条边删去此边, 即可得到一条从 v i 到 v j 的简单道路, 它恰好经过了 G 的所有边, 即是一条欧拉道路注 : 该推论实际是充分必要条件, 即无向连通图 G 中存在欧拉道路当且仅当 G 中有零个或两个度为奇数的节点范例例七桥问题既不存在欧拉回路也不存在欧拉道路范例例设连通图 G=(V,E) 有 k 个度为奇数的节点, 证明 E(G) 可以划分为 k/2 条简单道路证明证明易知 k 是偶数在这个 k 个节点间添加 k/2 条边, 使得每个节点都与其中一条边关联, 得到 G,, 易知 G 中各节点的度都为偶数, 故 G 中有欧拉回路 C,, 这 k/2 条边都在 C 上且不相邻接故删去这些边, 可以得到 k/2 条简单道路, 它们包含了 G 的所有边, 即 E(G) 划分成了 k/2 条简单道路编码盘范例例一个编码盘分成 16 个相等的扇面, 每个扇面分别由绝缘体和导体组成, 可以表示 0 和 1 两种状态, 其中 a,b,c,d 四个位置的扇面组成一组二进制输出试问这 16 个二进制数的序列应如何排列, 编码盘才恰好能组成 0000 到 1111 的 16 组四位二进制输出, 同时旋转一周后又返回到 0000 状态? 15 16

5 解法解如果从状态 a 1 a 2 a 3 a 4 (a i =0 或 1) 逆时针旋转一个扇面, 那么新的输出是 a 2 a 3 a 4 a 5, 其中有三位数字不变因此可以用 8 个节点表示从 000 到 111 这 8 个二进制数这样从节点 (a i-1,a i,a i+1 ) 可以到达节点 (a i,a i+1,0) 或 (a i,a i+1,1),, 其输出分别是 (a i-1,a i,a i+1,0) 和 (a i-1,a i,a i+1,1) 用这样的方法可以得到如下图, 它是有向连通图, 共 16 条边, 且每个节点的正负度相等解法 ( 续 ) 由有向图的欧拉回路推论, 该图存在有向欧拉回路, 其中任何一条都是原问题的解如下图即是一个合理的方案一笔画问题定义定义如果一个图可以从某个顶点出发, 每条边恰好经过一次, 最后终止在出发点或另一个顶点, 则称该图可以一笔画一笔画也就是说, 可以一笔画的图含有欧拉道路, 但不一定有欧拉回路拉回路显然欧拉图一定可以一笔画成, 反之则一般不然一笔画定理定理定理一个图能一笔画成的充要条件是, G 连通且奇顶点数为 0 或 2 若奇点数为 2, 则从其中一个奇顶点出发, 终止于另一个奇顶点上, 完成一笔画证明由欧拉回路定理或欧拉道路推论既得 19 20

范例 (2) 例判断下图是否可以一笔画成 : a b a b d c G e d H e c 哈密顿圈 Hamilton Circuit 21 22 哈密顿回路与道路定义定义无向图 G 的一条经过全部节点的初级回路 ( 道路 ) 称为 G 的哈密顿回路 ( 道路 ). 简记为 H 回路 ( 道路 ).

6 范例 (2) 例判断下图是否可以一笔画成 : a b a b d c G e d H e c 哈密顿圈 Hamilton Circuit 哈密顿回路与道路定义定义无向图 G 的一条经过全部节点的初级回路 ( 道路 ) 称为 G 的哈密顿回路 ( 道路 ). 简记为 H 回路 ( 道路 ). 含有哈密顿圈的图称为的图称为哈密顿图, 反之则称为非哈密顿图非哈密顿图对 H 回路问题要求 V(G)= n 3 只需考虑简单图, 因为重边和自环不起作用 H 回路的判定很困难, 没有发现充分必要的条件, 只有若有若干充分条件. 23 H 道路的判定定理定理若简单图 G 的任意两节点 v i 与 v j 之间恒有 d(v i ) +d(v j ) n 1 则 G 中存在 H 道路. 证明思路 : (1) 由定理条件 :G 是连通图. (2) 令 P 是 G 中最长初级道路, 则 P 是 H 道路. 若不是 : (i) 由定理条件 : 必有经过 P 中节点的初级回路 C. (ii) 由连通性 :C 必可与 C 外某相邻节点构成比 P 更长的初级道路. 24

7 证明连通性连通性我们首先首先证明 G 是连通图若 G 有两个或更多个多个互不连通的连通分不连通的连通分支, 设一个连通分支中有 n 1 个节点, 任取一个节点 v 1 设另一个连通分支中有 n 2 个节点, 任取一个节点 v 2 因为 d(v 1 ) n 1-1,d(v 2 ) n 2-1,, 故 d(v 1 )+d(v 2 ) n 1 +n 2-2<n-1,, 这与题设矛盾, 故 G 必连通证明 ( 续 ) 其次, 我们从一条边出发构成一条路, 证明它是 H 道路设在 G 中有含 p 1 条边的路,p<n,, 它的节点序列为 v 1, v 2,, v p 如果有 v 1 或 v p 邻接于不在这条路上的一个节点, 我们可们可扩展这条路, 使它包含这一个节点, 从而得到 p 条边的路, 否则,v 1 和 v p 都只邻接于这条路上的节点我们证明在这种们证明在这种情况情况下下, 存在一条回路包含节点 v 1, v 2,, v p 证明 ( 续 ) 若 v 1 邻接于 v p, 则 v 1, v 2,, v p, v 1 即为所求的回路假设与 v 1 邻接的节点集是 {v l,v m,,v t }( 共 k 个 ),, 这里 2 l, m,, j,, t p-1,, 如果 v p 邻接于 v l-1,v m-1,,v j-1,,v t-1 中之一, 譬如 v j-1, 则 v 1 v 2 v 3 v j-1 v p v p-1 v j v 1 是所求的包含节点 v 1, v 2,, v p 的回路证明 ( 续 ) 如果 v p 不邻接于 v l-1,v m-1,,v t-1 中任一个, 则 v p 至多邻接 p-k-1 个节点,d(v p ) p-k-1,d(v 1 )= k,, 故 d(v p )+d(v 1 ) p-k-1+k=p-1<n-1,, 即 v 1 与 v p 度数之和至多为 n 2,, 矛盾至此, 我们有包含所有节点 v 1, v 2,, v p 的一条回路, 因为 G 是连通的, 所以在 G 中必有一个不属于该回路的节点 v x 与 v 1, v 2,, v p 中的某一个节点 v k 邻接

8 证明 ( 续 ) 于是就得到一条包含 p 条边的路 (v x,v k,v k+1,,v j-1,v p,v p-1,,v j,,v 1,v 2,,v k-1 ) 如下图所示, 重复前述构造法, 直到得到 n-1 条边的路 H 回路的判定定理定理 (Ore,1960) 若简单图 G(n 3) 的任一对不相邻节点 v i 与 v j 都满足 d(v i ) +d(v j ) n 则 G 有 H 回路. 证明证明由 H 道路判定定理知,G 有 H 道路设其两端点是 v 1 和 v n, 若 G 不存在 H 回路, 一定有 d(v 1 ) +d(v n ) n-1<n,, 矛盾 H 回路的判定定理定理 (Dirac,1952) 若简单图 G(n 3) 的任一节点的度 n/2, 则 G 有 H 回路. 证明证明利用上用上述推理推理求证范例例举例说明存在不例说明存在不满足满足哈密顿图判定的充分条件, 但确实确实是哈密顿图解做正六边形 A, A 中所有顶点的度都为 2,, 则任意两个顶点的度之和都是 4,, 不满足哈密顿图判定的充分条件, 但它显然是哈密顿图 31 32

9 H 回路的判定 ( 闭合图引理 1) 引理简单图 G=(V,E) 若有不相邻的节点 v i, v j 满足 d(v i ) +d(v j ) n,, 则 G 有 H 回路 iff G+(v i,v j ) 有 H 回路. 证明证明必要性显然下面证充分性假设 G 不存在 H 回路, 则 G+(v i,v j ) 的 H 回路一定经过边 (v i,v j ),, 删去 (v i,v j ),, 即 G 中存在一条以 v i, v j 为端点的 H 道路, 这时又有 d(v i )+d(v j )<n,, 与已知矛盾闭合图定义定义若 v i 和 v j 是简单图 G 不相邻的节点, 且满足 d(v i ) +d(v j ) n,, 则令 G =G+(v i,v j ) 对 G 不断加入这样的边 (v i,v j ), 直至不再有满足条件的节点对, 最终得到的图称为 G 的闭合图, 记作 C(G). 例右图(a) 的闭合图是 (b) 闭合图引理 2 引理引理简单图 G 的闭合图是唯一的. 证明证明设 C 1 (G) 和 C 2 (G) 是 G 的两个闭合图, L 1 ={e 1,e 2,,e r },L 2 ={a 1,a 2,,a s } 分别是 C 1 (G) 和 C 2 (G) 中新加入边的集合, 可以证明 L 1 =L 2, 即 C 1 (G)=C 2 (G) 如若不然, 不妨设 e i+1 =(u,v) L 1 是构造 C 1 (G) 时第一条不属于 L 2 的边, 即 e i+1 C 2 (G) 令 H=G {e 1,e 2,,e i },, 这时 H 是 C 1 (G) 也是 C 2 (G) 的子图由于构造 C 1 (G) 时要加入 e i+1, 显然 H 中满足 d(u)+d(v) n,, 但 (u, v) C 2 (G),, 与 C 2 (G) 是 G 的闭合图矛盾闭合图定理定理定理 (Bondy&Chvátal, 1976) 简单图 G 有 H 回路 iff C(G) 有 H 回路. 证明证明设 C(G)=G L 1,L 1 ={e 1,e 2,,e t },, 由之前两个引理知 : G 有 H 回路 G+e 1 有 H 回路 G L 1 有 H 回路由于 C(G) 唯一, 故定理成立 35 36

10 闭合图推论推论推论若 C(G)=K n, 则 G 有 H 回路. Ore 定理和 Dirac 定理是这个推论的直接推论. 例右图(a) 有 H 回路注 : 该推论说明完全图 K n 必有 H 回路连通分量定理定理定理设 G 是哈密顿图, 则对于 G 顶点集的任意子集 S,, 在 G 中移除 S 中的顶点及所有与这些顶点相关联的边, 所产生子图的子图的连通分量数连通分量数必不必不大于 S 即 S V, p(g-s) S, 其中 p(g-s) 为 G-S 的连通分支数证明证明设 C 是 G 中任意一条 H 回路, 易知, 当 S 中顶点在 C 上均不相邻时,p(C-S) 达到最大值 S, 而当 S 中顶点在 C 上有彼此相邻现象时, 均有 p(c-s) < S,, 所以有 p(c-s) S 而 C 是 G 的生成子图, 所以有 p(g-s) p(c-s) S 推论推论推论每个哈密每个哈密尔顿图都没有顿图都没有割点证明证明设无向图 G=(V,E) 是 H 图, 假设其存在割点, 设为 v r, 令 S={v r },, 则由割点定义知,p(G-S) 2> S,, 与之前定理矛盾推论推论有奇数个顶点的二部图必定不是哈密顿图范例例设 n( 3) 人中中, 任两个人合在一合在一起都认识其余 n-2 个人证明这 n 个人可以排成一队, 使相邻者互者互相认识认识解用一个节点表示一个用一个节点表示一个人, 相互认识则用边连接相应的节点, 于是得到简单图 G 若 G 中有 H 道路, 则问题可证由已知条件, 对任意两点 v i, v j V(G),, 都有 d(v i )+d(v j ) n-2 此时若 v i, v j 认识, 即 (v i,v j ) E(G),, 则 d(v i )+d(v j ) n; 39 40

11 范例 ( 续 ) 若互相不相不认识, 必存在 v k V(G), 满足 (v i, v k ) E(G),(v j,v k ) E(G) 否则, 设 (v i, v k ) E(G),, 就出现 v k,v j 合在一起不认识 v i, 与原题设矛盾因此也有 d(v i )+d(v j ) n-1 由 H 路判定定理得,G 中存在 H 道路 H 回路范例例证明下图中没有 H 回路解 H 回路是经过每个节点一次的初级回路经观察, 如果给某个节点标记 A,, 它的邻接点标记 B,B 的邻接点标记 A,, 则可顺利标顺利标完 G 中的节点若 G 中有 H 回路, 该回路一定是沿着 ABAB AB 走完全部节点, 即标 A 与标 B 的节点数相同但 V(G) 是奇数, 矛盾地图染色例地图不存在相图不存在相交的边的边界如果一个地图中有 H 回路, 则可用 4 种不同颜色颜色对它们的域进行着色, 使相邻的域染域染不同不同颜色颜色证明证明两个不同的域相邻, 则共同边界为一条边 ; 三个或三个以上不同域相邻, 则共同边界为一个点 ; 解设 H 是图 G 中的一条 H 回路, 则 H 将 G 的域划分成了内域和外和外域两个部分内域和外和外域均域均用两种不同的颜色染色, 则四种颜色颜色即可如果内域和外和外域不能用两种不能用两种颜色着色, 则必然出现三个或三个以上的三个或三个以上的域相邻的相邻的情况情况这时, 该内域域 ( 外域域 ) 中定有一个域相交的点这与 H 回路相悖 43 44

12 Xiaofeng Gao

图论与代数结构

图论与代数结构第二章道路与回路 2.1 道路与回路定义 2.1.1 有向图 G=(V,E) 中, 若边序列 P=(e i1, e i2,, e iq ), 其中 e ik =(v i, v j ) 满足 v i 是 e ik-1 的终点, v j 是 e ik+1 的始点, 就称 P 是 G 的一条有向道路. 如果 e iq 的终点也是 e i1 的始点, 则称 P 是 G 的一条有向回路道路与回路如果 P