图的连通度问题研究
1．图的连通度的定义
图要么是连通的，要么是不连通的。但对于任意连通图来说，它们的连通程度也可能是不同的。为了精确地体现连通的程度，下面将引入两个概念：边连通度和顶点连通度。 设G = (V, E)是一个n阶图。如果G是完全图Kn，那么我们定义它的顶点连通度为
κ(Kn) = n – 1
否则，定义它的顶点连通度为
κ(G) = min{|U| : Gv-u是非连通的}
即最小顶点数，删除这些顶点便是非连通图。
图G的边连通度定义为从图G中删除边而使G非连通的最小边数，用λ(G)表示。
这里的图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中的一对不相同的点。定义λ(u, v)表示从图G中删除最少的边，使得u和v之间不存在任何路径。在有向图G中，λ(u, v)表示从G中删除最少的弧(有向边)，使得不存在任何从u到v的有向路径。注意到，在无向图中，有λ(u, v) =λ(v, u)，在有向图中却不符合这个等式。
显然，λ(u, v)就是图中u和v的最小割。求两点之间的最小割，根据最大流最小割定理，可以用最大流算法求解：令u为网络的源点，v为网络的汇点，每条边的容量为1，u到v的最大流便是u和v之间的最小割。预流推进算法可以在O(nm)时间复杂度下求出最大流。另外，每条边的容量都为1，可以用Hoproft算法在的时间复杂度下求出单位容量网络的最大流。具体算法的实现不在本文讨论范围之内，这里不再赘述。 显然，图G的λ(G)即所有点对的λ(u, v)的最小值。对于有n个点的无向图中，有n(n-1)/2个无序点对需要计算，而在有向图中有n(n-1)个有序点对需要计算。然而，经过证明，计算λ(G)，远远不需要枚举这么多点对计算λ(u, v)。
考虑如下一个连通图G的抽象图，令S为图G中的一个最小边割集。
图1
在图1中，L和R分别表示被S分割开的两个点集，不妨叫L位于S的左侧，R位于S的右侧。注意到，u为位于S一侧的任意一个顶点，那么至少存在一个顶点v在S的另一侧，使得λ(u, v) =λ(G)。因此可以按如下方法求出λ(G)： 算法1
输入图G = (V, E)
1． 令u为V中任意一个顶点，令X = V – {u}。
2． 枚举X中的所有点v，用网络流求出λ(u, v)。
3． 则λ(G) min{λ(u, v) | }。
继续观察图1，如果能到一个集合Y，满足Y既包含L中的点又包含R中的点，即Y ∩ L ≠ Ø 且Y ∩ R ≠ Ø，那么就能把算法一第一步中的V替换成Y，仍能求得正确的λ(G)。这样一个集合Y，叫做图G的λ覆盖(λ – covering)。显然，T越小，需要求网络流的次数越少。下面
的分析将得到一个新的算法。
定理1：
如果λ(G) < δ(G) 那么有|L| > δ 且 |R| > δ (δ = δ(G))
证明：
设L = {v1, v2, …,vk}，显然有
deg(v1) + deg(v2)+…+deg(vk) >= k·δ (1)
同样有
deg(v1)+deg(v2)+…+deg(vk) = 2|E(<L>)| + |S| (2)
这里，|E(<L>)|表示点集L包含的所有边的集合。
(1)(2)两式的等号成立，当且仅当是完全图的情况。因此联合(1),(2)两式可以得到δ·k ≤ k(k – 1) + 中国红歌会|S|。
因为|S|=λ(G) < δ(G)，所以有δ·k < k(k – 1) + δ。又因为L > 1即k >1(否则λ(G) = δ(G))，所以不等式两边同除以(k – 1)，得到k > δ，即有 |L| > δ 。
同理可以证明 |R| >δ。
根据定理1，可以得到下面的一些推论：
推论1 ：
当λ(G) < δ(G)时，那么L中至少存在一个点与S中的边不直接相连，R也同样。
推论1显然成立，否则|L| = δ。推论1也说明在这个情况下，图的直径大于等于3。
推论2 ：
T为G的一个生成树，Y是T的非叶子顶点集合。如果λ(G) < δ(G)，那么Y是G的一个λ覆盖，也就是说L，R中至少有一个点在Y中。 分析：若L中顶点都是Y中的叶子顶点，那么就有|L| = |S| = δ，矛盾。
由推论2可以得到算法抗拉强度计算2：
算法2：
1．到一棵生成树T，Y是T的非叶子顶点集合。
2．任选一个u，X = Y /{u}。
3．对于所有v 属于X，求出λ(u, v)。
4．
5．λ(G) = min{c, δ(G)}
容易证明算法2的正确性：如果λ(G) < δ(G)，那么Y是G的一个λ覆盖，则c便是λ(G)；否则λ(G) = δ(G)，步骤5将得到正确答案。然而，求一个叶子顶点最少的生成树是NP-难问题。因此算法2比较算法1的优势是，仅仅减少了λ(u, v)的计算量，而并没有降低时间复杂度的级别。
下面介绍一种另一种求解较小的λ覆盖方法，也是基于生成树的。注意到推论2的证明也说明了当λ(G) < δ(G)，L或R集合不可能只包含生成树的叶子顶点。也就是说在λ(G) < δ(G)的情况下，令Y为生成树T的非叶子顶点集合，那么Y和V(T)都是图G的一个λ覆盖。下面的算法中，对于G中的任意顶点u，I(u)所有与u相邻的边的集合，A(u)表示所有与u相邻的顶点集合。
算法3俄勒冈州火山爆发
输入：图G
输出：生成树H(V, E)
1． 令V(H) Ø，E(H) Ø。
2． 任选一个顶点，V(H) ，E(H) I(u)。
3． 选择H中的一个叶子结点w，对于所有H中的叶子结点r，满足。
4． 对于所有，把v加入V(H)，把边wv加入E(H)。
5． 如果|E(H)| < |V(H)| - 1，那么转第3步，否则算法终止。
算法3是用贪心的方法生成叶子结点尽量多的生成树。由此可以得到求λ(G)的另一个算法：
算法4：
1．用算法3到一棵生成树H，Y是H的非叶子顶点集合。
2．任选一个u，若|Y| < |V(H) – Y|，则X = Y /{u}，否则X = (V(H) – Y )/{u}
3．对于所有v 属于X，求出λ(u, v)。
4．
5．λ(G) = min{c, δ(G)}
根据算法第2步可以知道，算法4最多进行n / 2次网络流求解λ(u, v)。
还可以利用定理1和支配集改善了边连通度的算法。在图G=(V, E)中，集合叫做支配集，当且仅当对于V中的任意点u，要么u属于D，要么和G中的一个顶点相邻。
推论3
设D为G的一个支配集，当λ(G) <δ(G)，那么D是G的一个λ覆盖，也就是说L，R中至少有一个点在D中。
因为根据推论1可以知道，当λ(G) <δ(G)时，L和R中至少存在一个点与S中的边不直接相连，因此若D只属于L或R，那么另一侧集合中至少有一个顶点不被支配。
因此可以用贪心的方法求出极小支配集，然后利用与算法2类似的方法求出边连通度。根据均摊计算D中的每个顶点的λ(u, v)的复杂度，Matual能够将求解λ(G)总的时间复杂度降到O(nm)。具体的实现和证明方法，由于缺乏资料，所以这里不能够提供，有兴趣的读者请上网寻Matual的论文（我没有到）。
三、图的连通度的一些研究成果
Deciding | Author(s) | Year | Complexity | Comments |
Edge Connectivity |
= 2 or = 3 | Tarjan | 1972 | O(m + n) | uses Depth First Search |
| Even and Tarjan] | 1975 | O(mn min{m1/2, n2/3}) | n calls to max-flow |
(digraphs)大头蚁属 | Schnorr | 1979 | O(mn) | n calls to max-flow |
| Esfahanian & Hakimi | 1984 | O(mn) | n/2 calls to max-flow |
(digraphs) | Esfahanian & Hakimi | 1984 | O(mn) | n/2 calls to max-flow |
| Matula | 1987 | O(mn) | uses dominating sets |
= k | Matula | 1987 | O(kn2) | |
(digraphs) | Mansour & Schieber | 1989 | O(mn) | |
= k | Gabow | 1991 | O(m+k2nlog(n/k)) | Uses matroids |
Vertex Connectivity |
= 2 | Tarjan | 1972 | O(m + n) | uses Depth First Search |
= 3 | Hopcroft & Tarjan | 1973 | O(m + n足菌肿) | uses triconnected components |
| Even & Trajan | 1975 | O(((n – – 1)mn2/3) | max-flow based |
= k | Even | 1975 | O(kn3) | max-flow based |
| Galil | 1980 | O(min{, n2/3}mn) | max-flow based |
加密代理 = k | Galil | 1980 | O(min{k, n1/2}kmn) | max-flow based |
| Becker, et el. | 1982 | | probabilistic algorithm |
| Esfahanian & Hakimi | 1984 | O(( n – – 1 + ( – 1)/2)mn2/3) | max-flow based |
= 4 | Kanevsky & Ramachandran | 1991 | O(n2) | |
= k | Cheriyan & Thurimella | 1991 | O(k3n2) | |
| Henzinger & Rao | 1996 | O(mnlogn) | randomised algorithm |
| | | | |
四、总结
大部分关于图连通度的算法都是几乎基于网络流的。算法4和支配集的算法，经过实践，对于n < 500的随机数据都很快。但存在一些极端情况：如非叶子结点个数为n/2的树等等。如果在实践过程利用增广路算法求解λ(u, v)，将会比预流推进算法更好，因为总是求λ(u, v)的最小值，所以可以利用δ(G)和已求出的λ(u, v)进行限界，而且可以避免某些极端情况。
很可惜的是，没有能在网络上到Matula目前最优算法的论文。
参考文献
《On the Evolution of Graph Connectivity Algorithms》
Abdol–Hossein Esfahanian
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议