一筆書きには「運」ではなくルールがある
紙に星や家の形を描いて、
「ペンを紙から離さず、同じ線を二度通らずに全部描けるかな？」
と挑戦したことはありませんか？
何度も線を引き直し、
「最初の場所を間違えたのかな？」
と思った経験がある人もいるでしょう。
しかし、一筆書きには運や勘ではなく、数学的なルールがあります。
前回紹介した「ケーニヒスベルクの七つの橋問題」で、数学者レオンハルト・オイラーは複雑な地図を「点」と「線」だけに置き換えました。
この考え方から生まれた重要な概念が、
オイラー路（Euler Path）
と
オイラー閉路（Euler Circuit）
です。
今回は、この二つの違いと、一筆書きができるかどうかを一瞬で判断する方法を紹介します。
オイラー路とは？
グラフのすべての辺を、
同じ辺を二度通らずに一度ずつ通る道
をオイラー路と呼びます。
ここで大切なのは「すべての点を一度ずつ通る」のではなく、
すべての線を一度ずつ通る
ということです。
同じ頂点を何度通っても構いません。
しかし、同じ辺を二度使うことはできません。
例えば道路のネットワークなら、
すべての道路を一度ずつ通るルートを探す問題だと考えるとわかりやすいでしょう。
オイラー閉路とは？
オイラー路の中でも、
出発した頂点に最後に戻ってくるもの
をオイラー閉路と呼びます。
つまり、
出発 → すべての辺を一度ずつ通る → 出発地点へ戻る
というルートです。
オイラー路はスタートとゴールが違っても構いません。
一方、オイラー閉路は必ずスタートとゴールが同じになります。
この違いを覚えておくと、一筆書き問題がとても理解しやすくなります。
カギは「奇数の頂点」
では、一筆書きができるかどうかをどうやって判断するのでしょうか。
重要なのは各頂点の次数です。
次数とは、その頂点につながっている辺の本数のことです。
例えば、
3本の線が集まる頂点なら次数3。
4本なら次数4です。
そして、次数が奇数の頂点が何個あるのかを数えます。
この数だけで、多くの一筆書き問題を判定できます。
奇数の頂点が0個の場合
すべての頂点の次数が偶数なら、
オイラー閉路
を作ることができます。
つまり、好きな場所から出発し、
すべての線を一度ずつ通って、
最後に同じ場所へ戻ることができます。
なぜでしょうか。
途中の頂点に入ったら、別の線を使って出なければなりません。
「入る線」と「出る線」が一組になるため、線の本数が偶数なら自然に組を作ることができます。
奇数の頂点が2個の場合
奇数の次数を持つ頂点がちょうど2個なら、
オイラー路は存在しますが、オイラー閉路は存在しません。
一筆書きを成功させるためには、
奇数の頂点の一方からスタートし、
もう一方の奇数頂点で終了します。
つまり、スタート地点とゴール地点が決まっているのです。
適当な場所から始めると失敗することがあります。
一筆書きで「スタート地点が重要」と言われる理由はここにあります。
奇数の頂点が4個以上なら？
奇数の頂点が4個以上ある場合、
すべての辺を一度ずつ通るオイラー路は作れません。
前回のケーニヒスベルクの七つの橋問題では、
四つの頂点の次数が
3、3、3、5
でした。
つまり奇数の頂点が4個あったため、どんな順番で橋を渡っても成功しなかったのです。
何百回試しても結果は同じです。
ルートをまだ発見していないのではなく、
そもそも条件を満たすルートが存在しない
からです。
3秒で一筆書きを判定する方法
一筆書きの図形を見たら、すぐに描き始める必要はありません。
まず次の三つだけ確認しましょう。
奇数の頂点が0個
一筆書き可能。
しかもスタート地点へ戻ることができます。
奇数の頂点が2個
一筆書き可能。
ただし、一方の奇数頂点から始め、もう一方で終了します。
奇数の頂点が4個以上
一筆書き不可能。
このルールを知っていれば、複雑そうな図でも線を一本ずつ数えるだけで答えを予測できます。
オイラー路は現実社会でも役立つ
一筆書きは単なるパズルではありません。
「すべての道や区間を効率よく通る」という問題は現実社会にも存在します。
例えば、
道路の点検、
除雪車の経路、
ゴミ収集、
郵便配達、
道路清掃、
通信ネットワークの確認
などです。
現実の問題では、すべての道を一度だけ通れるとは限りません。
その場合は、どの道を重複して通れば全体の移動距離を最小にできるかを考えます。
この考え方は、オイラー路から発展した「中国人郵便配達問題」と呼ばれる最適化問題にもつながっています。
「点」ではなく「線」を見る数学
オイラー路の面白いところは、
図形そのものの美しさではなく、点と線のつながり方だけを見ることです。
線が曲がっていても、長くても短くても関係ありません。
数学的に重要なのは、
どの頂点とどの頂点がつながっているのか
です。
この考え方は、交通網、インターネット、SNS、物流など、巨大なネットワークを分析するときにも役立ちます。
まとめ
オイラー路とは、グラフのすべての辺を一度ずつ通る道です。
オイラー閉路は、さらに最後に出発地点へ戻る道です。
判定するときに重要なのは、奇数の次数を持つ頂点の数です。
0個 → オイラー閉路が可能
2個 → オイラー路が可能
4個以上 → 一筆書きは不可能
このルールを知るだけで、一筆書きパズルを見る目が大きく変わります。
次に一筆書き問題を見つけたら、いきなり線を描かず、まず奇数の頂点を数えてみてください。
答えは、線を一本も引く前から見えているかもしれません。
次回予告
「ハミルトン路とは？全部の点を一度ずつ通る数学パズル」
次回は「すべての線」ではなく「すべての点」を一度ずつ通る、似ているようでまったく違う問題を紹介します。
