Блог пользователя svg_af

Help with minimum vertex cover in bipartite graphs
Автор svg_af, история, 8 лет назад, По-английски

Hello there

I know that minimum vertex cover is equal to maximum matching

My question is about how to find the vertices that form the cover

any help would be appreciated

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Let X-Y be a bipartition of the vertex set.

  • Find a Maximum Matching (Theorem: A matching is maximum iff there isn't any augmenting path).
  • Call U the set of unsaturated vertices of X.
  • Call Z the set of vertices reachable from U (including U itself) through an alternating path.
  • Make (Latex seems to be broken, I wrote: R = (X-Z) union (Y intersection Z) )

R is a minimum cover.

It's fairly easy to prove it, but this is essentially König's theorem's proof, check it out in wikipedia.

→ Ответить