Максимальне узгодження в двопарному графі - алгоритм, теорія графів

Використовуйте такий евристичний алгоритм:

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

Де: М, Е - краї; gr (u) - ступінь u (число падаючих ребер з u);

Те, що нам було запропоновано:

  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.

Я майже впевнений, що цей алгоритм схожий на якийсь класичний алгоритм, який я не можу знайти, або рішення може бути повністю засноване на теоремах і властивостях дводольних графіків.

Чи можете ви дати мені відправну точку .. Що я відсутній?

Я думаю, що) легко .. Я все ще намагаюся знайти правильний доказ, я думаю, що він може бути повністю заснований на властивості дерев і дводольних графіків.
Для б) і с) .. Я ще не маю ніякої ідеї.

Відповіді:

Це дуже схоже на жадібний алгоритм відповідності. Подивитися статтю Вікіпедії для отримання додаткової інформації.

Що стосується питань ...

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?