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

Question

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

Answer 1

これが証拠です。

定理:葉Tのある任意の木とする。にマッチングiがあります。(|T|-i)/2T

証明: 帰納法による. が葉Tのある木である場合、 を からすべての葉を取り除いた木とします。 葉があります。同様に、からすべての葉を取り除いた結果のツリーを とします。 葉があります。iT'TT'j <= iT''T'T''k <= j

に帰納法による定理を適用するとT''、 にサイズの一致が存在(|T''|-k)/2 = (|T|-i-j-k)/2しT''ます。エッジのセットには、 のどのエッジにも、または互いに隣接していないエッジがT-T'少なくとも含まれているため ( の各リーフに 1 つのインシデントを選択)、これらのエッジを追加してサイズのマッチングを行います。以来、これは少なくともエッジです。QED。jT''T'T(|T|-i+j-k)/2j >= k(|T|-i)/2

/2 の床/天井の問題についてはざっと説明しましたが、それらを含めても証明は機能すると思います。