効率的な散歩ルートはどう決める？「一筆書き（オイラー路）」で日常をハックする数学
天気の良い日に近所を散歩するのは心地よいものですが、せっかくなら「すべての道を一度もダブらずに歩ききってみたい」と思ったことはありませんか？
一見、単なる暇つぶしのパズルのようですが、これは数学の世界で「グラフ理論」と呼ばれる非常に実用的な分野の入り口です。18世紀に大数学者レオンハルト・オイラーが解き明かした「一筆書き」の法則を使えば、いつもの散歩ルートや、ゴミの収集経路、さらには現代の物流ネットワークまで、効率的にハックすることができます。
出典: 始まりは「ケーニヒスベルクの橋」のパズル
グラフ理論の起源は、かつて東プロイセンにあったケーニヒスベルク（現在のロシア・カリーニングラード）という街にあります。
この街の中央にはプレーゲル川が流れており、そこには図のように7つの橋が架かっていました。当時の人々は、ある疑問を抱いてパズルを楽しんでいました。 「どの橋も一度だけ渡って、すべての橋を渡りきるルートはあるだろうか？（ただし同じ橋を2度渡ってはならない）」
多くの人が挑戦しましたが、誰も成功ルートを見つけられませんでした。そこで登場したのが、数学者のレオンハルト・オイラーです。
オイラーが示した「地図の単純化」と一筆書きの条件
オイラーは1736年、この問題を解くために画期的なアプローチを取りました。川で区切られた陸地を「点（頂点）」とし、架かっている橋を「線（辺）」として簡略化した図（これを数学で「グラフ」と呼びます）に置き換えたのです。
実際の地図の細かな地形や距離は無視し、「点と点がどのように線で結ばれているか」という接続関係だけを抽出しました。これが、現代でいう「トポロジー（位相幾何学）」や「グラフ理論」の誕生の瞬間でした。
オイラーはこの単純化した図を用いて、すべての線をちょうど1回ずつ通って描く「一筆書き（オイラー路）」ができるためのルールを発見しました。ルールは非常にシンプルです。
それぞれの点（交差点）に集まっている線の数を数え、その数が奇数である点（奇点）に注目します。
- 奇点が0個のとき：グラフ上のどこからスタートしても、出発点に戻ってくる一筆書き（オイラー閉路）が必ず可能です。
- 奇点が2個のとき：一方の奇点からスタートし、もう一方の奇点で終わる一筆書き（オイラー路）が必ず可能です。
- 奇点がそれ以外のとき（奇点が1個、または3個以上のとき）：絶対に一筆書きはできません。
ケーニヒスベルクの橋の図を点と線に置き換えてみると、4つの点すべての線の数が奇数（3本、3本、3本、5本）であり、奇点が4個ありました。したがって、「すべての橋を一度ずつ渡るルートは存在しない」ということが数学的に証明されたのです。
現代のテクノロジーを支えるオイラーの数学
オイラーが解決したこの一筆書きの法則は、現代社会の至る所で応用されています。
例えば、ゴミ収集車の巡回ルートです。街中の道路を最もダブりが少なく、無駄なく回るためのルートを設計する問題は「中国の郵便配達問題（Route Inspection Problem）」として知られており、グラフ理論を使って最適化されています。
また、半導体の基板設計においても、電気を通す微細な配線をどう引けば交差せずに効率よく接続できるかという問題に、グラフ理論が直接役立っています。私たちが使っているスマートフォンの頭脳も、オイラーの発見した数学の延長線上にあるのです。
散歩ルートをオイラー路でハックしてみよう
もし今日の夕方、散歩に出かけるなら、頭の中でご近所の簡略地図を作ってみてください。
大通りや小路を「線」、交差点を「点」とします。それぞれの交差点に集まる道路の数をカウントしてみて、奇数本の道路が集まる交差点が「2個以下」であれば、そのエリアは一筆書き（ダブりなしのルート）で散歩できます。
もし奇点が2個なら、必ずそのうちの一方から歩き始めてください。そうすれば、最後にもう一つの奇点に到着し、すべての道を網羅した「完全散歩」が達成できるはずです。数学は机の上だけでなく、私たちの足元にも広がっています。
お役立ち情報
- 一般社団法人 日本数学会（日本語）: 日本数学会 - 日本の数学界を代表する学会。教育・普及活動も行っており、数学の面白さを伝えるイベント情報や記事が掲載されています。
- 公益財団法人 日本数学検定協会（日本語）: 数検の学習コンテンツ - 数学の歴史や日常に潜む数学パズルなど、大人でも楽しめる読み物コンテンツを多数公開しています。
- J-STAGE グラフ理論と最適化（日本語）: グラフ理論を用いたルート最適化の論文 - 物流や都市工学における巡回ルート最適化の実用的な研究論文を検索・閲覧できます。