igraph（最大）生成树断开连接

Question

我有一个图，想求最大生成树，所以求图的最小生成树，权值倒数。然而，结果给出了一个断开连接的图形。

下面是我的问题示例：

import igraph
import numpy as np
AM = ([[0, 2, 1], [1, 0, 1], [2, 1, 0]])

g = igraph.Graph.Weighted_Adjacency(AM)
print g.is_connected()
inv_weight = [1./w for w in g.es["weight"]]
print g.spanning_tree(weights=inv_weight).is_connected()

结果是：

True
False

这怎么可能？

Answer 1

原来生成树是有向的，只有弱连接。因此

g.spanning_tree(weights=inv_weight).is_connected(mode="weak")

returns:

True

要获得强连接树，以下任一行都可行：

g = igraph.Graph.Weighted_Adjacency(AM, mode="undirected")

或

T = g.spanning_tree(weights=inv_weight)
T = T.to_undirected()
print T.is_connected()

结果是：

True

igraph（最大）生成树断开连接

igraph (maximum) spanning tree is disconnected

python

igraph