图论与代数结构

Size: px

Start display at page:

Download "图论与代数结构"

奥和
5 years ago
Views:

1 第二章道路与回路 2.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 的一条有向回路

2 道路与回路如果 P 中的边没有重复出现, 则分别称为简单有向道路和简单有向回路进而, 如果 P 中结点也不重复出现, 又分别称它们是初级有向道路和初级有向回路, 简称为路和回路显然, 初级有向道路 ( 回路 ) 一定是简单有向道路 ( 回路 )

3 有向道路 A e 4 B e 1 e 5 e 3 C e 2 D (e1, e2, e5, e1) 有向道路, 不是简单有向道路 (e1, e2, e5, e4) 简单有向道路, 不是初级有向道路 (A) (e1, e2, e3) 初级有向道路 (e1, e2, e5) 初级有向回路

4 道路与回路定义无向图 G=(V, E) 中, 若点边交替序列 P=(v i1, e i1, v i2, e i2,, e iq-1, v iq ) 满足 v ik, v ik+1 是 e ik 的两个端点, 则称 P 是 G 中的一条链或道路. 如果 v iq =v i1, 则称 P 是 G 中的一个圈或回路, 其长度为边数 (q-1) 如果 P 中没有重复出现的边, 称之为简单道路或简单回路, 若其中结点也不重复, 又称之为初级道路或初级回路

5 例 v 2 v 2 e 1 e 2 v 1 e 6 e 7 e 6 e 7 v 3 e 5 e 3 v 5 e4 v 4 e 4 V 1 到 v 24 的初级道路的简单道路

6 道路与回路定义设 G 是无向图, 若 G 的任意两结点之间都存在道路, 就称 G 是连通图, 否则称为非连通图 2. 如果 G 是有向图, 不考虑其边的方向, 即视为无向图, 若它是连通的, 则称 G 是连通图 3. 若连通子图 H 不是 G 的任何连通子图的真子图, 则称 H 是 G 的极大连通子图或称连通支显然 G 的每个连通支都是它的导出子图

7 连通图 A B 连通图 C D A C B D 非连通图两个连通分支 {B}, {A, C, D}

8 道路与回路定义设 C 是简单图 G 中含结点数大于 3 的一个初级回路, 如果结点 v i 和 v j 在 C 中不相邻, 而边 (v i,v j ) E(G), 则称 (v i,v j ) 是 C 的一条弦

9 极长初级道路极长初级道路 : 在简单图 G=<V,E> 中, E, 设 1 =v 0 v 1 v l 为 G 中一条初级道路, 若路径的两个端点 v 0 和 v l 不与初级道路本身以外的任何结点相邻, 这样的初级道路称为极长初级道路 ( 有向图中, 初级道路起点的前驱集 ( 内邻集 ), 终点的后继集 ( 外邻集 ), 都在初级道路本身上 )

10 扩大初级道路法扩大初级道路法 : 任何一条初级道路, 如果不是极长初级道路, 则至少有一个端点与初级道路本身以外的结点相邻, 则将该结点及其相关联的边扩到新的初级道路中来, 得到更新的初级道路继续上述过程, 直到变成极长初级道路为止

11 极长初级道路实例由某条道路扩大出来的极长初级道路不唯一, 可以说, 极长初级道路不是图中最长的道路 (1) 中的实线边所示为长度为 2 的初级道路, 而 (2)(3)(4) 为扩大后的极长初级道路

12 道路与回路证明 : 若对简单图 G 中每一个 v k V(G), 都有 d(v k ) 3, 则 G 中必含带弦的回路证明 : 在 G 中构造一条极长的初级道路 P=(v 0, e i1, v 1, e i2,, v l-1, e il, v l ) 由于 P 是极长的初级道路, 所以 v 0 和 v l 的邻接点都在该道路 P 上由已知条件, d(v k ) 3, 不妨设 Γ(v 0 )={v 1, v ij, v ik, }, 其中 1<j<k, 这时 (v 0, v 1,, v ik, v 0 ) 是一条初级回路, 而 (v 0, v ij ) 就是该回路中的一条弦

13 带弦回路 v 0 v 2 v 3 v 1 v 4 1. 构造极长初级道路 (v0, v1), (v0, v1, v2), (v0, v1, v2, v3), (v0, v1, v2, v3, v4) 2. Γ(v0)={v1,v2,v3,v4} 3. (v0,v1,v2,v3,v0) 即为所求的初级回路, 而 (v0,v2) 就是该回路的一条弦

14 道路与回路

16 道路与回路含有 K 3 子图的图一定不是二分图 K n 不是二分图 (n>=3)

