ランダムグラフのdfsツリーの葉を削除した後、残った辺の数を| S |とすると、そのグラフのマッチングが| S |/2になることを証明できるか?グラフアルゴリズム、近似アルゴリズム
3
A
答えて
2
ここに証拠があります。
定理: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で床/天井の問題を見てきましたが、あなたがそれらを含めても、その証拠はまだ機能すると思われます。
+0
それは返信のために天井です、ありがとうございます。 –
関連する問題
- 1. 矩形近似アルゴリズム
- 2. 「スパニングツリー」を使用したVertex-Cover問題の2近似アルゴリズム
- 3. 有向グラフの制約付き最大スパニングサブツリーの近似アルゴリズム
- 4. 近似アルゴリズムを使用したセールスマンライブラリの移動
- 5. セットカバー近似
- 6. ニューラルネットワーク近似関数
- 7. ビットマップデータの類似アルゴリズム
- 8. セットカバー(個々のインスタンス)の貪欲アルゴリズムの近似率の上限値
- 9. ポイントの集合に基づくグラフの近似式を得るアルゴリズム
- 10. 二次元曲線近似
- 11. OpenGLの球の近似
- 12. 近似log10 [x^k0 + k1]
- 13. Google maps距離近似
- 14. 最速の最近傍アルゴリズム
- 15. K最近傍アルゴリズム疑問
- 16. 2者グラフアルゴリズム
- 17. Fortuneのアルゴリズムの疑似コード
- 18. このアルゴリズムの擬似コード
- 19. 線形時間グラフアルゴリズム
- 20. YUIのDataTableに最も近いjQuery近似は何ですか?
- 21. 度数ベジェ曲線の近似N
- 22. 円でポリゴンを近似する
- 23. IOS UISlider非連続の近似値
- 24. 小数から無理数の近似
- 25. ブルームフィルタの近似母集団の計算
- 26. シンプルCプログラム定数に近似
- 27. ニューラルネットワークによる近似関数
- 28. MATLABで近似を見つける
- 29. maps.google.comの近似長方形InfoWindow
- 30. SQLクエリ - グループIは、クエリ持っ近似
| S |/2あなたは床または天井を意味しますか? – kunigami
@kunigami、天井を意味する。 –
1)Is | S | DFSツリーのリーフまたは元のランダムグラフを削除した後のエッジの数 2)あなたがマッチングすることは、最大マッチングまたはマッチングがすべてOKであることを意味しますか? – kunigami