toritoトップページ
ワンダーランド
パズル遊びへの招待・オンライン版

1−18.橋渡り問題と一筆書き


 大哲学者カントが生まれた町として有名なケーニヒスベルク(現在のカリーニングラード)は、プレーゲル川にまたがったおり、18世紀の初頭には、[1]のようにこの川に7つの橋がかかっていた。
 その頃、この橋を全部ただ一度ずつ渡ることができるかどうかが、この町の話題になった。ある人は不可能だと言った。ある人は実際にやったらできたと言ったが、もう一度再現することはできなかった。こうして町中の話題になっているときに、数学者のレオンハルト・オイラー(1707〜1783)がこの問題を取り上げて研究し、橋渡りが不可能であることを証明した。

 オイラーはまず、[1]の図を整理して、単純化することから始めた。[1][2]-Aのように橋の続き具合に注目して、橋を線で表し、ケーニヒスベルクの各地区を点で表してみると、[2]-Bのように変形することができる。このようにしても、それぞれの位置関係には変化がないことは明らかである。これによって橋渡りの問題は、Bが一筆書きできるかどうかの問題に変わってしまう。
 次に、一筆書きができるかどうかの判定をしなければならない。一筆書きしようとする図形のコーナー(分岐点)に注目すると、そこは書き始め(出発点)か、書き終わり(終点)か、中間点かのいずれかである。中間点の場合は、必ずその点に来る線と、そこから出ていく線とが対で存在しなければならない。一方、出発点と終点の場合は、両方が一致すれば線の数は偶数に、そうでなければ奇数になる。つまり、そこに集まる線の数が奇数になり得るのは、出発点と終点だけである。


[1]ケーニヒスベルクの図


[2]-A


[2]-B 単純化した図

 そこで一筆書きができるかどうかの見分け方は、次のようになる。まず、その図の各コーナーに集まる線の数を調べる。

  1. [3]-Aのように(カッコ内は線の数)線が偶数だけの図形は、どこから書き始めても、一筆書きが可能である。
  2. [3]-Bのように奇数の箇所が1または2の図形は、そこを出発点か終点(2箇所の場合はその両方)にすれば、一筆書きが可能である。
  3. [3]-Cのように奇数の箇所が3以上なら、その図形は一筆書きすることはできない。
[3]一筆書き判定説明図
A
B
C

 ところで[2]-Bは、各点に集まる線の数は4箇所とも奇数であり、橋渡りは不可能との結論になる。

 このコーナーは、高木茂男氏の著書「パズル遊びへの招待」(発行:PHP研究所・1994年)の内容に著者自身が加筆・修正を加えたものを、著者本人及び出版元の許諾により掲載しているものです。
 他サイトへの無断転載はご遠慮ください。

●第1部・歴史的なパズル●

  1. 迷路
  2. リンド・パピルスのパズル(からす算)
  3. 魔方陣
  4. 知恵の輪(チャイニーズリング)
  5. ヨセフスの問題とまま子立て
  6. 渡船問題(川渡りの問題)
  7. 油分け算
  8. 盗人隠し
  9. さっさ立て
  10. 薬師算
  11. 碁石拾い
  12. おしどりの遊びと入れ替え問題
  13. 一小刀問題
  14. ねずみ算とフィボナッチ数列
  15. 知恵の板
  16. 虫食い算
  17. 目付け字と数当てカード
  18. 橋渡り問題と一筆書き
  19. ソリテア
  20. ハノイの塔
  21. デュードニー
  22. サム・ロイド
  23. 移動板パズル
  24. 図形消滅パズル
  25. パラドックス
  26. 四色問題
  27. チェスのパズル
  28. にせ金の問題

●第2部・言葉と絵のパズル●

  1. 回文
  2. アナグラム
  3. 折り句
  4. 暗号
  5. ダブレット(変形パズル)
  6. クロスワードパズル
  7. サーチワード、クリスクロス
  8. スクラブル
  9. 漢字作りパズル
  10. 単語作りパズル
  11. 判じ物と判じ絵
  12. 絵暦
  13. 新しい単語パズルの作り方
  14. 電卓文字遊び
  15. いろいろな文字遊び
  16. 絵当てパズル
  17. かくし絵
  18. さかさ絵
  19. その他の絵のパズル

●第3部・パズルの展開●

  1. ポリオミノ
  2. 立体パズル
  3. ブラックボックス
  4. 裏表パズル
  5. ザイルトリック
  6. 絵合わせパズル
  7. 切り継ぎパズル
  8. お菓子の分配
  9. クロスワードパズルの数字版
  10. 電卓数字パズル
  11. 覆面算
  12. 年賀用パズル
  13. コインのパラドックス
  14. マスターマインド
  15. パソコン・パズル
  16. 速算ダイス
  17. インスタント・インサニティ
  18. グラスパズル
  19. 匹見木のパズル

●パズルの考え方・解き方●

  1. パズルの考え方・解き方 (1)
  2. パズルの考え方・解き方 (2)
  3. 参考文献

[↑toritoトップページ][パズル・ワンダーランド]