17 道路与回路证明 : 如果二分图 G 中存在回路, 则它们都是由偶数条边组成的证明 : 设 C 是二分图 G 的任一条回路, 不妨设 v 0 X 是 C 的始点, 由于 G 是二分图, 所以沿回路 C 必须经过偶数条边才能达到某结点 v i X, 因而只有经过偶数条边才能回到 v 0

19 道路与回路证明 : 设 G 是简单图, 当 m>(n-1)(n-2)/2 时,G 是连通图证明 : 假定 G 是非连通图, 则它至少含有 2 个连通分支设分别是 G 1 =(V 1,E 1 ), G 2 =(V 2,E 2 ) 其中 V 1 (G 1 ) =n 1, V 2 (G 2 ) =n 2, n 1 +n 2 =n, E 1 (G 1 ) + E 2 (G 2 ) =m 由于 G 是简单图, 因此 m E E G n n G n n n , 1, n 1 n n

20 道路与回路由于 1 n 1 n-1, 1 n 2 n-1 所以 m 1 2 n 1 n 1 n 1 n 1 n 2, 与已知条件矛盾, 故 G 是连通图

21 道路与回路 n 个结点的连通图的边数一定 n-1 两点间距离 : 若 u 与 v 连通, 则 u 与 v 之间最短道路长度称为 u 与 v 的距离割点 : 去掉该点 ( 及关联边后 ), 图的连通分支数上升割边 ( 桥 ): 去掉该边后, 图的连通分支数上升 a d f g b c e h 割点为 :b, c 和 e 桥 :{a, b} 和 {c, e}

22 补 : 等价概念清华教材曹老师教材链 / 道路通道 ( 依据起点终点是否重合 : 开 / 闭 ) 简单道路迹 ( 依据起点终点是否重合 : 开 / 闭 ) 初级道路路初级回路圈 ( 依据长度 : 奇 / 偶 ) 二分图二部图 / 偶图

23 2.3 欧拉道路与回路 1736 年瑞士著名数学家欧拉 (Leonhard Euler) 发表了图论的第一篇论文哥尼斯堡七桥问题. 成功地回答了, 图中是否存在经过每条边一次且仅一次的回路人们普遍认为欧拉是图论的创始人 1936 年, 匈牙利数学家寇尼格 (Konig) 出版了图论的第一部专著有限图与无限图理论, 这是图论发展史上的重要的里程碑, 它标志着图论将进入突飞猛进发展的新阶段

24 哥尼斯堡七桥问题哥尼斯堡城当时城中居民热衷于这样一个问题 1736 年, 瑞士数学家列昂哈德 ( 现在俄罗斯 ) 在 18. 世纪属东普鲁士欧拉 : 游人从四块陆地中 (Leonhard, Euler) 它位于普雷格尔任一块出发仔细研究了这个问题 (Pregel), 按什么样的线路方能做到每座桥通过一次, 河畔他将上述四块陆地与七座桥间的关, 河中有两个岛, 通过七座桥彼此相联且仅一次而最后返回原地系用一个抽象的图形来描述, 如下图 :, 其中的四块陆地分别用四个点表示, 而陆地之间有桥相连者则用连结两个点的边表示欧拉得出结论 : 哥尼斯堡桥问题是无解的, 即一个人不可能一次走遍两岛两旁陆地和七座桥

25 一笔画

26 欧拉道路与回路 ( 欧拉迹与欧拉闭迹 ) 定义无向连通图 G=(V, E) 中的一条经过所有边的简单回路 ( 道路 ) 称为 G 的欧拉回路 ( 道路 ) 定理无向连通图 G 存在欧拉回路的充要条件是 G 中各结点的度都是偶数

27 欧拉道路与回路定理的证明 : 1. 必要性 : 若 G 中有欧拉回路 C, 则 C 过每条边一次且仅一次. 对任一结点 v 来说, 如果 C 经过 e i 进入 v, 则一定通过另一条边 e j 从 v 离开. 因此结点 v 的度是偶数 2. 充分性 : 由于 G 是有穷图, 因此可以断定, 从 G 的任一结点 v 0 出发一定存在 G 的一条简单回路 C. 这是因为各结点的度都是偶数, 所以这条简单道路不可能停留在 v 0 以外的某个点, 而不能再向前延伸以致构成回路 C

