图的匹配问题与最大流问题（四）计算图的边连通度和点连通度

图的匹配问题与最大流问题（四）计算图的边连通度和点连通度2015-09-02最近有点忙，好久没跟进了，有兴趣的朋友可以先熟悉下前三篇文章内容，（一）讲述了基础概念；（二）介绍了最大流算法的实现原理以及证明；（三）用Java语言予以了实现，欢迎大家批评指正。

回到正题，首先介绍下什么是图的边连通度和点连通度。一般来说，点连通度是指对应一个图G，对于所有点集U属于V（G），也就是V（G）的子集中，使得G-U要么是一个非连通图，要么就是一个平凡图（即仅包含一个独立点的图），其中最小的集合U的大小就是图G的点连通度，有时候也直接称为图的连通度。通俗点说，就是一个图G最少要去掉多少个点会变成非连通图或者平凡图。当然对于一个完全图来说Kn来说，它的连通度就是n-1。

同理，边连通度就是对于一个非平凡图G，至少去掉多少条边才能使得该图变成非连通图。我们的问题就是，对于任意一个图，如何求该图的连通度以及边连通度？这跟最大流问题有什么联系？

简单起见，我们先说如何求一个图的边连通度lamda（G）。（基于无向图考虑）

对于图G，设u，v是图G上的两个顶点，定义r（u，v）为删除最少的边，使得u到v之间没有通路。将图G转换成一个流网络H，u为源点，v是汇点，边容量均为1，那么显然r（u，v）就是流网络的最小割，根据（二）里的介绍，其等于流网络的最大流。

但是，目前为止我们还没解决完问题，因为显然我们要求的边连通度lamda（G）是所有的点对<u,v>对应的r（u，v）中最小的那个值。这样的话我们就必须遍历所有的点对，遍历的的复杂度为O（n*n）。这显然代价太高，而事实上，我们也不必遍历所有点对。

如图所示，设S为图G的最小割集，那么lamda（G）=|S|。设在取任意一个点u，若u在L内，那么必然至少存在一个点v，使得r（u，v）=|S|（v是在R内时即成立）。所以，我们只需要任取一个点u，计算u和其他点的r（u，v），取最小者，必然是等于最小割集，即边连通度。

public class EdgeConnectivity {/*** @param args*/public static void main（String[] args） {double graph[][]={{0,1,0,1,0,0},{1,0,1,0,1,0},{0,1,0,0,0,1},{1,0,0,0,1,0},{0,1,0,1,0,1},{0,0,1,0,1,0}};double graph2[][]={{0,1,1,1,1,1},{1,0,1,1,1,1},{1,1,0,1,1,1},{1,1,1,0,1,1},{1,1,1,1,0,1},{1,1,1,1,1,0}};System.out.println（edgeConnectivity（graph2））;}public static int edgeConnectivity（double graph[][]）{double min=Double.MAX_VALUE;for（int i=1;i<graph.length;i++）{double maxflow=FordFulkerson.edmondsKarpMaxFlow（graph, 0, i）;if（maxflow<min）min=maxflow;}return （int）min;}}

对于点连通度来说，可能就要复杂点了。求点连通度的方法就是转换为求边连通度，所以就需要我们巧妙的去构造一个流网络，使得其边连通度等于我们原来的图的点连通度。构造流网络N：

若G为无向图：

（1）原 G 图中的每个顶点 v 变成 N 网中的两个顶点 v" 和 v" ，顶点 v" 至 v" 有一条弧（有向边）连接，弧容量为 1;

（2）原 G 图中的每条边 e ＝ uv ，在 N 网中有两条弧 e’= u"v",e"=v"u" 与之对应， e" 弧容量为 ∞ ， e" 弧容量为 ∞

（3）求该网络的边连通度