計算コラム

  1. ホーム/
  2. 計算コラム

(99) 一筆書きとグラフ理論

  • Back
2020/06/11
　ある図形が与えられたときに、"一筆書きができるか？"という判定問題は、アルゴリズムの題材によく使われる他、 算数の入試問題に使われることもある。簡単な図形であれば、図形を１つ１つ手でなぞって判定することも可能だが、複雑な図形になってくると困難である。
例えば、図1(a)のような四角形であれば、すぐに一筆書きを出来ることは分かるが、 図1(b)のようになると、すぐには判定できそうにない。 この一筆書きの問題を考えるにあたって、有名な例として「ケーニヒスベルクの橋の問題」がある。

問.
18世紀の初めにプロイセン王国のケーニヒスベルク（現ロシア連邦カリーニングラード）の 中央にはプレーゲル川があり、図2のような7つの橋が架かっていた。 ある地点から出発して、7つの橋を1回ずつ渡ることはできるか？

この問題について、18世紀スイスの大数学者レオンハルト・オイラーは図3のような節点(node)、辺(edge)からなる"グラフ"に置き換えて考えた。
このグラフが一筆書きが可能であれば、橋を全て1回ずつ渡るルートが存在することになるが、オイラーはこのグラフが一筆書きができないことを証明した。
一筆書きが出来る図形はオイラー路と呼ばれ、辺が偶数本繋がっている節点を偶節点、奇数本繋がっている節点を奇節点とするとき、 オイラー路が存在するためには、奇節点が0個または2個でなければならない。
図1(a)を見ると偶節点4つ、図1(b)は偶節点4つ・奇節点2つとなり、一筆書きが出来るということが分かる。 図3に当てはめると、確かに4つの節点全てが、奇節点となっており、一筆書きが出来ないことが分かる。 このオイラーの用いた鮮やかな解法が、現在のグラフ理論に繋がっている。
関連リンク
[1]Wikipedia 一筆書き
[2]参考文献：野崎昭弘 (2015). "「P≠NP」問題 現代数学の難問" 講談社 ブルーバックス

ブックマーク

実行履歴

計算コラム