图的连通度问题的求法

Posted on 2011-04-05 16:23 Mato_No1 阅读(2719) 评论(0)  编辑 收藏 引用 所属分类: 网络流
图的连通度问题是指:在图中删去部分元素(点或边),使得图中指定的两个点s和t不连通(不存在从s到t的路径),求至少要删去几个元素。
图的连通度分为点连通度和边连通度:
(1)点连通度:只许删点,求至少要删掉几个点(当然,s和t不能删去,这里保证原图中至少有三个点);
(2)边连通度:只许删边,求至少要删掉几条边。
并且,有向图和无向图的连通度求法不同,因此还要分开考虑(对于混合图,只需将其中所有的无向边按照无向图的办法处理、有向边按照有向图的办法处理即可)。

【1】有向图的边连通度:
这个其实就是最小割问题。以s为源点,t为汇点建立网络,原图中的每条边在网络中仍存在,容量为1,求该网络的最小割(也就是最大流)的值即为原图的边连通度。

【2】有向图的点连通度:
需要拆点。建立一个网络,原图中的每个点i在网络中拆成i'与i'',有一条边<i', i''>,容量为1(<s', s''>和<t', t''>例外,容量为正无穷)。原图中的每条边<i, j>在网络中为边<i'', j'>,容量为正无穷。以s'为源点、t''为汇点求最大流,最大流的值即为原图的点连通度。

说明:最大流对应的是最小割。显然,容量为正无穷的边不可能通过最小割,也就是原图中的边和s、t两个点不能删去;若边<i, i''>通过最小割,则表示将原图中的点i删去。

【3】无向图的边连通度:
将图中的每条边(i, j)拆成<i, j>和<j, i>两条边,再按照有向图的办法(【1】)处理;

【4】无向图的点连通度:
将图中的每条边(i, j)拆成<i, j>和<j, i>两条边,再按照有向图的办法(【2】)处理。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理