28 定理充分性证明如果 E(G)=C, 则 C 就是欧拉回路, 充分性得证否则在 G 中删去 C 的各边, 得到 G 1 =G-C G 1 可能是非连通图, 但是每个结点的度保持为偶数这时,G 1 中一定存在某个度非零的结点 v i, 同时 v i 也是 C 中的结点否则 C 的结点与 G 1 的结点之间无边相连, 与 G 是连通图矛盾同理, 从 v i 出发,G 1 中 v i 所在连通分支内存在一条简单回路 C 1 显然,C C 1 仍然是 G 的一条简单回路, 但它包括的边数比 C 多继续以上构造方法, 最终有简单回路 C = C C 1 C k, 它包含了 G 的全部边, 即 C 是 G 的一条欧拉回路

29 构造欧拉回路 v 1 v 2 e 1 e 6 e 3 v 3 e 7 e 4 e 8 C=(e 1,e 6,e 8,e 7,e 2 ) C =(e 3,e 5,e 4 ) e 2 v 5 v 2 e 5 v 4 C C =(e 1,e 3,e 5,e 4,e 6,e 8,e 7,e 2 ) =E(G) v 3 v 1 e 3 e 4 v 5 v 4 e 5

30 欧拉道路与回路推论若无向连通图 G 中只有 2 个度为奇的结点, 则 G 存在欧拉道路. 证明 : 设 v i 和 v j 是两个度为奇数的结点. 作 G =G+(v i, v j ), 则 G 中各点的度都是偶数. 由定理 2.3.1, G 有欧拉回路, 它含边 (v i, v j ), 删去该边, 得到一条从 v i 到 v j 的简单道路, 它恰好经过了 G 的所有边, 亦即是一条欧拉道路

31 欧拉道路与回路结论 : 七桥问题既不存在欧拉回路也不存在欧拉道路推论若有向连通图 G 中各结点的正负度相等, 则 G 存在有向欧拉回路. 其证明与定理的证明相仿.

32 欧拉道路与回路例设连通图 G=(V,E) 有 k 个度为奇数的结点, 那么 E(G) 可以划分成 k/2 条简单道路证明 : 由性质 1.1.2,k 是偶数在这 k 个结点间增添 k/2 条边, 使每个结点都与其中一条边关联, 得到 G, 那么 G 中各结点的度都为偶数由定理 2.3.1,G 包含一个欧拉回路 C 而新添的 k/2 条边在 C 上都不相邻所以删去这些边后, 我们就得到由 E(G) 划分成的 k/2 条简单道路

33 举例欧拉回路 (1,2,3,4,5,6,7,8,9) 2(=4/2) 条简单道路 (3,4) 和 (6,7,8,9,1)

34 一笔画某图形是否可以一笔画出凡是由偶点组成的连通图, 一定可以一笔画成画时可以把任一偶点为起点, 最后一定能以这个点为终点画完此图凡是只有两个奇点的连通图 ( 其余都为偶点 ), 一定可以一笔画成画时必须把一个奇点为起点, 另一个奇点终点其他情况的图都不能一笔画出, 但是奇点数除以二便可算出此图需几笔画成

35 编码盘一个编码盘分成 16 个相等的扇面, 每个扇面分别由绝缘体和导体组成, 可表示 0 和 1 两种状态, 其中 a,b,c,d 四个位置的扇面组成一组二进制输出, 如下图所示试问这 16 个二进制数的序列应如何排列, 才恰好能组成 0000 到 1111 的 16 组二进制输出, 同时旋转一周后又返回到 0000 状态? a 16 a 1 a 2 a b a 5 a 4 a 3 c d

36 编码盘解答 : 如果从状态 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- 1a 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), 这样可以得到下图

37 编码盘 0000 (000) (001) 1001 (100) (010) (011) (101) (111) 1111 (110)

38 编码盘解答 : 该图是有向连通图, 共有 16 条边, 且每结点的正负度相等有推论 2.3.2, 它存在有向欧拉回路其中任一条都是原问题的解, 比如 ( ) 就是一个方案 0000, 0001, 0010, 0101, 1010, 0100, 1001, 0011, 0110, 1101, 1011, 0111, 1111, 1110, 1100, 1000.

39 作业一 P35 1; 2; 3; 6

40 2.4 哈密顿道路与回路 ( 哈密顿路与圈 ) 19 世纪英国数学家哈密顿提出的问题 : 一个凸 12 面体, 把 20 个顶点比作世界上 20 个城市,30 条棱表示这些城市间的交通路线问 : 能否周游世界, 即从某个城市出发, 经过每城一次且只一次最后返回出发地

41 哈密顿道路与回路答案 :

