二分图中的最大匹配

Question

使用以下启发式算法：

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

翻译内容：

在哪里：M，E - 边缘; 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)很简单。我仍在努力寻找正确的证明，我认为它可能完全基于树和二分图的性质。
对于b)和c)... 我还没有任何想法。

- sdadffdfd

---

当你说“经典算法”时，你是指Hopcroft-Karp算法吗？ - sleeplessnerd

Answer 1

这与贪婪匹配算法非常相似。更多信息请参见维基百科文章。

至于问题...

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?

- Yonatan N