「すべての線」ではなく「すべての点」を通れる？
前回は、すべての線を一度ずつ通る「オイラー路」を紹介しました。
では、ルールを少し変えてみましょう。
地図の上にいくつかの町があり、それぞれが道路で結ばれているとします。
すべての町を一度ずつ訪れることはできるでしょうか？
今回は「すべての線」を通る必要はありません。
重要なのは、
すべての点を一度ずつ通ること。
このような道を数学では**ハミルトン路（Hamiltonian Path）**と呼びます。
一見するとオイラー路とよく似ていますが、実はまったく違う問題です。
そして、この考え方は配送、旅行計画、コンピューター、物流などにもつながっています。
ハミルトン路とは？
グラフには「頂点」と「辺」があります。
町を頂点、町を結ぶ道路を辺と考えてみましょう。
ハミルトン路とは、
グラフに存在するすべての頂点を、それぞれ一度ずつ通る道
のことです。
例えばA、B、C、D、Eという五つの町があるとします。
A → C → E → B → D
のように、五つの町を重複せずにすべて訪れることができれば、それはハミルトン路です。
すべての道路を使う必要はありません。
使わない道路が残っていても問題ありません。
ここがオイラー路との大きな違いです。
ハミルトン閉路とは？
すべての頂点を一度ずつ訪れたあと、
最後に出発した頂点へ戻ることができる道
をハミルトン閉路（Hamiltonian Cycle）と呼びます。
例えば、
A → B → C → D → E → A
のようなルートです。
Aからスタートして、他の頂点をそれぞれ一度ずつ訪れ、最後にAへ戻ります。
旅行に例えるなら、
「ホテルを出発して、観光地をそれぞれ一度ずつ訪れ、最後に同じホテルへ戻る」
ようなルートです。
オイラー路と何が違う？
ここが今回の最も重要なポイントです。
オイラー路は「辺」を一度ずつ通ります。
ハミルトン路は「頂点」を一度ずつ通ります。
例えば道路と町で考えると、とても簡単です。
オイラー路では、
「すべての道路を一度ずつ通れるか？」
を考えます。
ハミルトン路では、
「すべての町を一度ずつ訪問できるか？」
を考えます。
つまり、
オイラー＝線
ハミルトン＝点
と覚えるとわかりやすいでしょう。
オイラー路のような簡単な判定方法はある？
前回紹介したオイラー路では、奇数次数の頂点を数えるだけで、一筆書きが可能かどうかを判定できました。
奇数の頂点が0個または2個なら可能。
4個以上なら不可能。
とてもわかりやすいルールでした。
では、ハミルトン路にも同じような簡単なルールがあるのでしょうか？
実は、一般のグラフに対して
「これだけ確認すれば必ず判定できる」
というオイラー路のような単純な条件はありません。
ここがハミルトン問題の難しいところです。
頂点が少ない場合は実際にルートを試すことができます。
しかし、頂点が増えると候補となる順番が急激に増えていきます。
町が増えると候補が爆発する
例えば5つの町を訪問する順番を考えてみましょう。
単純に順番だけを考えると、
5! = 120
通りあります。
10個なら、
10! = 3,628,800
通りです。
20個になると、
20! は約243京通りという、とてつもなく大きな数になります。
もちろん実際のグラフでは道路が存在しない組み合わせを除外できるため、常にすべてを調べるわけではありません。
それでも頂点が増えるほど、候補を効率よく調べることが重要になります。
コンピューター科学でハミルトン路が重要なテーマになる理由の一つです。
有名な「巡回セールスマン問題」
ハミルトン閉路とよく関連して紹介される問題に、
巡回セールスマン問題（Traveling Salesman Problem：TSP）
があります。
セールスマンが複数の都市を訪問するとします。
条件は、
すべての都市を訪問し、
最後に出発地点へ戻ること。
さらに、
移動距離をできるだけ短くすること
です。
単に一周できるルートを見つけるだけではありません。
たくさんある候補の中から、より短いルートを探さなければなりません。
都市の数が増えると候補も急激に増えるため、非常に有名な最適化問題になっています。
私たちの生活にもつながっている
このような「多くの場所を効率よく回る」という考え方は、現実社会のさまざまな場面に登場します。
例えば、
- 商品の配送ルート
- 工場での作業順序
- 観光地を回る旅行計画
- ロボットの移動経路
- コンピューター回路の設計
- 物流ネットワーク
などです。
現実の問題では距離だけでなく、時間、料金、道路状況、営業時間など、さまざまな条件も加わります。
そのため、単純な数学パズルだった問題が、大規模な最適化問題へと発展します。
小さな問題なら自分でも挑戦できる
紙に六つの点を描き、いくつかの点を線で結んでみてください。
そして、
すべての点を一度ずつ通るルート
を探します。
線を全部使う必要はありません。
一つの頂点を二度訪れてはいけません。
見つかったら、次は最後にスタート地点へ戻れるか試してみましょう。
戻れればハミルトン閉路です。
たった六つの点でも、線のつなぎ方を変えるだけで簡単な問題にも難しい問題にもなります。
オイラーとハミルトンを間違えない覚え方
最後に二つの違いをもう一度整理しましょう。
オイラー路
すべての**辺（線）**を一度ずつ通る。
同じ頂点を複数回通ることはあります。
ハミルトン路
すべての**頂点（点）**を一度ずつ通る。
すべての辺を使う必要はありません。
迷ったら、
オイラーは線、ハミルトンは点
と覚えてください。
まとめ
ハミルトン路とは、グラフにあるすべての頂点を一度ずつ訪れる道です。
さらに最後に出発地点へ戻るものをハミルトン閉路と呼びます。
オイラー路が「すべての線」を一度ずつ通る問題なのに対し、ハミルトン路は「すべての点」を一度ずつ通る問題です。
似ているように見えますが、数学的には大きな違いがあります。
そしてハミルトン路には、オイラー路の奇数頂点ルールのような単純な一般判定法がありません。
だからこそ、頂点の数が増えるほど問題は面白く、難しくなります。
次に地図を見たとき、
「この場所を全部一度ずつ回るなら、どんなルートになるだろう？」
と考えてみてください。
いつもの地図が、一つの数学パズルに見えてくるかもしれません。
次回予告
「巡回セールスマン問題とは？最短ルートを探すと、なぜ急に難しくなる？」
次回は、すべての都市を回りながら最短ルートを探す、有名な数学とコンピューター科学の問題を紹介します。
