确定图中所有可以移除的边,从而在给定图中不会产生新的桥的最有效方法是什么?
目前我总是复制图,把优势并检查桥梁的桥梁和数量是否改变。我对每条边重复这个过程,然后返回边的列表。在列表中选择一个并删除它。当我想要删除几个边时,我重复整个过程几次。
什么是更好/更有效的方法?(我总是需要整个候选人名单。)
我想你是在寻找当移除时会产生k=2的所有k边分量的边。
-
用
nx.algorithms.connectivity.edge_kcomponents.k_edge_components
(k=2)搜索G中的所有k边分量。这将产生由切割大小为2的切割产生的所有顶点集。 -
为每个顶点集归纳出一个子图,并利用
nx.compose
将子图组合成一个图h -
用
nx.difference(G, H)
测定G和H的差值