计算机问题求解 – 论题3-10 - 图的连通度 2018年11月13日.

Presentation on theme: "计算机问题求解 – 论题3-10 - 图的连通度 2018年11月13日."— Presentation transcript:

1 计算机问题求解 – 论题 图的连通度 2018年11月13日

2 “连通”并不都是一样的 问题1: 你能否解释一下它们的“连通” 怎么不一样? 割点、割边与回路

3 问题2： 衡量连通的“牢度”的指 标是什么？

4 指标1：minimum vertex-cut
By a vertex-cut in a graph G, we mean a set U of vertices of G such that G - U is disconnected. A vertex-cut of minimum cardinality in G is called a minimum vertex-cut.  问题3： 你应该了解割点是什么？围绕割点，有哪些有趣的现象

5 围绕割点的若干结论

6 围绕割点的重要概念之一：不可分割 A graph of order at least 3 is nonseparable if and only if every two vertices lie on a common cycle 充分条件 显然，删除任意一点，均不能使得任意两点不连通 必要条件：反正法 找到不成回路的最短uv路径P 令vk-1是v的直接前驱节点 u, vk-1有回路C 删去vk-1 ，u和v仍然相连:Q 令x是C和Q的第一个交点 构造P’,Q’,可以形成ux+Q’+P’的uv回路

7 问题4：从这个定理及证明中能否看出，不可分离图在外表上具有什么共性？
围绕割点的重要概念之二：Block 问题4：从这个定理及证明中能否看出，不可分离图在外表上具有什么共性？ 重重叠叠的环交织而成！

8 A maximal nonseparable subgraph of a graph G is called a block of G.
极大还是最大？

9 关于block的几个理解 Theorem 5.8 Let R be the relation defined on the edge set of a nontrivial connected graph G by e R f, where e, f ∈E(G), if e = f or e and f lie on a common cycle of G. Then R is an equivalence relation. 用等价关系来描述边之间的关系，到底有何用意？ 问题6：Block的“极大”特性和“等价类”有何关系？ 等价类特性保证了“极大”特性 Each subgraph of G induced by the edges in an equivalence class is in fact a block of G.

10 问题7： 两个block的“边界”是什 么？

11 问题7： 两个block的“边界”是什 么？ Corollary 5.9 Every two distinct blocks B1 and B2 in a nontrivial connected graph G have the following properties: (a) The blocks B1 and B2 are edge-disjoint. (b) The blocks B1 and B2 have at most one vertex in common. (c) If B1 and B2 have a vertex v in common, then v is a cut-vertex of G.

12 最小点割集的势 点连通度K(G) 问题9： 问题8： 从一个k-连通图中删除k个点，剩下的图是否一定不连通了？
kappa 问题9： Block和2-连通图是什么关系？

13 问题10： 边连通度是什么概念？ 我们能够简称4边连通度图为4连通图吗？ 2连通必定不可分离，必定是个block

14 Whitney定理 Theorem 5.11 For every graph G,
Case1：否定G1和G2中每个点都连通，为case2做准备 u v x1 x2 x3 x4 G1 G2 遍历边割集中的边，删去其中一点，构造边割集：连接u的边，选该边的G2子图点，否则选该边的G1子图点

15 Whitney定理 Theorem 5.11 For every graph G,
证明K小于等于λ的case2的基本思路：在最小边割集的两侧选一对不直接相邻的点，考虑如何“切断”它们之间的通路。 u G1 G2 x2 x1 遍历边割集中的边，删去其中一点，构造边割集：连接u的边，选该边的G2子图点，否则选该边的G1子图点 x3 x4 v

16 点连通度和图的边、点数关系 问题11：如何理解 The bound given in Theorem 5.13 is sharp
Theorem 5.13 If G is a graph of order n and size m >=n - 1, then The bound given in Theorem 5.13 is sharp 问题11：如何理解 针对任意满足条件的n,m，都有一个图，其点连通度等于右值

17 Harary图：一种特殊的连通度接近2m/n的图
图G的k次幂：

18 图例：

19 计算机网络 – 一个应用的例子 问题: 将n个计算机连成一个通信网络以共享资源，如果要以最小的代价（假设以链路条数计）保证在故障节点少于k个的条件下所有计算机能保持互连，网络应该如何连接？ 数学模型：找出n个结点的完全图的一个边最少的r- 连通子图。 （注意：含n个顶点的r-连通图至少有nr/2条边，因为 该图中最小顶点次数不能小于r）

