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

式中：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）。我还不知道。

最佳答案

这与贪婪匹配算法非常相似。有关更多信息，请参见the wikipedia article。
至于问题…

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?

关于algorithm - 二部图中的最大匹配，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4281971/