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

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

参数:

GNetworkX 图

terminal_nodes列表

需要查找最小 steiner 树的终端节点列表。

weight字符串 (默认 = ‘weight’)

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

method字符串, 可选 (默认 = ‘mehlhorn’)

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

返回值:

NetworkX 图

G 由 terminal_nodes 诱导的最小 steiner 树的近似解。

引发:

NetworkXNotImplemented

如果 G 是有向图。

ValueError

如果指定的 method 不受支持。

注意

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

参考文献

[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。