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
弧我们导出一个有向图d2n
节点和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