高校大学連携授業 2

「関係を図で表現する道具」(坂本 明雄)

  1. はじめに
  2. 関係を数学的に定義すると
  3. 関係を座標図で表現する
  4. 関係を矢線図で表現する
  5. 関係を有向グラフで表現する
  6. ケーニヒスベルグの七つの橋:グラフ理論の誕生
  7. 握手の定理
  8. ハミルトングラフ:難しい問題の例
  9. 同型なグラフ

印刷用PDFファイル [本文(190KB)] [解答(65KB)]

※一部特殊文字を使用しているため環境によっては、文字化けが起こる場合があります。その場合は、印刷用PDFファイルをご覧ください。


7. ハミルトングラフ:難しい問題の例

  • 世界周遊の旅問題
     
  • ハミルトン閉路:すべての点をちょうど一回だけ通って元へ戻る道筋
     
  • ハミルトングラフ:ハミルトン閉路があるグラフ
                     簡単な調べ方はない!
                     [総当たり法で調べることは可能だが...]
     
  • NP完全問題:難しい問題。非常に多くの重要な問題がNP完全であることが証明されており,そのうちの一つを効率よく解く方法を発見すれば,その方法を利用して他のすべてのNP完全問題も効率よく解けることが保証されている。
     
  • ハミルトングラフであるかどうかを判定する問題はNP完全である。
      「効率よく解く方法を見つけることはあきらめよう...」
     

  • 【練習問題7】 下の3つのグラフについて,ハミルトングラフであるかどうかを判定せよ。ハミルトングラフであればそのハミルトン閉路を見つけよ。また,ハミルトングラフでなければ,最小本数の辺をつけ加えてハミルトングラフになるようにせよ。頂点は増やさないこと。



     

     

    トップページに戻る