CODEWITHSUNDEEP
algorithmgraph-theory
sdadffdfd
sdadffdfd

Reputation: 693

Maximum matching in a bipartite graph

Use the following heuristic algorithm:

M = NULL
while E != NULL do {
if ((∃u vertex) and (gr(u) == 1)) then 
    e ← the incident edge with u
  else 
    e ← an incident edge with a vertex with the most incident edges
M ← M ∪ {e}
E ← E - (all the incident edges with e)
}
return M //return the matching

Where: M,E - edges ; gr(u) - the grade of u (the number of incident edges with u) ;

What we were asked:

  a) Prove that this algorithm returns the maximum matching for a tree.
  b) Prove that if there is a perfect matching M0 then the algorithm returns it, for any bipartite graph.
  c) Prove that |M| ≥ (v(G)/2), for any bipartite graph. 
  //G is the graph, v(G) is the matching number, size of the maximum matching.

I'm almost sure this algorithm is similar to some classic algorithm that I'm failing to find, or the solution could be completely based on theorems and properties of bipartite graphs.

Can you please give me a starting point.. What am I missing ?

I think a) is easy.. I'm still trying to find the right proof, I think it may be completely based on properties of trees and bipartite graphs.
For b) and c) .. I don't have any idea yet.

Upvotes: 4

Views: 2451

Answers (1)

Yonatan N
Yonatan N

Reputation: 307

This is very similar to the greedy matching algorithm. See the wikipedia article for more information.

As for the questions...

a) Show that the matching you get is maximal (there are no larger matchings containing it). What does this imply on a tree?
b) Show that if M0 is a valid matching that can be found in M ∪ E in a given step, that it can be found in M ∪ E in the next. By induction, the statement holds.
c) Consider a maximum matching M1. Why must at least one of the vertices adjacent to any given edge in M1 appear as an endpoint for some edge in the matching the algorithm outputs? What does this tell you about a lower bound for its size?

Upvotes: 2

Related Questions