《图的连通度问题.pdf》由会员分享，可在线阅读，更多相关《图的连通度问题.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、IOI2005 国家集训队作业：图的连通度问题研究 长郡中学 任恺 图的连通度问题研究 1图的连通度的定义 图要么是连通的，要么是不连通的。但对于任意连通图来说，它们的连通程度也可能是不同的。为了精确地体现连通的程度，下面将引入两个概念：边连通度和顶点连通度。设 G=(V,E)是一个 n 阶图。如果 G 是完全图 Kn，那么我们定义它的顶点连通度为(Kn)=n 1 否则，定义它的顶点连通度为(G)=min|U|:Gv-u是非连通的 即最小顶点数，删除这些顶点便是非连通图。图 G 的边连通度定义为从图 G 中删除边而使 G 非连通的最小边数，用(G)表示。这里的图 G=(V,E)代表无向图或有向
2、图，且没有自环和重边。下面将主要讨论无向图的边连通度，有向图的边连通度和顶点连通图可以以此类推。2无向图的边连通度 在无向图 G 中，令顶点 v 的度数 deg(v)表示与顶点 v 相连的边的数目。无向图 G 的最小度(G)定义为：(G)=mindeg(v)|v 属于 G。考虑有向图 G 中，v的入度表示为 in-deg(v)，v 的出度表示为 out-deg(v)，相应的最小度为：(G)=minin-deg(v),out-deg(v)|v 属于 G。在整篇文章中，图的点数用 n 表示，边数用m 表示。另 u 和 v 表示图 G 中的一对不相同的点。定义(u,v)表示从图 G 中删除最少的边，
3、使得 u 和 v 之间不存在任何路径。在有向图 G 中，(u,v)表示从 G 中删除最少的弧(有向边)，使得不存在任何从 u 到 v 的有向路径。注意到，在无向图中，有(u,v)=(v,u)，在有向图中却不符合这个等式。显然，(u,v)就是图中 u 和 v 的最小割。求两点之间的最小割，根据最大流IOI2005 国家集训队作业：图的连通度问题研究 长郡中学 任恺 最小割定理，可以用最大流算法求解：令 u 为网络的源点，v 为网络的汇点，每条边的容量为 1，u 到 v 的最大流便是 u 和 v 之间的最小割。预流推进算法可以在 O(nm)时间复杂度下求出最大流。另外，每条边的容量都为 1，可以用
4、 Hoproft算法在()Onm的时间复杂度下求出单位容量网络的最大流。具体算法的实现不在本文讨论范围之内，这里不再赘述。显然，图 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 一侧的任意一个顶点，那
5、么至少存在一个顶点 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)|vX。继续观察图 1，如果能找到一个集合 Y，满足 Y 既包含 L 中的点又包含 R 中的点，即 Y L 且 Y R ，那么就能把算法一第一步中的 V 替换成 Y，仍能求得正确的(G)。这样一个集合 Y，叫做图 G 的 覆盖(covering)。显然，T 越小，需要求网络流的次数越少。下面的分析将得到一个新的算法。IOI2005 国家集训队作
6、业：图的连通度问题研究 长郡中学 任恺 定理 1：如果(G)且|R|(=(G)证明：设 L=v1,v2,vk，显然有 deg(v1)+deg(v2)+deg(vk)=k (1)同样有 deg(v1)+deg(v2)+deg(vk)=2|E()|+|S|(2)这里，|E()|表示点集 L 包含的所有边的集合。(1)(2)两式的等号成立，当且仅当是完全图的情况。因此联合(1),(2)两式可以得到 k k(k 1)+|S|。因为|S|=(G)(G)，所以有 k 1 即 k 1(否则(G)=(G)，所以不等式两边同除以(k 1)，得到 k ，即有|L|。同理可以证明|R|。根据定理 1，可以得到下面的
7、一些推论：推论 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)。IOI2005
8、国家集训队作业：图的连通度问题研究 长郡中学 任恺 4Xvvuc|),(min 5(G)=minc,(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 的非叶
9、子顶点集合，那么 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)(uAu，E(H)I(u)。3选择 H 中的一个叶子结点 w，对于所有 H 中的叶子结点 r，满足|)()()(|)()()(|HVGVrAHVGVwA。4对于所有)()()(HVGVwAv，把 v 加入 V(H)，把边 wv 加入 E(H)。5如果|E(H)|V(H)|-1，那么转第 3 步，否则算法终止。算法 3 是用
10、贪心的方法生成叶子结点尽量多的生成树。由此可以得到求(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)。4Xvvuc|),(min IOI2005 国家集训队作业：图的连通度问题研究 长郡中学 任恺 5(G)=minc,(G)根据算法第 2 步可以知道，算法 4 最多进行 n/2 次网络流求解(u,v)。还可以利用定理 1 和支配集改善了边连通度的算法。在图 G=(V,E)中，集合VD叫做支配集，当且仅当对于 V 中的任意点 u
11、，要么 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)。具体的实现和证明方法，由于缺乏资料，所以这里不能够提
12、供，有兴趣的读者请上网寻找 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 minm1/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 ca
13、lls 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 1
14、973 O(m+n)uses triconnected components Even&Trajan 1975 O(n 1)mn2/3)max-flow based IOI2005 国家集训队作业：图的连通度问题研究 长郡中学 任恺 =k Even 1975 O(kn3)max-flow based Galil 1980 O(min,n2/3mn)max-flow based =k Galil 1980 O(mink,n1/2kmn)max-flow based Becker,et el.1982 probabilistic algorithm Esfahanian&Hakimi 1984 O
15、(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 AbdolHossein Esfahanian