Minimum vertex cover
Difference between en1 and en2, changed 48 character(s)
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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English physicsIE 2019-04-20 20:04:27 48
en1 English physicsIE 2019-04-20 19:47:48 663 Initial revision (published)