42 哈密顿道路与回路定义无向图的一条过全部结点的初级回路 ( 道路 ) 称为 G 的哈密顿回路 ( 道路 ), 简记为 H 回路 ( 道路 ) 哈密顿回路是初级回路, 是特殊的简单回路, 因此它与欧拉回路不同当然在特殊情况下,G 的哈密顿回路恰好也是其欧拉回路鉴于 H 回路是初级回路, 所以如果 G 中含有重边或自环, 删去它们后得到的简单图 G, 那么 G 和 G 关于 H 回路 ( 道路 ) 的存在性是等价的因此, 判定 H 回路存在性问题一般是针对简单图的

43 充分条件和必要条件满足充分条件, 判断是 ( 是哈密顿图 ) 不满足必要条件, 判断否 ( 不是哈密顿图 ) 不满足充分条件, 不能判断否 ( 不是哈密顿图 ) 满足必要条件, 不能判断是 ( 是哈密顿图 )

44 哈密顿道路与回路 - 引理 * 引理 *: 设 P=(v 1, v 2,, v l ) 是图 G 中一条极长的初级道路 ( 即 v 1 和 v l 的邻点都在 P 上 ) 而且 d(v 1 )+d(v l ) l, 则 G 中一定存在经过结点 v 1, v 2,, v l 的初级回路证明 : 反证法若边 (v 1,v p ) E(G), 就不能有 (v l, v p- 1) E(G), 不然删除 (v p, v p-1 ), 就形成了一条过这 l 个结点的初级回路于是, 设 d(v 1 )=k, 则 d(v l ) lk-1( 其中减去 1 表示不能与自身相邻 ) 因此 d(v 1 )+d(v l ) l-1 与已知矛盾所以存在经过结点 v 1, v 2,, v l 的初级回路 C

45 哈密顿道路与回路 - 引理 * v l v p V p-1 v 1 v 2

46 哈密顿道路与回路 - 充分性定理 1 定理如果简单图 G 的任意两结点 v i, v j 之间恒有 d(v i )+d(v j ) n-1 则 G 中存在哈密顿道路证明 : 先证 G 是连通图若 G 非连通, 则至少分为 2 个连通支 H 1, H 2, 其结点数分别为 n 1, n 2 从中各任取一个结点 v i, v j, 则 d(v i ) n 1-1, d(v j ) n 2-1 故 d(v i )+d(v j )<n-1 矛盾

47 哈密顿道路与回路 - 充分性定理 1 以下证 G 存在 H 道路设 P=(v i1, v i2,, v il ) 是 G 中一条极长的初级道路, 即 v i1 和 v il 的邻点都在 P 上此时, (1) 若 l=n, P 即为一条 H 道路 (2) 若 l<n, 则可以证明 G 中一定存在经过结点 v i1, v i2,, v il 的初级回路 (CLAIM) 否则, 若边 (v i1,v ip ) E(G), 就不能有 (v il, v ip-1 ) E(G), 不然删除 (v ip, v ip-1 ), 就形成了一条过这 l 个结点的初级回路于是, 设 d(v i1 )=k, 则 d(v il ) l-k-1( 其中减去 1 表示不能与自身相邻 ) 因此 d(v i1 )+d(v il ) l-1 < n-1 与已知矛盾所以存在经过结点 v i1, v i2,, v il 的初级回路 C

48 哈密顿道路与回路 - 充分性定理 1 由于 G 连通, 所以存在 C 之外的结点 v t 与 C 中某点 (v iq ) 相邻删去 (v iq-1, v iq ), 则 P =(v t, v iq,, v ip-1, v il,, v ip, v i1,, v iq-1 ) 是 G 中一条比 P 更长的初级道路以 P 的两个端点 v t 和 v iq-1 继续扩充, 可得到一条新的极长的初级道路重复上述过程, 因为 G 是有穷图, 所以最终得到的初级道路一定包含了 G 的全部结点, 即是 H 道路

49 哈密顿道路与回路 - 充分性定理 1 v il v il v ip v ip V ip-1 V ip-1 v i1 v i2 V iq-1 v iq v iq+1 v t v i1 v i2

50 哈密顿道路与回路 - 充分性定理 1 推论若简单图 G 的任意两结点 v i 和 v j 之间恒有则 G 中存在哈密顿回路 d(v i )+d(v j ) n 证明 : 由定理 2.4.1,G 有 H 道路设其两端点是 v 1 和 v n, 若 G 不存在 H 回路, 根据引理 * 证明, 一定有 : 若 d(v 1 )=k, 则 d(v n ) n-k-1, 那么 d(v 1 )+d(v n ) n-1<n, 与已知矛盾推论若简单图 G 中每个结点的度都大于等于 n/2, 则 G 有 H 回路证明 : 由推论可得

