集合的运算

Size: px

Start display at page:

Download "集合的运算"

盈潭侯
4 years ago
Views:

1 图的连通性离散数学图论初步南京大学计算机科学与技术系

2 内容提要通路与回路通路与同构无向图的连通性连通度 2- 连通图有向图的连通性无向图的定向 2

3 通路的定义定义 : 图 G 中从 v 0 到 v n 的长度为 n 的通路是 G 的 n 条边 e 1,, e n 的序列, 满足下列性质存在 v i V (0 i n), 使得 v i-1 和 v i 是 e i 的两个端点 (1 i n) 相关点回路 : 起点与终点相同, 长度大于 0 不必区分多重边时, 可以用相应顶点的序列表示通路长度为 0 的通路由单个顶点组成简单通路 : 边不重复, 即, i, j, i j e i e j 初级通路 : 点不重复, 亦称为路径 3

4 通路 ( 举例 ) a b c d e f 简单通路 :a, d, c, f, e 长度为 4 回路 :b, c, f, e, b 长度为 4 通路 :a, b, e, d, a, b 长度为 5 不是通路 :d, e, c, b 4

5 通路的定义 ( 有向图 ) 定义 : 有向图 G 中从 v 0 到 v n 的长度为 n 的通路是 G 的 n 条边 e 1,, e n 的序列, 满足下列性质存在 v i V (0 i n), 使得 v i-1 和 v i 分别是 e i 的起点和终点 (1 i n) 相关点回路 : 起点与终点相同, 长度大于 0 不必区分多重边时, 可以用相应顶点的序列表示通路长度为 0 的通路由单个顶点组成简单通路 : 边不重复, 即, i, j, i j e i e j 5

6 通路 ( 举例 ) v 1 v 2 v 4 v 3 简单通路 :v 1, v 4, v 2, v 3 长度为 3 回路 : v 2, v 1, v 4, v 2 长度为 3 通路 : v 2, v 3, v 1, v 4, v 2, v 3 长度为 5 6

7 通路与同构设图 G 的邻接矩阵为 A (A k ) i,j : v i 到 v j 的长度为 k 的通路个数 (A k ) i,i : v i 到 v i 的长度为 k 的回路个数同构图的不变量 : 长度为 k 的回路的存在性 7

8 通路与同构 u 1 v 1 u 6 u 2 v 6 v 2 u 5 u 3 u 2 u 4 v 5 v 3 v 4 v 2 u 1 u 3 v 1 v 3 u 5 u 4 v 5 v 4 8

9 无向图的连通性定义 : 无向图 G 称为是连通的, 如果 G 中任意两个不同顶点之间都有通路 b b a c a c e d e d G 1 G 2 9

10 连通分支连通分支极大连通子图每个无向图是若干个互不相交的连通分支的并顶点之间存在通路是一个等价关系, 任一等价类上的导出子图即为一个连通分支若图 G 中存在从 u 到 v 的通路, 则一定有从 u 到 v 的简单通路证明 : 最短通路必是简单的, 事实上, 它没有重复顶点 10

11 点的删除与连通分支数量的增减 p(g-v)( 其中 v 是 G 中任意一个顶点 ) 的情况比较复杂 ( 注意 : 删除顶点意味着同时删除该点关联的边 ) 可能会减少 ( 删除孤立点 ) ( 孤立点 ) 不变 ( 例如 : 删除悬挂点 ) ( 悬挂点 ) 增加很多个 ( 例如 :star) 11

12 割点 (cut vertex, articulation vertex) 定义 :G 是图, v V G, 若 p(g-v)>p(g), 则称 v 是割点割点 ( 注意 : 只需考虑割点所在的连通分支, 以下讨论不妨只考虑连通图 ) 12

