A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.↵
↵
A minimum vertex cover is a vertex cover with minimal cardinality.↵
↵
Consider a set of all minimum vertex covers of a given bipartite graph.↵
↵
our task is to divide all the vertices of the graph into three sets.↵
↵
A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.↵
↵
A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.↵
↵
If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).↵
↵
How to classify vertices ??↵
↵
Basically, I want to solve this problem
↵
A minimum vertex cover is a vertex cover with minimal cardinality.↵
↵
Consider a set of all minimum vertex covers of a given bipartite graph.↵
↵
our task is to divide all the vertices of the graph into three sets.↵
↵
A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex.↵
↵
A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph.↵
↵
If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).↵
↵
How to classify vertices
↵
Basically, I want to solve this problem