一筆書き
出典: フリー百科事典『ウィキペディア（Wikipedia）』
一筆書き（ひとふでがき）とは、ペンを紙から一度も離さずに図形を描くことである。例えば、三角形「△」や四角形「□」は一筆書き可能だが、十字「+」は一筆書きできない。
与えられた図形が一筆書き可能かどうかという問題の例として、「ケーニヒスベルクの問題」が知られている。
目次 |
[編集] ケーニヒスベルクの問題
[編集] 問題
ケーニヒスベルク（現在のロシア領カリーニングラード）を流れるプレーゲル川には、市の中心地で大聖堂の建っている中州クナイプホーフ島ともう一つの大きな中洲があり、それらを中心に両岸へ以下のように7つの橋が架かっている。
この7つの橋を各1度ずつ通って、元の場所に戻ってくることができるかどうか? ただし、同じ橋を2度以上通ってはならない。
[編集] グラフ理論との関連
1736年、レオンハルト・オイラーは、この問題を以下のグラフに置き換えて考えた。
このグラフが一筆書き可能であれば、ケーニヒスベルクの橋を全て1度ずつ通って戻ってくるルートが存在することになる。
そして、オイラーは、このグラフが一筆書きできないことを証明し、ケーニヒスベルクの問題を否定的に解決した。
[編集] 一筆書き可能かどうかの判定法
ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである。
- すべての頂点の次数が偶数 → 運筆が起点に戻る場合（閉路）
- 次数が奇数の頂点の数が2で、残りの頂点の次数は全て偶数 → 運筆が必ずしも起点にもどらない場合（路）
[編集] 迷路の解法
- すべての頂点の次数が偶数 → ある頂点から出発し、元の頂点に戻り、さらにその頂点から出発し、元の頂点に戻る順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。
- 次数が奇数の頂点の数が2で、残りの頂点の次数は全て偶数 → ある奇点から出発し、もう一方の奇点に戻る順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。
