最小切割顶点/节点 - 不是边线

Question

我们都知道并喜欢s-t最小切割算法，但它们都切割了图中的边缘。是否有任何变种切入节点？

Answer 1

因此，要使用s-t最小割算法，您需要将图转换为流网络。这给出了一个隐式有向图（边的正向流动方向）。你可以使用这个有向表示将图转换成应该解决这个问题的东西。本质上，你将每个顶点V（不包括源和汇）转换成两个顶点，称它们为A和B.A获取V的所有边内，B获得所有V的外边。然后创建最大容量为无穷大的边A - > B.

我想如果你运行通常的s-t最小切割算法，它只会选择你创建的边缘。我认为唯一必要的修改是在A的入度是1的情况下，它可以选择该边切割，然后只选择A作为顶点。 （这取决于s-t算法的实现）

我希望这是有道理的。我不确定这是否行得通（即我不想考虑一个合适的证明），但是直觉上它会这样。我所拥有的直观观点是，如果你切割一个“非顶点”边缘，那么你可能会削减一个“顶点”边缘，因为它具有与w.r.t相同的效果来断开图形。