[连通度问题,最小割]

题意:给一个无向图,求其点连通度?(注意输入问题)

思路:

  如果只有1个点,那么输出“1”;

  如果有0条边,那么输出“0”;

  其他情况:用最大流解决。下面讲如何建图:

  图的连通度问题是指:在图中删去部分元素(点或边),使得图中指定的两个点s和t不连通(即不存在从s到t的路径),求至少要删去几个元素。

  图的连通度分为点连通度和边连通度:
    (1)点连通度:只许删点,求至少要删掉几个点(当然,s和t不能删去,这里保证原图中至少有三个点);
    (2)边连通度:只许删边,求至少要删掉几条边。

  并且,有向图和无向图的点连通度求法不同,因此还要分开考虑。说明:最大流对应的是最小割。

  【有向图】:这个其实就是最小割问题。以s为源点,t为汇点建立网络,原图中的每条边在网络中仍存在,容量为1。

  【无向图】:需要拆点,每个点都拆成两个点v和v’,并连1条有向边v->v’,容量为1。点v承接原图中所有入边,点v’承接原图中所有出边。那么对于原图每条有向边就得建两条边了,容量无穷,且涉4个新顶点。

  【混合图】无向边按无向图处理,有向边按有向图处理。

  最后,源点S到汇点,跑一次最大流,就得到了答案。如果无指定ST,那么应该顶下1个S,再穷举其他点作为T。这个S应该如何定就不知道了,时间充裕就穷举S和T,不充裕就找个度最少的为S。

原文地址:https://www.cnblogs.com/zy691357966/p/5480304.html