13 关于割点的三个等价命题以下三个命题等价 : (1) v 是割点 (2) 存在 V-{v} 的分划 {V 1, V 2 }, 使 u V 1, w V 2, uw- 通路均包含 v (3) 存在顶点 u,w(u v, w v), 使得任意的 uw- 通路均包含 v 证明 : (1) (2): v 是割点,G-v 至少存在两个连通分支, 设其中一个的顶点集是 V 1 令 V 2 =V-(V 1 {v}), 则 u V 1, w V 2, u,w 一定在 G-v 的不同的连通分支中在 G 中, 任何 uw- 通路必含 v (2) (3): 注意 :(3) 是 (2) 的特例 (3) (1): 显然, 在 G-v 中已不可能还有 uw- 通路, G-v 不连通, v 是割点 13

14 边的删除与连通分支数量的增加设 p(g) 表示图 G 中连通分支数, 则 : p(g) p(g-e) p(g)+1, 其中 e 是 G 中任意一条边第一个不大于显然成立 ( 删除 e 只会影响 e 所在的那一个连通分支 ) 第二个不大于成立 : 注意在图中任意两点之间加一条边, 最多只能将两个连通分支连成一个 14

15 割边 ( 桥 ;cut edge, bridge) 定义 : 设 G 是图,e E G, 若 p(g-e)>p(g), 则称 e 是 G 中的割边割边 ( 注意 : 只需考虑割边所在的连通分支, 以下讨论不妨只考虑连通图 ) 15

16 割边与回路 e 是割边当且仅当 e 不在 G 的任一简单回路上 ( 注意 : 割点没有相应结论 ) 证明 : : 假设 C 是包含 e=xy 的初级回路, 令 C-e=P, P 是不含 e 的 xy- 路径对 G 中任意顶点 u,v, 若 uv- 通路中不含 e, 则该通路也是 G-e 中的 uv- 通路 ; 若 uv- 通路中含 e, 则将所有的 e 均替换为 P, 得到 G-e 中的 uv- 通路, G-e 仍连通, 与 e 是割边矛盾 : 假设 e=xy 不是割边则 G-e 仍连通, 设 P 是 G-e 中的 xy- 路径, P 中不含 e, 则 :P+e 是 G 中的简单回路, 矛盾 16

17 有关割边的四个等价命题以下四个命题等价 : (1) e 是割边 (2) e 不在 G 的任一简单回路上 ( 注意 : 割点没有相应结论 ) (3) 存在 V 的分划 {V 1, V 2 }, 使得 u V 1, w V 2, uw- 通路均包含 e (4) 存在顶点 u,w, 使得任意的 uw- 通路均包含 e 17

18 连通图连接的牢固度不一样图 G 1 中删除任意一条边都不连通了图 G 2 则至少删除两条边, 或删除中间那个顶点, 才不连通图 G 3 删除任意一个点依然连通图 G 4 至少要删除四条边才可能不连通, 且不可能通过删除顶点使其不连通 G 1 G 2 G 3 G 4 18

19 图的 ( 点 ) 连通度 ( 注意 : 若 G 是顶点数不少于 2 的非完全图, 删除足够数量的点一定能使图变成不连通图或者平凡图 ) 定义 : 使非平凡连通图 G 成为不连通图或者平凡图需要删除的最少顶点数称为图 G 的 ( 点 ) 连通度, 记为 κ(g) ( 注意 : 这不意味着任意删除 κ(g) 个点就一定会使该图不连通 ) 约定 : 不连通图或平凡图的连通度为 0, 而 κ(k n )=n-1 若图 G 的连通度不小于 k, 则称 G 是 k- 连通图 ; (k- 连通图, 即 κ(g) k: 删除少于 k 个顶点, 它依然连通 ) ( κ(g)=k: k- 连通图, 且有 k 个顶点, 删除它们就不连通 ) 19

