同じルートを踏むことなく、すべての点や線を一筆で描くパズルで遊んだことはありますか？与えられた図形を一筆で描くゲームです。9つのドットを一筆で全部通過する「ナインドットパズル」や、脳トレ問題としても扱われているこの「一筆書き」は、数学でも扱われてきた立派な研究だったりします。
今回はそんな一筆書き問題について紹介します。
一筆書き問題の誕生
筆書き問題が数学として取り扱われるようになった背景には、18世紀の「ケーニヒスベルクの橋の問題」があります。この問題は、当時のプロイセン（現在のロシアのカリーニングラード）にあるケーニヒスベルクという町に架かる7つの橋に由来しています。町の人々は、すべての橋を一度ずつ渡って出発点に戻ることができるかどうかを考えました。
▽ケーニヒスベルクについて興味がある方はこちらもどうぞ！
math-math-fun100.hatenablog.jp
一筆書き問題の解決
この問題を解決したのが、スイスのスーパー数学者レオンハルト・オイラーです。オイラーは1736年にこの問題に取り組み、その結果、グラフ理論という新しい学問分野の基礎を築きました。彼は、橋と陸地を点と線で構成された単純な「グラフ」で表し、すべての橋を一度ずつ渡ることができるかどうかを数学的に証明しました。
オイラーの研究によって、オイラー閉路（すべての辺を一度だけ通って元の頂点に戻るルート）と、オイラー路（すべての辺を一度だけ通るが、元の頂点とは異なる頂点で終わることもあるルート）が存在する条件が明確になりました。
1. オイラー閉路（オイラーグラフ）の条件
オイラー閉路は、すべての辺を一度だけ通って元の頂点に戻る閉路です。オイラー閉路が存在するためには、次の条件が満たされている必要があります：
- すべての頂点の次数が偶数であること（次数とは、その頂点に接続する辺の数のことです）。
- グラフが連結していること（すべての頂点が何らかの形でつながっていること）。
この条件を満たすグラフは「オイラーグラフ」と呼ばれ、すべての辺を一度だけ通る閉路を持ちます。
2. オイラー路（オイラー半グラフ）の条件
オイラー路は、すべての辺を一度だけ通るが、出発点と終点が異なる場合があります。オイラー路が存在するための条件は次の通りです：
- 奇数の次数を持つ頂点がちょうど2つであること（残りの頂点はすべて偶数次数でなければならない）。
- グラフが連結していること。
この条件を満たすグラフは、オイラー路が存在し、奇数の次数を持つ頂点の1つが出発点、もう1つが終点となります。
一筆書き問題の現実社会における活用
一筆書き問題（オイラー路問題としても知られる）は、グラフ理論の一分野で、現実社会において非常に重要な役割を果たしています。以下に、現実社会で一筆書き問題がどのように役立っているかを紹介します。
1. 物流と配送計画
物流や配送業では、経路の最適化が非常に重要です。特に、すべての地点を一度だけ通り、効率的に配送したり、メンテナンス作業を行ったりする必要があります。
-
郵便配達やゴミ収集：郵便配達員がすべての家を回る際、またはゴミ収集車がすべてのルートを一度だけ通る最適な経路を見つける問題は、オイラー路に関連しています。各地点（家やゴミ集積所）を一度だけ訪れることが要求されるため、この問題を解くことで、効率的なルートが見つかり、燃料コストや労働時間を削減できます。
-
ケーブル敷設やメンテナンス作業：電線や通信ケーブルを敷設する際や、メンテナンス作業で各地点を回る際にも、同じ道を何度も通らずに効率よく移動する方法を計画するのにオイラー路が役立ちます。
2. ネットワーク設計
コンピュータネットワークや通信ネットワークの設計でも、一筆書き問題が活用されています。ネットワークを構築する際には、すべてのノード（地点）を効率的に接続する必要があります。無駄な経路を省いて通信を効率化するためには、各ノードを一度だけ通る経路を見つけることが重要です。
- データ転送の最適化：データパケットが通信ネットワーク内を移動する際、無駄な経路を避け、効率的にルートを決めるためには、オイラー路的な考え方が応用されます。これにより、ネットワークの遅延や負荷を最小限に抑えることができます。
3. 回路設計
電子回路の設計では、プリント基板（PCB）における配線の最適化が重要です。回路基板上で、すべての接続を一度だけ通るように経路を引く問題は、グラフ理論とオイラー路問題に基づいています。
4. ドローンや自動運転車のルート最適化
ドローンや自動運転車が、指定されたエリアを監視したり物を運んだりする場合、効率的にすべての地点を回る経路を決める必要があります。一筆書き問題（オイラー路問題）の解法は、ドローンや自動運転車のルート最適化に役立っています。
- 監視や巡回：ドローンが指定されたエリアを飛行して監視する際、すべての領域を無駄なく巡回するためにオイラー路問題の考え方が使われます。また、自動運転車が配送業務を行う際にも、この経路最適化が適用されます。
5. 観光や旅行の経路計画
観光業や旅行業では、観光客が一度に複数の観光地を効率よく回れるように、最適な経路を計画することが求められます。すべての観光地を一度だけ訪れ、無駄な移動を避ける経路を見つけることができれば、観光客の時間や交通費を節約できます。
- 観光バスのルート設計：観光バスやガイドツアーなどでは、オイラー路の概念を使って、最も効率的に観光スポットを回れる経路が計画されることがあります。
画像処理とグラフィックス
画像処理やコンピュータビジョンの分野でも、オイラー路は利用されています。輪郭抽出や画像のパターン認識において、一筆書きのように経路をたどることで、画像内の形状や境界を効率よく処理できる方法があります。
まとめ
一筆書き問題（オイラー路問題）は、物流、通信、ネットワーク設計、回路設計、画像処理など、さまざまな分野で経路の最適化に関する現実的な問題を解決するために利用されています。これにより、コスト削減や効率化が可能となり、特に交通、電力、データ通信、エネルギー消費の最適化が重要視される現代社会において、非常に有用なツールとして活用されています。
もしかしたら、あなたの身近でも一筆書き問題で解決できる日常の問題があるかもしれません。たとえば帰り道の最適ルート（どれだけ信号を回避して家に帰れるか、距離を短くできるか、良く吠える犬のいる家を回避できるかなど）の探索や、アドベンチャーゲームやシミュレーションゲームの超効率化プレイなど。選択肢がたくさんあり、そのうちの必須ポイントを線でつないだグラフにおいて、最も無駄なく全ポイントをめぐるための経路を探るのが「一筆書き問題」です。
「あ、これって一筆書き問題で解決できそう」という事柄があったら、ぜひコメント欄で教えてくださいね！
