图的连通度问题
- 格式：docx
- 大小：40.32 KB
- 文档页数：6
1012005国家集训队作业：图的连通度问题研究 长郡中学任恺
图的连通度问题研究
1 •图的连通度的定义
图要么是连通的，要么是不连通的。但对于任意连通图来说，它们的连通程 度也可能是不同的。为了精确地体现连通的程度，下面将引入两个概念：边连通 度和顶点连通度。
设G = (V, E)是一个n阶图。如果G是完全图Kn,那么我们定义它的顶点连 通度为
KKn) = n T
否则，定义它的顶点连通度为
KG) = min{| U| : Gv-u是非连通的}
即最小顶点数，删除这些顶点便是非连通图。
图G的边连通度定义为从图G中删除边而使G非连通的最小边数，用 XG) 表示。
这里的图G=(V, E)代表无向图或有向图，且没有自环和重边。
下面将主要讨论无向图的边连通度， 有向图的边连通度和顶点连通图可以以 此类推。
2 •无向图的边连通度
在无向图G中，令顶点v的度数deg(v)表示与顶点v相连的边的数目。无向 图G的最小度＜G)定义为：/G) = min{deg( v) | v属于G}。考虑有向图G中，v 的入度表示为in-deg(v)，v的出度表示为 out-deg(v)，相应的最小度为：＜G)= min{in-deg(v), out-deg(v)| v属于G}。在整篇文章中，图的点数用n表示，边数用 m表示。
另u和v表示图G中的一对不相同的点。定义Xu, v)表示从图G中删除最少 的边，使得u和v之间不存在任何路径。在有向图 G中，Xu, v)表示从G中删除 最少的弧(有向边)，使得不存在任何从u到v的有向路径。注意到，在无向图中， 有Xu,
v) = Xv, u)，在有向图中却不符合这个等式。
显然，Xu, v)就是图中u和v的最小割。求两点之间的最小割，根据最大流 最小1012005国家集训队作业：图的连通度问题研究 长郡中学任恺
割定理，可以用最大流算法求解：令 u为网络的源点，V为网络的汇点，每 条边的容量为1, u到V的最大流便是u和V之间的最小割。预流推进算法可以 在0(nm)时间复杂度下求出最大流。另外，每条边的容量都为1,可以用Hoproft
算法在0(nm)的时间复杂度下求出单位容量网络的最大流。具体算法的实现不 在本文讨论范围之内，这里不再赘述。
显然，图G的2(G)即所有点对的Xu, v)的最小值。对于有n个点的无向图中，
有n(n-1)/2个无序点对需要计算，而在有向图中有 n(n-1)个有序点对需要计算。 然而，经过证明，计算 XG)，远远不需要枚举这么多点对计算 Xu, v)。
图1
在图1中，L和R分别表示被S分割开的两个点集，不妨叫L位于S的左侧， R位于S的右侧。注意到，u为位于S一侧的任意一个顶点，那么至少存在一个 顶点v在S的另一侧，使得Xu, v) = XG)。因此可以按如下方法求出 XG)：
算法1
输入图G = (V, E)
1•令u为V中任意一个顶点，令X = V -{u}。
2. 枚举X中的所有点v,用网络流求出Xu, v)。
3. 贝U XG) min{ Xu, v) | v X }。
继续观察图1,如果能找到一个集合 Y,满足Y既包含L中的点又包含R中 的点，即丫 n L工？且丫 n R工？，那么就能把算法一第一步中的 V替换成Y, 仍能求得正确的XG)。这样一个集合Y,叫做图G的入覆盖(X -covering)。显然, T越小，需要求网络流的次数越少。下面的分析将得到一个新的算法。
定理1 : 1012005国家集训队作业：图的连通度问题研究 长郡中学任恺
如果 g < &G)那么有 |L| > S 且 |R| > 3( S= 8(G))
证明：
设L = {V1, V2,…,Vk}，显然有
deg(vi) + deg(V2)+…+degVk) >= k 8 (1)
同样有
deg(vi)+deg(v2)+ …+degVk) = 2|E()| + |S| (2)
这里，|E()|表示点集L包含的所有边的集合。
(1)(2)两式的等号成立，当且仅当是完全图的情况。因此联合 (1) ,(2)两式可以
得到 8k
因为S|=XG) < 8(G),所以有8k < k(k -1) + 8又因为L > 1即k >1(否则XG)
=8G))，所以不等式两边同除以(k -1),得到k > 8,即有|L| > 8。
同理可以证明 R| >8
根据定理1,可以得到下面的一些推论：
推论1 :
当XG) < 8(G)时，那么L中至少存在一个点与S中的边不直接相连，R也同
样。
推论1显然成立，否则|L| = 8。推论1也说明在这个情况下，图的直径大于 等于3。
推论2 :
T为G的一个生成树，丫是T的非叶子顶点集合。如果2(G) < /G)，那么丫 是G的一个入覆盖，也就是说L, R中至少有一个点在丫中。
分析：若L中顶点都是丫中的叶子顶点，那么就有|L| = SI = 8矛盾。
由推论2可以得到算法2：
算法2：
1 •找到一棵生成树T, 丫是T的非叶子顶点集合。
2. 任选一个 u, X = 丫 /{u}。
3•对于所有V属于X,求出2u, V)。1012005国家集训队作业：图的连通度问题研究 长郡中学任恺
4. c = min「(u,v) |v = X』
5. 入G) = min{c, SG)}
容易证明算法2的正确性：如果2(G) < SG),那么丫是G的一个入覆盖，则 c便是2G);否则2G) = SG)，步骤5将得到正确答案。然而，求一个叶子顶点 最少的生成树是NP-难问题。因此算法2比较算法1的优势是，仅仅减少了 2u, v)的计算量，而并没有降低时间复杂度的级别。
下面介绍一种另一种求解较小的 入覆盖方法，也是基于生成树的。注意到推
论2的证明也说明了当2(G) < SG)丄或R集合不可能只包含生成树的叶子顶点。 也就是说在2G) < SG)的情况下，令丫为生成树T的非叶子顶点集合，那么 丫 和V(T)都是图G的一个入覆盖。下面的算法中，对于 G中的任意顶点u，I(u)所 有与u相邻的边的集合，A(u)表示所有与u相邻的顶点集合。
算法3
输入：图G
输出：生成树H(V, E)
1. 令 V(H) ?，E(H) ?。
2. 任选一个顶点，V(H) {u} A(u)，E(H) l(u)。
3. 选择H中的一个叶子结点 w，对于所有 H中的叶子结点 r，满足
|A(w) - (V(G) -V(H))| | A(r) - (V(G)-V(H)) |。
4. 对于所有v A(wr (V(G) -V(H ))，把v加入V(H)，把边wv加入E(H)。
5. 如果|E(H)| < V(H)| - 1，那么转第3步，否则算法终止。
算法3是用贪心的方法生成叶子结点尽量多的生成树。由此可以得到求2G) 的另一个算法：
算法4：
1. 用算法3找到一棵生成树H , 丫是H的非叶子顶点集合。
2. 任选一个 u,若|Y| < V(H) -Y|，贝U X = Y /{u}，否则 X = (V(H) — )/{u}
3. 对于所有v属于X，求出2u, v)。 1012005国家集训队作业：图的连通度问题研究 长郡中学任恺
4. c = min • (u,v) |v X f
5. 入G) = min{c, SG)}
根据算法第2步可以知道，算法4最多进行n / 2次网络流求解2(u, V)。
还可以利用定理1和支配集改善了边连通度的算法。在图 G=(V, E)中，集合 D V叫做支配集，当且仅当对于 V中的任意点u,要么u属于D，要么和G中 的一个顶点相邻。
推论3
设D为G的一个支配集，当 入G) v^G),那么D是G的一个入覆盖，也就 是说L, R中至少有一个点在D中。
因为根据推论1可以知道，当入G)
因此可以用贪心的方法求出极小支配集， 然后利用与算法2类似的方法求出 边连通度。根据均摊计算 D中的每个顶点的Xu, v)的复杂度，Matual能够将求 解XG)总的时间复杂度降到0(nm)。具体的实现和证明方法，由于缺乏资料，所 以这里不能够提供，有兴趣的读者请上网寻找 Matual的论文(我没有找到 )。
三、图的连通度的一些研究成果
Deciding Author(s) Yea
r Complexity Comments
Edge Connectivity
Z = 2 or Z = 3 Tarja n 1972 0(m + n) uses Depth First Search
A Eve n and Tarja n] 1975 1/2 2/3
0(mn 汽 min{ m , n }) n calls to max-flow
Z (digraphs) Sch norr 1979 O(Xmn) n calls to max-flow
k Esfaha nian & Hakimi 1984 O(Xmn) 兰 n/2 calls to max-flow
Z (digraphs) Esfaha nian & Hakimi 1984 O(Xmn) 兰 n/2 calls to max-flow
扎 Matula 1987 0(m n) uses domin ati ng sets
Z = k Matula 1987 0(k n2)
Z (digraphs) Man sour & Schieber 1989 0(m n)
?. = k Gabow 1991 2 0(m+k nlog( n/k)) Uses matroids
Vertex Connectivity
K = 2 Tarja n 1972 0(m + n) uses Depth First Search
瓷=3 Hopcroft & Tarja n 1973 0(m + n) uses tric onn ected
comp onents
K Eve n & Traja n 1975 0((%n — -1) mn ) max-flow based
