蟹图,算法,图论,这个网络是如何流动的？

Question

有人可以帮我解决这个问题吗？解决方案显然是使用网络流量,但我不是很熟悉网络流量.网络流程如何帮助您解决这个问题？

螃蟹是一个无向图,它有两种顶点:1个头和K个脚,正好是K个边缘,它们将头部连接到每个腿上.(1 <= K <= T,其中给出了T)

给定一个无向图,你必须在其中找到一些顶点不相交的子图,其中每个子图都是一个螃蟹.目标是以这样的方式选择那些螃蟹,使得它们所覆盖的顶点的总数最大化.

注意:如果两个图形没有任何共同的顶点,则它们是顶点不相交的.

例如 输入

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6

Answer 1

想想网络流如何应用于这个问题.这应该是一种流动从螃蟹的头部流到它的脚.并且流到头部的流量应该具有相当于英尺数的值,并且从头到脚的每个边缘应该具有容量1.

我们怎样才能做到这一点？自己来到这里肯定很难,但我希望在多次见到这个例子之后,你可以掌握这一点.

我们必须创建一个新的图形,其中原始顶点是重复的.一组可以给每个顶点有机会成为头部而另一组可以作为脚.记住这一点,准确的算法可以写成如下: -

1. We create a new graph where original vertices are duplicated (vertex i  becomes 2*i (head set) and 2*i+1  (feet set)    ).

2.For i and j vertices connected in original graph make sure that 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1.

3.source vertex (S) is connected to each 2*i vertex(head set) with capacity min(T, degree).
4. Each 2*i+1(feet set) vertex is connected to target vertex (T) with capacity 1
5. Maxflow is the answer.

下面的图片可以很好地了解图形的形成方式. 新的图形形成

第3点的解释: - 耳机中的每个顶点都应该与容量min(t,degree)的源连接,因为如果我们希望在这个边缘有一个最大流量与T一样大,不要超过那个因为因为蟹不能超过t英尺,这里的容量值也受到连接0的顶点的程度的限制.头部不能超过其度数.

点4的解释: - 为了确保对不相交,使得每个顶点仅在一个螃蟹中,每个脚与容量1连接到图中的目标10.

如果需要,我可以发布代码.

Answer 2

通过顶点覆盖方法解决上述问题会产生指数 tim 算法，但这可以通过使用 Ford Fulkerson 算法最大化流来解决 上述问题可以使用 Ford Fulkerson 来解决。

1. 创建一条从 source(0) 到容量 = t 的图的所有节点的路径。
2. 创建一条从所有节点到目标(1) 的路径，容量 = 1。
3. 使用 Ford Fulkerson 求上述修改图的最大流量。

福特富尔克森算法在给定图中找到最大流量

1. 在图中找到从源到目标的路径。
2. 找出沿路径的最小流量。
3. 将沿路径的所有边的流量增加上面计算的最小流量
4. 存储路径的最小流量。

重复上述4步，直到没有增广路为止。

Ford Fulkerson 算法的解释

选择一条可能的路径并确定容量最小的边。记录该数字 从该路径上的每个数字中减去该数字。这是路径上每条弧的新容量。选择另一条路线，重复步骤1，再次记录最小容量。重复直到所有可能的路径都用尽。添加所有路线中最小的容量。这是网络的最小承载能力

参考

http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20algorithm