20 图的边连通度 ( 注意 : 若 G 是顶点数不少于 2 的连通图, 删除足够数量的边使得图变成不连通 ) 类似地, 使非平凡连通图 G 变成不连通需要删除的最少边数称为图 G 的边连通度记为 (G) ( 注意 : 这不意味着任意删除 (G) 条边就一定会使该图不连通 ) 约定 : 不连通图或平凡图的边连通度为 0 (K n )=n-1 若图 G 的边连通度不小于 k, 则称 G 是 k- 边连通图 (k- 边连通图, 即 (G) k: 删除少于 k 条边, 它依然连通 ) ( (G) =k: k- 边连通图, 且有 k 条边, 删除它们就不连通 ) 20

21 关于连通度的例子 W 6 ( 轮 ): = =3 = C 6 ( 圈 ): = =2 = K 2,3 ( 完全二部图 ): = =2 = G: =1, =2, =3 表示图中最小顶点度 W 6 C 6 K 2,3 G 21

22 连通度的上限 ( 续 ) 若图 G 是非平凡的, 则 (G) (G) (G) 易证 λ(g) (G) 设 F 为 E 的极小子集使得 G-F 不连通, 只需证明 κ(g) F 若 G 中存在不与 F 中的边相关联的点, 设为 v 令 C 为 G-F 中 v 所在的连通分支 F 中的任一边, 其两个端点不会都在 C 中 (F 的极小性 ) C 中与 F 中边相关联的顶点 ( 集合 ) 分隔 v 与 G-C,κ(G) F 22

23 连通度的上限 ( 续 ) 若 G 中的各顶点均和 F 中的某条边关联对任意顶点 v, 令 C 是 G-F 中包含 v 的连通分支考虑 v 的任一邻居 w 若 w 在 C 中, 则 w 必定和 F 中的某条边关联 ; 若 w 在 G-C 中, 则边 vw 属于 F 因此, N(v) F, 即 d G (v) F. 若 V-N(v)-v Ф, 则删除 N(v) 后, v 和 V-N(v)-v 不连通, 从而 κ(g) F 若 V-N(v)-v=Ф, 则取其它节点以满足 1) 的条件若所有节点均有 V-N(u)-u=Ф, 则图 G 为完全图, 有 κ(g)=λ(g)= G -1 23

24 连通度的上限 ( 续 ) d G (v) F 24

25 达到连通度上限的图设 G 是简单图, G =n 3, 且 G n-2, 则 (G)= G ( 注意 : 任一点最多与一个点不相邻, 此时 (G) 也必为 G ) 证明 : 设 V V G, 使得 G-V 含两个连通分支 G 1, G 2, 不妨设 G 1 G 2, 则 G 1 (n- V )/2 V G1 G 1 G v G1 d(v) G 1 ( G 1-1)+ G 1 V G G 1-1+ V (n- V )/2 + V -1 G2 2 G n-2 + V G + V, 所以 V G 所以 (G) G 25

26 连通度与点不相交的通路 ( 现象 : 对图 G 中任意两点 u,v, 如果点不相交的 uv- 通路有 k 条, 显然, 要使 u,v 不连通, 至少须删除 k 个顶点 ) Whitney 定理 : 图 G( G 3) 是 2- 连通图当且仅当 G 中任意两点被至少 2 条除端点外顶点不相交的路径所连接注意 : G 中任意两点被至少 2 条除端点外顶点不相交的路径所连接等价于任意两点均处在同一初级回路中 26

27 Whitney 定理的证明显然 : 设 u,v 是图 G 中的任意两点下面对距离 d(u,v) 进行归纳当 d(u,v)=1, uv E G, 因为 G 是 2- 连通图,G-uv 仍连通, 则 G 中除边 uv 外, 必有另一条不含 uv 的路径假设当 d(u,v)<k 时, 至少存在两条中间点不相交的通路若 d(u,v)=k, 设 u,v 间的一条最短路径是 u wv, w 是与 v 相邻的顶点则 d(u,w)<k, 由归纳假设 u,w 之间存在两条中间点不相交的路径, 设为 P, Q 因为 G 是 2- 连通图,G-w 中仍有 ( 不含 w 的 )uv- 路径 P, 且它一定与 P, Q 有公共点 (u 就是一个 ) 假设这样的公共点中距离 v 最近的是 x( 不妨假设它在 P 上 ), 则 Q+wv 边以及 P 上的 ux- 段 +P 上的 xv- 段是 u,v 之间两条中间点不相交的通路 27 u P Q x w v

