igraph的Gomory–Hu树无法工作？

Question

当我尝试用 python-igraph 做以下操作时：

from igraph import *

g= Graph()

g.add_vertices(3)

g.vs["name"] = ["0", "1", "3"]

g.add_edge("0", "1", weight=0.0)
g.add_edge("1", "3", weight=10.0)
g.add_edge("0", "3", weight=10.0)

t = g.gomory_hu_tree(capacity="weight")
print t

我得到的结果是：

IGRAPH UNW- 3 2 --
+ attr: name (v), flow (e), weight (e)
+ edges (vertex names):
0--1, 1--3

这让我很困惑，因为顶点 "3" 是通过一些权重很大的边和其他顶点相连的。所以，最小割树 t 应该是一个以 "3" 为中心的星形结构。但显然并不是这样……

Answer 1

这个算法运行得很好。要断开任何两个节点之间的连接，最少需要花费10.0的成本。这个图的所有子图都是有效的Gomory-Hu树。实际上，对于任何有两条边权重相同、第三条边权重较小的K3图来说，都是这样的情况。

想想暴力破解的方法。因为要断开任何两个节点的最小成本是10.0，所以完整的最小割图就是三个节点通过权重为10.0的边连接在一起。由于对称性，这个图有三个同样有效的Gomory-Hu树，每棵树由完整最小割图中的任意两条边组成。

所以，0--1--3、1--3--0和3--0--1都是上面图的可接受的Gomory-Hu树。

实际上，对于任何有n个节点的图，如果它的完整最小割图中所有边的权重都相等，那么Gomory-Hu树就是连接每个节点的任何树。