steiner_tree

steiner_tree(G, terminal_nodes, weight='weight', method=None)

返回图的最小Steiner树的近似结果。

G 相对于一组 terminal_nodes （也称为 S）的最小Steiner树是在 G 中跨越这些节点且具有最小尺寸（边权重的总和）的树。

近似算法通过 method 关键字参数指定。所有三种可用算法产生的树的权重都在最优Steiner树权重的 (2 - (2 / l)) 因子之内，其中 l 是所有可能的Steiner树中最小叶子节点数。

• "kou" [Rfafe17775e63-2]_（运行时间 \(O(|S| |V|^2)\)）计算由终端节点诱导的 G 的度量闭包的子图的最小生成树，其中 G 的度量闭包是完全图，其中每条边由 G 中节点之间的最短路径距离加权。

• "mehlhorn" [Rfafe17775e63-3]_（运行时间 \(O(|E|+|V|\log|V|)\)）修改了 Kou 等人的算法，首先为每个非终端节点找到最近的终端节点。这些数据用于创建仅包含终端节点的完全图，其中每条边由它们之间的最短路径距离加权。然后算法以与 Kou 等人相同的方式继续进行。

Parameters:

GNetworkX图

terminal_nodes列表

要找到最小Steiner树的终端节点列表。

weight字符串（默认 = ‘weight’）

使用此字符串指定的边属性作为边权重。任何不存在的边属性默认值为1。

method字符串，可选（默认 = ‘mehlhorn’）

用于近似Steiner树的算法。 支持的选项：’kou’, ‘mehlhorn’。 其他输入会产生 ValueError。

Returns:

NetworkX图

G 由 terminal_nodes 诱导的最小Steiner树的近似结果。

Raises:

NetworkXNotImplemented

如果 G 是有向图。

ValueError

如果指定的 method 不受支持。

Notes

对于多重图，两个节点之间具有最小权重的边是放入Steiner树的边。

References

[1]

Wikipedia上的Steiner树问题。 https://en.wikipedia.org/wiki/Steiner_tree_problem

[2]

Kou, L., G. Markowsky, and L. Berman. 1981. ‘A Fast Algorithm for Steiner Trees’. Acta Informatica 15 (2): 141–45. https://doi.org/10.1007/BF00288961.

[3]

Mehlhorn, Kurt. 1988. ‘A Faster Approximation Algorithm for the Steiner Problem in Graphs’. Information Processing Letters 27 (3): 125–28. https://doi.org/10.1016/0020-0190(88)90066-X.