在图形中查找割集 [英] Find cut set in a graph

问题描述

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

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

A subset S, of edges of a graph G = (V,E), how can one 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

推荐答案

换句话说，您要确定是否存在标签V-> {0，1}，以使S中的边具有带有不同标签的端点，并且E-S中的边具有带有相同标签的端点.这样的标签(如果存在)始终可以通过以下过程构造.

In other words, you want to determine whether there exists a labeling V -> {0, 1} such that edges in S have endpoints with different labels, and edges in E - S have endpoints with identical labels. Such a labeling, if it exists, always can be constructed by the following procedure.

横越G(例如深度优先，但这并不重要).标签遍历的根是任意的.每次处理从带标签的节点u到其他节点v的边e时，如果e不在S中，则用u的标签标记v；如果e在S中，则用u的标签相反.如果v已经具有不同的标签，则S为不是套路.否则，如果遍历没有发生意外，则S是割集.

Traverse G (say depth-first, but it doesn't really matter). Label traversal roots arbitrarily. Every time you process an edge e from a labeled node u to some other node v, label v with u's label if e not in S and the opposite of u's label if e in S. If v already has a different label, then S is not a cut-set. Otherwise, if the traversal finishes without incident, then S is a cut-set.

这篇关于在图形中查找割集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！