螃蟹图、算法、图论，这个网络流怎么样？

Question

螃蟹图、算法、图论，这个网络流怎么样？

algorithmgraphgraph-theorynetwork-flow

6

请有人帮助我解决这个问题吗？解决方案显然要使用网络流，但我对网络流不太熟悉。网络流如何帮助你解决这个问题？

螃蟹是一个无向图，它有两种类型的顶点：1个头和K个脚，恰好有K条边将头连接到每个腿。(1 <= K <= T，其中T是给定的)

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

注意：如果两个图没有任何公共顶点，则它们是顶点不相交的。

例子. 输入：

- user2445793

3

请注意，这是在HackerRank竞赛网站上进行的一项挑战活动。 - Beta

3个回答

3

这是一个顶点覆盖问题。对于一个图的顶点覆盖，螃蟹头是顶点覆盖的顶点，而螃蟹脚是与这些头相连的顶点。重复的螃蟹脚应该被移除，但要注意不能移除一个螃蟹的所有脚:-)

更新：最小顶点覆盖是一个NP完全问题，这不太好 :-) 我认为螃蟹覆盖是等效的。至少有了最小的螃蟹覆盖，我们可以得到最小的顶点覆盖。所以，如果最小的螃蟹覆盖不是NP完全问题，那么最小的顶点覆盖也不应该是NP完全问题。

让我们证明，如果蟹的覆盖面积最小，那么我们可以得到最小的顶点覆盖。通常的方法是使用蟹头来获取顶点覆盖。假设相反，存在一个比蟹头少的顶点覆盖，覆盖中的顶点数比蟹头少。对于这个顶点覆盖，我们可以构造一个具有相同度数的蟹覆盖，除了我们不确定是否存在没有足部的蟹，因为我们移除了重复的足部。只有在存在一个头和其他头共享脚且每个其他头没有其他足时，才可能出现这种情况。在这种情况下，我们可以通过删除这两个头并在关键脚上设置头来构造更小的顶点覆盖。由此产生了矛盾，因此不存在比这更少的顶点覆盖。因此，最小的蟹覆盖也是最小的顶点覆盖。

- Ante

有趣，我不确定为什么我没有想到。我会实现并尽快回复您。非常感谢！ - user2445793

我知道有一种使用网络流算法，特别是福特-福克森算法的解决方案。如果有人知道为什么这样做，请告诉我，因为我对网络流不是很熟悉，想学习更多。谢谢大家！ - user2445793

使用顶点覆盖也很困难，因为它是一个 NP 完全问题。而网络流则不是。 - user2445793

1

通过顶点覆盖方法解决上述问题会导致指数级时间算法，但可以通过使用Ford Fulkerson算法来最大化流量来解决此问题。可以使用Ford Fulkerson解决上述问题。

创建从源（0）到具有容量t的图中所有节点的路径。
创建从所有节点到目标（1）的路径，容量为1。
使用Ford Fulkerson找到上述修改后的图的最大流。

Ford Fulkerson算法用于查找给定图中的最大流

在图中找到从源到目标的路径。
找到路径上的最小流量。
增加沿路径的所有边的流量，其值为上述计算出的最小流量。
存储路径的最小流量。

重复以上4个步骤，直到不可能再找到增广路径为止。

Ford Fulkerson算法的解释

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

参考资料

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

- its ramteja

1

哪些节点是源节点和目标节点？最终的流量与螃蟹数量有什么关系？ - Sebastian

1

这对我来说没有意义。如果您像这样修改图形，则最大流将始终是节点数。 - Zsolt Safrany

为什么在这里解释最大流算法？我可以查找；我对螃蟹图解决方案感兴趣。 :) 它没有解释如何解决螃蟹问题。为什么这个答案被接受了？ - Zsolt Safrany

1

这是我在StackOverflow上看过的最具误导性的答案之一。请阅读来自machaxX的答案。 - jk_

1

不提供解决给定问题的解决方案，也不提供任何支持性想法来解决它。 - Yerken

请提供要翻译的内容。 - Akash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- machaxX · Accepted Answer

思考如何将网络流应用于此问题。应该是这样的，从螃蟹的头到脚有一条流动，流向头部的流应该具有与脚数相当的值，而从头到脚的每个边缘的容量应为一。

我们该如何实现这一点？肯定很难独自想出来，但我希望在多次看到示例后，你能掌握这个技巧。

我们必须创建一个新图，其中原始顶点被复制。一个集合可以使每个顶点都有成为头部的机会，另一个集合则可以充当脚。记住这一点，精确的算法可以写成以下形式：

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，因为螃蟹不能有超过t只脚，并且这里的容量值还受到所连接的顶点度数的限制。一个头戴式设备不能拥有比其度数更多的脚。

第4点的解释：为确保配对是不相交的，以便每个顶点只出现在一个螃蟹中，每只脚都与图中的目标10相连，容量为1。

如果需要，我可以发布代码。