次のヒューリスティックアルゴリズムを使用してください。
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.
このアルゴリズムが私が見つけられなかった古典的なアルゴリズムに似ていることはほぼ間違いないか、あるいは解決策は完全に定理と2部グラフの性質に基づいている可能性がある。
出発点を教えてください。私が欠けているものは何ですか？
a）は簡単だと思います。私はまだ正しい証明を見つけようとしています。それは完全に木の性質と2部グラフに基づいているのではないかと思います。
b）とc）については、まだ何も考えていません。
回答：
回答№1は2これは、欲張りマッチングアルゴリズムと非常によく似ています。見る ウィキペディアの記事 詳細については。
質問は…
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?