28 连通性的一般性质 Menger 定理 (Whitney 定理的推广 ) 图 G 是 k- 连通图当且仅当 G 中任意两点被至少 k 条除端点外顶点不相交的路径所连接图 G 是 k- 边连通图当且仅当 G 中任意两点被至少 k 条边不相交的路径所连接 28

29 2- 连通图命题. 一个图是 2- 连通的它是一个回路 (cycle), 或者可在已有的 2- 连通图上依次增加 H-path 而得. 该通路有两个端点, 且仅仅这两个端点在原图上 29

30 2- 连通图证明. 充分条件显然成立. 下证必要条件. 设 G 是 2- 连通的. G 必包含回路 C, 设 H 是包含 C, 依次增加 H-Path 得到的极大子图. H 必是 G 的导出子图. 倘若 H G, 则存在 v G-H, w H, vw G. G 是 2- 连通的, G-w 连通, v 到 H 有路径 P, wvp 是 H-Path, 矛盾. v H w 30

31 2- 连通图 31

32 有向图的连通性若将有向图 D 各边的方向去掉, 所得的无向图 ( 称为 D 的底图 ) 连通, 则 D 称为弱连通有向图 ( 见下右图 : 既无 uv-, 又无 vu- 有向通路 ) u,v V D, 存在一条 (u,v)- 有向通路或者 (v,u)- 有向通路, 则 D 称为单连通有向图 ( 见下中图 : 有 uv-, 但无 vu- 有向通路 ) u,v V D, 均存在 (u,v)- 有向通路和 (v,u)- 有向通路, 则 D 称为强连通有向图 ( 见下左图 ) u u u v v v 32

33 强连通的充分必要条件有向图 D 是强连通的当且仅当 D 中的所有顶点在同一个有向回路上证明 : 显然设 V D ={v 1,v 2,,v n }, 令 i 是 v i 到 v i+1 的有向通路 (i=1,,n-1), 令 n 是 v n 到 v 1 的有向通路, 则 1, 2, n 依次连接是包含 D 中一切顶点的回路 33

34 单向连通图中处处可达的顶点若有向图 D 是单向连通, 则非空集 V' V D, v' V', 使得 v' 可达 V' 中的所有顶点 ( 规定顶点到其自身是可达的 ) 注意 : 当 V ' 足够小, 上述条件一定成立证明 :( 注意 : 按照非空子集的大小进行归纳证明 ) V? v i r v k 1 34

35 单向连通的充分必要条件有向图 D 是单向连通的当且仅当 D 中的所有顶点在同一个有向通路上充分性显然, 下面证明必要性设 V D ={v 1,v 2, v n }, 令 V 1 =V D, 则 V 1 中存在可达所有顶点的顶点, 不妨假设它就是 v 1, 令 V i+1 =V i -{v i }, 其中 i=1,2,,n-1; 而且诸 V i 中均有可达该子集中所有顶点的顶点 ( 不妨假设其就是 v i ), 于是 : 将诸 v i v i+1 - 通路连接起来即包含 D 中所有顶点的有向通路 35

36 无向图的边定向问题 : 何种道路网可以用规定单行道的办法来改善交通? 在图模型中, 该问题表述为 : 什么样的无向图 G 可通过边定向成强连通有向图. 显然 G 中不能有割边, 否则定向后, 割边端点之间不能双向可达因此,G 的 2- 边连通是个必要条件, 但它是否也是充分条件呢? 36

37 2- 边连通与 2- 连通 ( 无向图 ) v 3 v 2 v 1 37

