build_auxiliary_node_connectivity

build_auxiliary_node_connectivity(G)

从无向图G创建有向图D以计算基于流的节点连接。

对于具有以下条件的无向图G n 节点和 m 我们导出有向图D的边 2n 节点和 2m+n 通过替换每个原始节点来绘制圆弧 v 具有两个节点 vA ， vB 由D中的(内部)圆弧连接，然后针对每条边 (u ， v 在G中，我们添加两个圆弧 (uB ， vA )和 (vB ， uA )中)。最后，我们为D中的每条弧设置属性Capacity=1 [1].

对于有向图 n 节点和 m 弧我们导出一个有向图d 2n 节点和 m+n 通过替换每个原始节点生成圆弧 v 有两个节点 vA ， vB 由（内部）弧链接 (vA ， vB ）在D中，然后对于每个弧 (u ， v ）在G中，我们加一个弧 (uB ， vA ）最后，我们为D中的每个弧设置属性capacity=1。

原始图和辅助有向图中节点之间的映射字典存储为一个图属性：h.graph。 [“映射”] .

工具书类

1

卡默尔、弗兰克和汉乔·陶比格。图形连接性。收录于Brandes and Erlebach，《网络分析：方法论基础》，《计算机科学讲义》，第3418卷，Springer-Verlag，2005年。Https://doi.org/10.1007/978-3-540-31955-9_7