12.9 特別な歩道と閉歩道
12.9.1 Euler 周遊
ボストン美術館の全ての廊下をちょうど一度ずつ通るように歩き回ることはできるだろうか？ この問題はグラフを使ってモデル化できる: 頂点が廊下に対応し、辺が廊下間の接続関係を表すグラフを考えればよい。例えば、美術館の間取りが図 \(\text{12.16}\) のグラフによって表されるとき、全ての廊下を一度ずつ通ることは可能だろうか？
グラフ理論という数学の分野は、十七世紀に活躍した有名な数学者 Leonhard Euler が Königsberg にある \(7\) 個の橋をちょうど一度ずつ通るルートがあるかどうかを考えたときに始まった1 ── これは本質的に先述したボストン美術館の廊下に関する問題と同一である。
グラフの Euler 周遊 (Euler tour) とは、全ての辺をちょうど一度ずつ含む閉歩道を言う2。Euler 周遊を持つグラフは簡単に特定できる:
「連結なグラフ \(G\) が Euler 周遊を持つ」と「\(G\) の頂点の次数が全て偶数」は同値である。
この定理の証明は簡単なステップに分解して問題 12.44 に示した。この証明からは、Euler 周遊が存在するとき実際にそれを構築する手続きが得られる: 簡単に言えば、空グラフから始めて「残っている」辺からなる閉歩道を連結し続けると最終的に Euler 周遊となる。
同様に、全ての辺をちょうど一度ずつ含む閉歩道でない (始点と終点が異なる) 歩道を Euler 歩道 (Euler walk) と呼ぶ。定理 12.9.1 の簡単な系として、連結なグラフは次数が奇数の頂点が \(2\) 個のとき、かつそのときに限って Euler 歩道を持つことが言える。図 \(\text{12.16}\) のグラフには次数が奇数の頂点が \(2\) 個あるので、このグラフは Euler 歩道を持つものの Euler 周遊は持たない。
12.9.2 Hamilton 閉路
Hamilton 閉路は Euler 周遊の粗暴な従兄弟である。
\(G\) をグラフとする。\(G\) の全ての頂点をちょうど一度ずつ含む閉路を、\(G\) の Hamilton 閉路 (Hamiltonian cycle) と呼ぶ。同様に、\(G\) の全ての頂点をちょうど一度ずつ含む路を \(G\) の Hamilton 路 (Hamiltonian path) と呼ぶ。
Hamilton 閉路は Euler 周遊とよく似ている ── 定義の「全ての辺」を「全ての頂点」に変えれば得られる ── ものの、Hamilton 閉路または Hamilton 路を見つける問題は Euler 周遊または Euler 歩道を見つける問題より格段に難しい。Hamilton 閉路を持つグラフの簡単な特徴付けは発見されていない。さらに、グラフが Hamilton 閉路を持つかどうかを判定する問題は第 3.5 節で触れた SAT と同じカテゴリに属する: グラフが Hamilton 閉路を持つかどうかを効率的に判定する手続き (または、そのような手続きが存在しないことの証明) を発見すると、Clay 研究所から百万ドルが授与される。
12.9.3 巡回セールスパーソン問題
多くの応用では、グラフの辺に数値で表されるコストや重みが割り当てられる。例えばグラフの頂点が都市を表し、辺のコストが距離に等しいグラフでは、ロサンゼルスとニューヨークを結ぶ辺のコストがニューヨークとボストンを結ぶ辺のコストよりずっと大きくなる。
Hamilton 閉路を見つける問題では物足りないとでも言うかのように、重み付きグラフに対して辺の重みの和が最小の Hamilton 閉路を見つける必要が生じる場面がある。これは有名な巡回セールスパーソン問題 (traveling salesperson problem) である。例えば、図 \(\text{12.17}\) のグラフの全ての頂点をちょうど一度ずつ通る閉路であって重みが \(15\) のものを見つけられるだろうか？
