build_auxiliary_node_connectivity

build_auxiliary_node_connectivity(G)

从无向图 G 创建一个有向图 D，用于计算基于流的节点连通性。

对于一个拥有 n 个节点和 m 条边的无向图 G，我们通过将每个原始节点 v 替换为两个通过 D 中一条（内部）弧连接的节点 vA、vB，从而得到一个拥有 2n 个节点和 2m+n 条弧的有向图 D。然后，对于 G 中的每条边 (u, v)，我们在 D 中添加两条弧 (uB, vA) 和 (vB, uA)。最后，我们将 D 中每条弧的 capacity 属性设置为 1 [1]。

对于一个拥有 n 个节点和 m 条弧的有向图，我们通过将每个原始节点 v 替换为两个通过 D 中一条（内部）弧 (vA, vB) 连接的节点 vA、vB，从而得到一个拥有 2n 个节点和 m+n 条弧的有向图 D。然后，对于 G 中的每条弧 (u, v)，我们在 D 中添加一条弧 (uB, vA)。最后，我们将 D 中每条弧的 capacity 属性设置为 1。

一个包含原始图节点与辅助有向图节点之间映射关系的字典被存储为一个图属性：D.graph[‘mapping’]。

参考文献

[1]

Kammer, Frank and Hanjo Taubig. Graph Connectivity. 载于 Brandes and Erlebach, ‘Network Analysis: Methodological Foundations’, Lecture Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. https://doi.org/10.1007/978-3-540-31955-9_7