高校大学連携授業 2

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

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

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

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


5. ケーニヒスベルグの七つの橋:グラフ理論の誕生

 オイラー(Euler:1707-1782)は,1736年にケーニヒスベルグ(Königsberg)の七つの橋の問題をグラフを用いて解決した。

  • 無向グラフ:頂点と無向辺からなる図。無向辺を単に辺と呼ぶ
     
  • 頂点の次数:頂点につながっている辺の本数
     
  • 多重辺:同じ頂点間にある辺
     
  • オイラー閉路:一筆書きができる閉じた道筋
                   = すべての辺をちょうど一回だけ通って元へ戻る道筋
     
  • オイラーグラフ:オイラー閉路があるグラフ
                    = すべての頂点の次数が偶数である連結なグラフ
     
  • 単純グラフ:ループも多重辺ももたないグラフ
     
  • 多重辺をもたない無向グラフは,頂点に対応する集合の上の対称な関係を図で表現したもの
     

  • 【練習問題5】 下のグラフがオイラーグラフなら,そのオイラー閉路を見つけよ。オイラーグラフでなければ,最小本数の辺をつけ加えてオイラーグラフになるようにせよ。多重辺ができてもかまわないが,頂点は増やさないこと。



     

     

    トップページに戻る