算法：对于G = (V,E)，如何确定边集（e属于E）是否是图的有效割集
给定图 G = (V,E) 的边子集，我们如何检查它是否是图的有效割集？ 注意：切割是将图的顶点划分为两个不相交的子集。因此，割集的割集是其端点位于分区的不同子集中的边的集合。 我有兴趣找到解决这个问题的算法
Given a subset of edges of a graph G = (V,E), how can we check whether it is a valid cut-set of the graph or not?
Note: A cut is a partition of the vertices of a graph into two disjoint subsets. So, cut-set of the cut is the set of edges whose end points are in different subsets of the partition.
I am interested to find an algorithm for this problem
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一个简单的算法是从图中删除可疑的切边，然后看看是否仍然可以从删除边的节点到达其对应的边。如果你还能做到的话，那么这还不是一个完整的剪辑。因此，如果您删除具有节点 A 和 D 的 E2，您可以使用从 A 开始的广度优先搜索，看看是否到达 D。它的空间要求和复杂性应该是线性的，因为我们存储了我们访问过的所有节点，所以我们不要回溯并访问任何节点两次。
这个维基页面有一些漂亮的图片可能会有所帮助：http://en.wikipedia.org/维基/Cut_%28graph_theory%29
A simple algorithm would be to remove the suspected cut-edges from the graph, and see if you can still get from a node of a removed edge to its counterpart. If you still can, it was not a full cut. So if you remove E2 which had nodes A and D, you can use breadth first search from A and see if you ever get to D. It should be linear in space requirements and complexity since we store all the nodes we've visited so we don't backtrack and visit any node twice.
This wiki page has some nice pictures that might help: http://en.wikipedia.org/wiki/Cut_%28graph_theory%29
如果删除该边子集后，它不再是连通图，则它是有效的割集。
如果您要求算法，您应该能够从任何节点开始，看看是否可以通过深度优先搜索到达所有其他节点。如果是，则它不是有效的割集，如果不能，则它是有效的割集。
It's a valid cut set if, with that edge subset removed, it's no longer a connected graph.
If you're asking for algorithms, you should be able to start at any node and see if you can reach all other nodes via depth first search. If so, it's not a valid cut set, if it can't, it's a valid cut set.