igraph的gomory\u hu峎u树计算最小割树吗？

Question

我试图用pythonigraph实现this graph clustering algorithm (sec. 3.2)。由于我不想自己计算最小割树，所以我尝试使用gomory_hu_tree()方法。为了使用这种方法（并提供MWE），我写了以下内容：

from igraph import *

g= Graph()

g.add_vertices(4)

g.vs["name"] = ["0", "1", "2", "artificial"]

g.add_edge("0", "1", weight=10.0)
g.add_edge("0", "2", weight=20.0)
g.add_edge("2", "1", weight=30.0)
g.add_edge("artificial", "0", weight=100.0)
g.add_edge("artificial", "1", weight=100.0)
g.add_edge("artificial", "2", weight=100.0)

t = g.gomory_hu_tree(capacity="weight")
print t.es["flow"]
print
print t

我得到以下输出：

^{pr2}$

但那不是一棵最小的砍伐树！如果树是这样的，那么移除1和{}之间的边将以250的代价将图划分为两个子集{0, 1}和{}。然而，正确的答案是将{1}和{}分割开来，只需花费140英镑。在

（我所说的“成本”是指各自削减的价值。）

所以，一个（也是唯一的）正确答案应该是

0--artificial, 1--artificial, 2--artificial

我做错什么了？在这种情况下使用gomory_hu_tree()方法可能是错误的吗？在

注意：我最初是asked this question in a completely wrong way。在

Answer 1

以下是几个定义：

1）当且仅当对每对节点（u，v）而言，树中这两个节点之间的最大流与原始图中的相同（这意味着最小割的代价是相同的），则称为流等价树。在

2）一棵树满足A割性质当且仅当每对节点（u，v）的最小割与原图中的最小割相同（不仅代价相同，而且两个子集也相同）。在

所以问题是：什么是Gomory Hu树？有两种常见的定义：
1） 等效流 2） 满足割性质的流等价树。在

尽管没有记录在这个库中使用什么定义，但似乎他们使用了第一个定义。所以只能保证削减的成本是一样的，而不是削减本身。如果需要找到切割本身，可以对一对固定的节点使用maxflow方法。在