算法:对于 G = (V,E)，如何确定边集(e 属于 E)是否是图的有效割集

Question

给定图 G = (V,E) 的边子集，我们如何检查它是否是图的有效割集？注意:割是将图的顶点划分为两个不相交的子集。因此，切割的切割集是其端点位于分区的不同子集中的边的集合。我有兴趣找到解决这个问题的算法

Answer 1

一个简单的算法是从图中删除可疑的切边，然后查看是否仍然可以从已删除边的节点到对应的节点。如果你仍然可以，那不是一个完整的削减。因此，如果您删除具有节点 A 和 D 的 E2，您可以使用 A 的广度优先搜索，看看是否到达 D。它在空间需求和复杂性方面应该是线性的，因为我们存储了我们访问过的所有节点，所以我们不要回溯并访问任何节点两次。这个 wiki 页面有一些可能有用的漂亮图片:http://en.wikipedia.org/wiki/Cut_%28graph_theory%29