Corrispondenza massima in un grafico bipartito: algoritmo, teoria dei grafi

Usa il seguente algoritmo euristico:

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

Dove: M, E - bordi; gr (u) - il grado di u (il numero di fronti incidenti con u);

Quello che ci è stato chiesto:

  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.

Sono quasi sicuro che questo algoritmo sia simile ad un algoritmo classico che non riesco a trovare, o la soluzione potrebbe essere completamente basata su teoremi e proprietà di grafici bipartiti.

Puoi per favore darmi un punto di partenza .. Cosa mi manca?

Penso che a) sia facile .. Sto ancora cercando di trovare la prova giusta, penso che possa essere completamente basata sulle proprietà di alberi e grafici bipartiti.
Per b) ec) .. Non ho ancora idea.

risposte:

Questo è molto simile all'algoritmo di corrispondenza avidi. Vedere l'articolo di Wikipedia per maggiori informazioni.

Per quanto riguarda le domande ...

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?