我有一个图，其中我有两个节点（0 和 6），我必须尽可能减少边缘，以便它们不连接。例如在这张图中
作为节点 0 和 6，我必须切割的最少边是 2-7 和 3-7。我的想法是使用 bfs 找到两者之间的最短路径，我找到了一个（0-2-7-6），但我不知道如何找到另一个（0-3-7-6）。即使那样，我也不知道如何选择要切割的边缘。
如果有人可以就此事给我一些指示，那就太好了。
问问题
1272 次
2 回答
2
你想要的是一个最小的削减。在一般图中找到一个的常用方法是运行一个算法，如使用源 0 和接收器 6 的push relabel，它计算一个最小切割作为计算最大流量的副产品。
Karger 的算法找到了一个最小割，即，它最小化了 s 和 t 以及割。由于 s 和 t 对您来说是固定的，因此 Karger's 是不合适的。一个关节顶点是一个顶点，其移除会断开图的连接。您对删除边感兴趣，而不是顶点。
于 2013-06-06T14:32:38.353 回答
2
这个问题似乎与在图中查找关节节点的问题非常相似。关节点或双连接组件的技术定义是一个节点，其删除将导致图形一分为二。
从图中发现铰接节点是一个很大程度上已解决的问题，您可以在此处找到有关它的更多详细信息：http ://en.wikipedia.org/wiki/Biconnected_component
在我看来，你想解决这样的问题的方式通常是这样的：
1. Find all articulation points
2. Do a bfs from each node and determine articulation points along the path
3. Split graph at the articulation point, choosing the side with minimal edges
4. Continue until the two nodes are not connected
在上面的示例中，7 是唯一的连接点，因此您将剪断 7、2 和 3 之间的边，因为 7 和 0-4 图形之间只有两条边，7 和 5、6、8 之间只有 3 条边图形。
有一种更成熟的算法可以做到这一点（阅读：一个我没有想出的），称为 Karger 算法，可以解决您的问题，尽管在 n^2 时间。
该算法通过有效地将相邻节点彼此连接起来，直到只有两个节点，然后计算两个节点之间留下的边数。边数是分割图所需的最小切割数。
您在问题中实现 Karger 算法的方式只需要注意，您应该始终将节点连接到要拆分的两个节点。此外，为了能够回到您需要切割的原始边缘，您应该保留对边缘最初属于哪些节点的引用。
这里有一个很好的 Karger 算法可视化：http ://en.wikipedia.org/wiki/Karger%27s_algorithm
于 2013-06-04T19:29:46.570 回答