build_auxiliary_node_connectivity

build_auxiliary_node_connectivity(G)

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

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

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

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

References

[1]

Kammer, Frank 和 Hanjo Taubig。图连通性。在 Brandes 和 Erlebach 的 ‘网络分析：方法论基础’ 中，计算机科学讲义，第 3418 卷，Springer-Verlag，2005 年。 https://doi.org/10.1007/978-3-540-31955-9_7