グラフアルゴリズム、近似アルゴリズム

Question

ランダムグラフのdfsツリーの葉を削除した後、残った辺の数を| S |とすると、そのグラフのマッチングが| S |/2になることを証明できるか？

Answer 1

ここに証拠があります。

定理：Tはiの葉を持つ任意のツリーであるとします。 Tに一致する(|T|-i)/2があります。

証明：誘導による。 Tがiの葉を持つツリーである場合は、Tからすべての葉を削除すると、T'がツリーになります。 T'はj <= iの葉を有する。同様に、すべての葉をT'から削除すると、T''がツリーになります。 T''はk <= jの葉を有する。

T''に定理を適用すると、(|T''|-k)/2 = (|T|-i-j-k)/2の一致がT''に存在します。 T-T'には、少なくともjのエッジが含まれており、T''のいずれのエッジにも当てはまらない（T'の各リーフに1つのインシデントを選択する）ので、のTで一致するようにそれらのエッジを追加します。 j >= k以降、これは少なくとも(|T|-i)/2エッジです。 QED。

私は/ 2で床/天井の問題を見てきましたが、あなたがそれらを含めても、その証拠はまだ機能すると思われます。