高校大学連携授業 2

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

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

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

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


6. 握手の定理

『グラフにおいて,各頂点の次数の総和は辺の本数の2倍になる』

 例えば,あるパーティーに出席した人たちが握手した回数の総和は,パーティーでかわされた握手の回数の2倍に一致する。

【練習問題6】 ただひとつの頂点の次数が奇数で,それ以外の頂点の次数が偶数であるようなグラフは存在しないことを説明せよ。








 

 

トップページに戻る