51 哈密顿道路与回路定义若 v i 和 v j 是简单图 G 的不相邻结点, 且满足 d(v i )+d(v j ) n, 则令 G =G+(v i, v j ). 对 G 重复上述过程, 直至不再有这样的结点对为止. 最终得到的图为 G 的闭合图, 记作 C(G). G C(G)

52 哈密顿道路与回路引理简单图 G 的闭合图 C(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 L 2 令 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 的闭合图矛盾

53 哈密顿道路与回路引理设 G 是简单图, v i,v j 是不相邻结点, 且满足 d(v i )+d(v j ) n. 则 G 存在 H 回路的充要条件是 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, 与已知矛盾

54 哈密顿道路与回路 - 充分性定理 2 定理简单图 G 存在哈密顿回路的充要条件是其闭合图存在哈密顿回路证明 : 设 C(G)=G L 1, L 1 ={e 1, e 2,, e t }, 由引理和引理 2.4.2, G 有 H 回路 G+e 1 有 H 回路 G L 1 有 H 回路由于 C(G) 是唯一的, 故定理得证推论设 G(n 3) 是简单图, 若 C(G) 是完全图 K n, G 有 H 回路说明 :d(v i )+d(v j )=(n-1)+(n-1)=n+(n-2)

55 哈密顿道路与回路举例 : 设 n( 3) 个人中, 任两个人合在一起都认识其余 n-2 个人证明这 n 个人可以排成一队, 使相邻者都互相认识证明 : 每个人用一个结点表示, 相互认识则用边连接相应的结点, 于是得到简单图 G 若 G 中有 H 道路, 则问题得证由已知条件, 对任意两点 v i, v j V(G), 都有 d(v i )+d(v j ) n-2 此时, (1) 若 v i 和 v j 相识, 即 (v i,v j ) E(G), 则 d(v i )+d(v j ) n (2) 若 v i 和 v j 不相识, 必存在 v k V(G), 满足 (v i,v k ), (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 综上由定理 2.4.1,G 中存在 H 道路

56 哈密顿道路与回路 - 必要性定理必要性定理 : 若 G 是 H- 图, 则对于 V 的每个非空真子集 S, 均有 W(G-S) S, 其中 W(G-S) 是 G-S 中连通分支数证明 : 设 C 是 G 的 H- 回路, 则对于 V 的每个非空真子集 S 均有 W(C-S) S 而 C-S 是 G-S 的生成子图, 故 W(G-S) W(C-S), 因此 W(G-S) S 以 K 4 为例

57 哈密尔顿图例判定下面三个图是否是哈密尔顿图. a a

58 哈密尔顿图在 G 1 中, 令 S={a,b,c,d,e}, 则 W(G 1 -S)=6, 由必要性定理知, G 不是哈密尔顿图在 G 2 中令 S={a,b,c}, 则 W(G 2 -S)=4, 所以 G 2 也不是哈密尔顿图 G 3 称为彼得森图可以证明它不是哈密尔顿图, 但对它的任意顶点子集 S, 有 W(G 3 -S) S 这说明必要性定理中的条件, 只是哈密尔顿图的一个必要条件, 而不是充分条件与彼得森图同构的图也一定不是哈密尔顿图

59 充分条件和必要条件满足充分条件, 判断是 ( 是哈密顿图 ) 不满足必要条件, 判断否 ( 不是哈密顿图 ) 不满足充分条件, 不能判断否 ( 不是哈密顿图 ) 满足必要条件, 不能判断是 ( 是哈密顿图 )

60 推论 : 哈密顿图没有割点. 定理 : 有奇数个顶点的二部图必不是哈密顿图.

61 哈密尔顿图对于一个 H- 图, 如果可以用 A, B 交替标记所有的顶点 ( 即 : 从任一结点开始, 给其标以 A, 它的邻接点标以 B,B 的邻接点再标以 A, 如此继续下去, 直至 G 中所有结点被标完 ), 则有 A = B ( 即 A,B 个数相同 ) 对于一个图如果无法用 A, B 交替标记顶点, 也无法判断是否是 H- 图例如 : A B B

62 哈密尔顿图难点

63 作业二 P36 8, 9, 10

Microsoft PowerPoint - Slide10-EulerHamilton.pptx

Microsoft PowerPoint - Slide10-EulerHamilton.pptx 目录欧拉图与哈密顿图 Euler and Hamilton Graph 高晓沨 (XiaofengGao) 1 2 欧拉道路与欧拉回路哈密顿道路与哈密顿回路 Department of Computer Science Shanghai Jiao Tong Univ. 2 欧拉回路欧拉道路与欧拉回路 Euler Path and Euler Circuit 定义定义给定无向连通图 G=(V,E),,