38 2- 边连通无向图的边定向 2- 边连通图中一定含回路 C 1 v 3 v 2 P v 6 v 1 v 5 Q v 4 构作有向通路 C 2 =C 1 +QP,..., 总会得到包括图中所有点的强连通有向图仍未包括的边可以任意定向 38

39 无向图边定向算法输入 : 无环 2- 边连通无向图 G ( 设 V G ={v 1,v 2,,v n }) 输出 : 以 G 为底图的强连通有向图过程 : (1) 令 V 1 ={v 1 }, i=1 (2) 若 V i =V G, 对未定向边任意定向, 算法结束否则转 3 (3) 取边 v, 使得 v V v V V ( 一定可取到所要的边 ) v i v i v 0 i 1 i i i1 从开始找一条初级通路或回路, 满足始点和终点在 V i 中, 0 i 1 0, 而中间点均在 V G -V i 中, 加方向使之成为有向通路 (4) V i+1 =V i { 上述通路或回路中所有中间点 }, 转 2 G i 39

40 无向图边定向算法 ( 续 ) 示例 j a b h i c g f d e 40

41 作业见课程网站 41

42 参考文献 Reinhard Diestel. Graph Theory. Springer, Heidelberg, 2005 Section 1.3 and section

43 连通度的应用问题 : 将 n 个计算机连成一个通信网络以共享资源, 如果要以最小的代价保证在故障节点少于 k 个的条件下所有计算机能保持互连, 网络应该如何连接? 数学模型 : 找出 n 个结点的完全图的一个边最少的 k- 连通子图 ( 注意 : 含 n 个顶点的 k- 连通图至少有 nk/2 条边, 因为该图中最小顶点度不能小于 k) 这个问题的一般形式 : 若 G 是带权图, 对给定的正整数 k, 确定 G 的最小 k- 连通生成子图被认为是一个 NP- 完全问题 43

44 Harary 的解 :H k,n H 5,8 k 是奇数 n 是偶数 H 4,8 k, n 均是偶数 H 5,9 k 是奇数 n 也是奇数 44

45 证明的思路以这一较简单的情况为例 1. 前已说明 : 含 n 个顶点的 k- 连通图至少有 nk/2 条边 2. 左边的解恰好是 nk/2 条边 0 3. 因此, 只须证明, 这图是 k- 连通的 H k,n k,n 均是偶数令 k=2r (r 是整数 ) 不失一般性, 假设 S V <r; 则有 : 要么 v i 与 v j 直接相邻 ; 要么存在 v i1 在 v i 与 v j 之间使得 v i 与 v i1 直接相邻 j (i-r) mod ; 接下来以同样方式 n 或 j (i+r) mod n 考虑 v i1 与 v j 之间的连通性 ; 直至找到 v i v i1 v it v j 通路对任意顶点 i, 让它与满足下述条件的顶点 j 相连 : 于是, 如果两点取模差不大于 r, 则相连. 假设从图中删除少于 2r 个顶点 ( 构成子集 V ), 图就不连通了, 删除后, 顶点 i,j 属不同的分支. 考虑两个子集合 ( 这里的序号对 n 取模 ): S={i,i+1,, j-1, j}; T={j, j+1,, i-1, i} 由于 V 中元素个数小于 2r, 这两集合中至少有一个含 V 中的元素少于 r 个, 则此集合中删除 V 后仍构成一 ij- 45 通路, 矛盾

PowerPoint 演示文稿

PowerPoint 演示文稿图的连通性 1 回顾 2 图的定义用图建模图的表示图的运算图的同构提要 3 通路与回路无向图的连通性连通度 2- 连通图有向图的连通性无向图的定向通路的定义 4 定义 : 图 G 中从 v 0 到 v n 的长度为 n 的通路是 G 的 n 条边 e 1,, e n 的序列, 满足下列性质存在 v i V (0 i n), 使得 v i-1 和 v i 是 e i 的两个端点