YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 06-29 Reducing to Clique

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. これがイメージ図になります
    グラフHから始めましょう
  2. ここにあるエッジを
    Hを補完する新しいグラフGに置き換えます
  3. Hにおいてエッジがある部分はすべて
  4. Gではエッジがないままにしておきます
  5. 例えばこのノードはこことここにつながっていません
  6. 補完グラフでつなげます
  7. このノードは上列のこの3つと
    下列の1つとつながっていますが
  8. 補完グラフではその他のノードにつなげます
  9. 上列の1つと下列の2つとですね
  10. 注意深くつなげていくと補完グラフGは
  11. sクリークを持っていることが分かりますね
  12. Hが独立s点集合問題を持っていた場合のみです
  13. 実際にノードの集合は同じです
    この例では4つのクリークがあります
  14. 前に出たグラフと似ていますね
  15. Gの中に4つのクリークがあり対応する箇所では
    Hの中に4つの独立点集合があります
  16. Gの中にペアのエッジがすべてあり
    Hの中にはないからです
  17. これが独立点集合問題を解くための
    クリーク問題の解き方です
  18. 一例として一般的なアイデアを紹介しましょう
  19. ある問題のインスタンスを
    他のインスタンスに変換します
  20. この場合変換はとても直接的です
  21. 最初はよく分からないかも知れませんが
    とても直接的なんですよ
  22. 還元も関係してきます
  23. この例では逆の還元も簡単に行えます
  24. 独立点集合をアルゴリズムに持つ場合
  25. クリーク問題を同じ方法で解くために使えます
  26. 補完グラフを元のグラフに反転し
    独立点集合を確認します
  27. 元のグラフにクリークが存在するか確認してください
  28. ただいつも問題と問題の関係が
    こんなに直接的であるとは限りません