計算コラム
(99) 一筆書きとグラフ理論
2020/06/11
ある図形が与えられたときに、"一筆書きができるか?"という判定問題は、アルゴリズムの題材によく使われる他、
算数の入試問題に使われることもある。簡単な図形であれば、図形を1つ1つ手でなぞって判定することも可能だが、複雑な図形になってくると困難である。
![]() 問. 18世紀の初めにプロイセン王国のケーニヒスベルク(現ロシア連邦カリーニングラード)の 中央にはプレーゲル川があり、図2のような7つの橋が架かっていた。 ある地点から出発して、7つの橋を1回ずつ渡ることはできるか? ![]() この問題について、18世紀スイスの大数学者レオンハルト・オイラーは図3のような節点(node)、辺(edge)からなる"グラフ"に置き換えて考えた。 ![]() 一筆書きが出来る図形はオイラー路と呼ばれ、辺が偶数本繋がっている節点を偶節点、奇数本繋がっている節点を奇節点とするとき、 オイラー路が存在するためには、奇節点が0個または2個でなければならない。 図1(a)を見ると偶節点4つ、図1(b)は偶節点4つ・奇節点2つとなり、一筆書きが出来るということが分かる。 図3に当てはめると、確かに4つの節点全てが、奇節点となっており、一筆書きが出来ないことが分かる。 このオイラーの用いた鮮やかな解法が、現在のグラフ理論に繋がっている。 |
関連リンク | |
[1]Wikipedia 一筆書き [2]参考文献:野崎昭弘 (2015). "「P≠NP」問題 現代数学の難問" 講談社 ブルーバックス | |
![]() |