igraph的Gomory-Hu树不起作用？ [英] igraph's Gomory–Hu tree not working?

问题描述

当我使用 python-igraph ：

  from igraph import * 
 
g =图表（）
 
 g.add_vertices（3）
 
 g.vs [name] = [0 ，1，3] 
 
 g.add_edge（0，1，权重= 0.0）
 g.add_edge（1，3，体重= 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（顶点名称）：
 0--1，1--3 
  

顶点3连接到其他顶点通过重量较高的边。因此，最小剪切树 t 应该是一个中心为3的星。这显然不是这种情况...

解决方案

算法工作正常。断开任何两个节点的最低成本是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树是连接每个节点的任何树。

When I try the following with 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

I get the output:

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

This makes no sense as vertex "3" is connected to the other vertices through edges with high weight. Therefor the minimum cut tree t should be a star with center "3". This is obviously not the case...

解决方案

The algorithm is working fine. The minimum cost to disconnect any two nodes is 10.0. All trees which are subgraphs of this graph are valid Gomory-Hu trees. In fact, this is the case for any K3 which has two edges of identical weight and a third of less weight.

Consider the brute-force approach. Since the minimum cost to disconnect any two nodes is 10.0, the complete minimum cut graph is the three nodes connected with edges of weight 10.0. By symmetry, this graph has three equally valid Gomory-Hu trees consisting of any two of the edges of the complete minimum cut graph.

So 0--1--3, 1--3--0, and 3--0--1 are all acceptable Gomory-Hu trees of the graph above.

In fact, for any graph of n nodes which has a complete minimum cut graph with all edges equal, the Gomory-Hu tree is any tree which connects every node.

这篇关于igraph的Gomory-Hu树不起作用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！