couplage maximum dans un graphe biparti

Question

Utilisez l'algorithme heuristique suivante:

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 

dans laquelle: M, E - bords; gr (u) - la note de u (le nombre de bords incidents avec u);

Ce que nous a demandé:

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. 

Je suis presque sûr que cet algorithme est similaire à un algorithme classique que je ne pas trouver, ou la solution pourrait être complètement basée sur théorèmes et propriétés de biparti graphiques.

Pouvez-vous s'il vous plaît me donner un point de départ .. Qu'est-ce qui me manque?

Je pense que a) est facile .. J'essaie toujours de trouver la bonne preuve, je pense qu'il peut être entièrement basé sur les propriétés des arbres et des graphiques bipartites.
Pour b) et c) .. Je n'ai pas encore d'idée.

Answer 1

Ceci est très similaire à l'algorithme de correspondance glouton. Voir the wikipedia article pour plus d'informations.

En ce qui concerne les questions ...