20 Harary的解：Hr,n Hr,n一定包含一个Cn；

21 Harary的解：Hr,n Hr,n一定包含一个Cn； 当r=2k时： Hr,n =Cnk： H4,8

22 H5,8 Harary的解：Hr,n Hr,n一定包含一个Cn； 当r=2k时： Hr,n =Cnk：
当r=2k+1，n=2l 时： Hr,n =Cnk+{vivi+l |i=1，l } H5,8

23 H5,9 Hr,n一定包含一个Cn； 当r=2k时： Hr,n =Cnk：
当r=2k+1，n=2l 时： Hr,n =Cnk+{vivi+l |i=1，l } 当r=2k+1，n=2l+1 时：Hr,n =Cnk+{vivi+l+1 |i=1，l }+{v1v1+l } H5,9

24 Harary图离正则图有多远？ Harary的解：Hr,n Hr,n一定包含一个Cn； 当r=2k时： Hr,n =Cnk：
当r=2k+1，n=2l 时： Hr,n =Cnk+{vivi+l |i=1，l } 当r=2k+1，n=2l+1 时：Hr,n =Cnk+{vivi+l+1 |i=1，l }+{v1v1+l } 只有第三种情况不是正则图 Harary图离正则图有多远？

25 指标2：multiplicity of alternative paths
How many internally disjoint paths are there to link any pair of vertex u,v in graph G? 两种指标本质上是一样的。 对图G中任意两点u,v, 如果点不相交的uv-通路有k条，显然，要使u,v不连通， 至少须删除k个顶点。

26 Menger theorem Let u and v be nonadjacent vertices in a graph G. The minimum number of vertices in a u-v separating set equals the maximum number of internally disjoint u-v paths in G. 证明要点： 1，对图的边数(size)进行归纳； 2，对“分离点集”中的点的特殊性进行分别分析： 1）存在和uv直接相邻的点； 2）同时存在一个不和u相邻的点以及存在一个不和v相邻的点 3）所有的点要么和u相邻，要么和v相邻

27 证明：最小分离点集，最大内部不相交路径数
奠基：m=0,1,2时，显然成立。(k=0,1时成立，因此可以讨论k>1) 假设：G的size小于m时，最小分离点集势等于最大内部不相交路径数 归纳：当G的size=m时： 三种情况分别讨论

28 Case1：存在节点x，构成(u,x,v)路径
G-x的最小分离点集势为k-1 G-x的最大内部不相交路径为k-1 恢复x，结论成立 c x u … v

29 Case2:分离点集中存在一个和u不相邻的点以及不和v相邻的点
1)构造Gu和Gu’,Gv和Gv’图 2)Gu’和Gv’满足归纳假设，最大最小相等为k 3)原G图结论归纳成立 假设wi不和v相邻，p(wi,v)至少两条边，Gu’就至少少一条边 要点：Since W contains a vertex that is not adjacent to u and a vertex that is not adjacent to v, the size of each of the graphs G’u and G’v is less than m.

30 Case3:所有的点，要么只和u相邻，要么只和v相邻
考察uv最短路上的边e，考察G-e： 适用归纳假设 G-e的最大最小相等成立 至少是k-1 G-e中最小分割集一定是k ？ G-e中存在k条不相交uv路 G中也有k条不相交uv路 归纳结论成立 c x y e u … v 在G-e中，最小分离点集至少为k-1 S集合中，去掉x，加上y，依然构成k分离点集，此时y必定和U相邻，uy….v成立，路径更短 S集合

31 G-e中最小分割集一定是k？ 假设是k-1： 找到G-e中某个最小分割集Z： Z的势为k-1 Z中元素只均和u相邻，不和v相邻
Z+{x}是G中最小分割集集合 Z+{y}是G中最小分割集集合 y应该和u相邻 (u,y,…,v)路径成立 (u,x,y, …v)就不是最短 c y u x … v Z集合：G-e的最小分割集

32 图示Menger定理

33 由Menger定理引出的系列结论

34 Open Topics 学习并介绍图的block寻找算法； 尝试证明harary图确实是r连通的