eis*_*baw 5 language-agnostic algorithm graph-theory graph
我们都知道并喜欢最小切割算法,但它们都切入图中的边缘.是否存在切断节点的变体？
Kee*_*ith 10
因此,要使用st最小割算法,您需要将图形转换为流网络.这给出了隐式有向图(边缘向前流动的方向).您可以使用此定向表示将图形转换为应解决此问题的内容.基本上你将每个顶点V(不包括源和接收器)转换为两个顶点,称为A和B.A获取所有V的边缘,B获得V的所有边缘.然后创建边缘A - > B,最大容量为无穷大.
我想如果你运行通常的st最小割算法,它只会选择你创建的边.我认为唯一必要的修改是在A的入度为1的情况下,它可能选择要切割的边缘,但是然后选择A作为顶点.(这取决于st算法的实现)
我希望这是有道理的.我不确定这是否有效(即我不想想出一个合适的证据),但它直观地表明它会.我的直观想法是,如果你剪切一个"非顶点"边缘,你也可以剪切一个"顶点"边缘,因为它与断开图形具有相同的效果.