二部グラフの最大マッチング

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. 

を、私はこのアルゴリズムは、私が見つけることができないんだいくつかの古典的なアルゴリズムに似ている、または溶液が完全に二分の定理や性質に基づいてすることができ、ほぼ確信している：私たちが求めていた何

グラフ。

私に出発点を教えてもらえますか？私は何が欠けていますか？

私はまだ簡単なことを考えています。私はまだ正しい証拠を見つけようとしていますが、それは木々と二部グラフの特性に完全に基づいていると思います。
b）とc）については、まだ分かりません。

Answer 1

これはグリーディマッチングアルゴリズムに非常によく似ています。詳細については、the wikipedia articleを参照してください。質問については

...