Hamilton閉路
概要
Hamilton閉路（Hamiltonian cycle）とは、グラフのすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路のことである。閉路の長さは 3 以上なので、Hamilton 閉路をもつグラフの頂点数は 3 以上である。正十二面体や立方体の頂点と辺のグラフは Hamilton 閉路をもつが、Petersen グラフや両側の頂点数が異なる二部グラフはもたない。すべての辺を 1 回ずつ通る Euler 閉路と違って簡単な判定条件は知られておらず、判定の問題は NP 完全である。十分条件として、頂点数 $n\ge3$ のグラフですべての頂点の次数が $n/2$ 以上なら Hamilton 閉路をもつという Dirac の定理と、それを一般化した Ore の定理がある。
前提知識: グラフ, 次数(グラフ), 連結グラフ, 二部グラフ
正十二面体の 20 個の頂点を 20 の都市、30 本の辺を都市を結ぶ道とみなす。ある都市を出発し、辺に沿って進んで、すべての都市をちょうど 1 回ずつ訪れて出発点に戻ることはできるだろうか。これは W. R. Hamilton が遊び（Icosian game）として売り出した問題で（rem-ham-cycle-history）、実際にそのような道順がある（下の ex-ham-cycle-dodecahedron に 1 つ書いた）。立方体の 8 個の頂点を $0$ と $1$ の 3 桁の列で表し、1 桁だけ違う頂点を辺で結ぶと、
$$
000\to001\to011\to010\to110\to111\to101\to100\to000
$$
はどの矢印でも 1 桁だけが変わり、8 頂点をちょうど 1 回ずつ通って戻る道順になっている。一方、辺の数が 15 本もある Petersen グラフ（prop-ham-cycle-petersen）では、どう回ってもこのような道順は作れない。
このように、グラフのすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路を Hamilton 閉路 という。すべての辺を 1 回ずつ通る Euler閉路 には「辺をもつ頂点がすべて 1 つの連結成分に入り、すべての頂点の次数が偶数である」という簡単な判定条件があるが、Hamilton 閉路にはそのような判定条件が知られておらず、判定の問題は NP完全 である（rem-ham-cycle-complexity）。本記事では、定義と基本的な例、存在のための必要条件（二部グラフの頂点数、頂点を除いたときの連結成分の個数）、十分条件である Ore の定理と Dirac の定理（頂点数 $n\ge3$ で最小次数が $n/2$ 以上なら Hamilton 閉路がある）の証明、Petersen グラフが Hamilton 閉路をもたないことの証明を述べる。
定義
以下、グラフは グラフ の記事の意味の有限な単純無向グラフとし、記法もそれに従う。とくに 閉路 は、長さ $\ell\ge3$ の閉歩道 $v_0,v_1,\dots,v_\ell$（$v_\ell=v_0$）で $v_1,\dots,v_\ell$ が相異なるものであり、道 は頂点が相異なる歩道である。頂点 $v$ の次数を $\deg(v)$、最小次数を $\delta(G)$ と書く（次数(グラフ)）。
$G=(V,E)$ を有限グラフとする。
- すべての頂点を通る閉路を $G$ の Hamilton 閉路（Hamiltonian cycle）という。すなわち、$V$ の元を 1 列に並べた $v_1,v_2,\dots,v_n$（$n=|V|\ge3$、各頂点がちょうど 1 回ずつ現れる）で、$v_1v_2,\ v_2v_3,\ \dots,\ v_{n-1}v_n,\ v_nv_1$ がすべて辺であるものが定める閉路である。
- すべての頂点を通る道を $G$ の Hamilton 路（Hamiltonian path）という。
- Hamilton 閉路をもつグラフを Hamilton グラフ（Hamiltonian graph）という。
閉路の長さは $3$ 以上なので、Hamilton 閉路をもつグラフの頂点数は $3$ 以上である。頂点数 $n$ のグラフの Hamilton 閉路の長さはちょうど $n$ である。Hamilton 閉路から 1 本の辺を除くと Hamilton 路が得られるが、逆は成り立たない（ex-ham-cycle-path-graph）。Hamilton 閉路は辺の集合として見ることが多く、同じ閉路を出発点や向きを変えて読んだものは同じ Hamilton 閉路とみなす。
直感
Hamilton 閉路は「全員を 1 回ずつ訪ねて帰ってくる巡回路」である。どこかの頂点を取り除くとグラフがばらばらになるなら、巡回路はその頂点を 2 回以上通らないと各部分を訪ねられないので、Hamilton 閉路はない（prop-ham-cycle-components）。逆に、どの頂点も多くの頂点と隣り合っていれば、巡回路を作り損ねても組み替えて延ばせるはずである。Dirac の定理（cor-ham-cycle-dirac）は、「どの頂点も全体の半分以上の頂点と隣り合う」という量的な条件がこの組み替えを保証することを述べる。どちらの条件も、必要十分な判定には届かない。
例と反例
$n\ge3$ とする。$n$ 頂点の完全グラフ $K_n$ の Hamilton 閉路（辺の集合として区別する）はちょうど $\frac{(n-1)!}{2}$ 個ある。
$K_n$ ではどの 2 頂点も隣接するので、$n$ 個の頂点の並べ方 $v_1,\dots,v_n$（$n!$ 通り）はどれも Hamilton 閉路を定める。1 つの Hamilton 閉路（長さ $n$）を定める並べ方は、出発点の選び方 $n$ 通りと向きの選び方 $2$ 通りで $2n$ 通りあり、$n\ge3$ なのでこれらの並べ方はすべて異なる。よって Hamilton 閉路の個数は $\frac{n!}{2n}=\frac{(n-1)!}{2}$ である。$\square$
たとえば $K_4$ には $3$ 個、$K_5$ には $12$ 個、$K_{10}$ には $181440$ 個の Hamilton 閉路がある。巡回セールスマン問題は、辺に長さが与えられた完全グラフで、長さの和が最小の Hamilton 閉路を求める問題である。候補の数 $\frac{(n-1)!}{2}$ は $n$ とともに急激に増えるので、すべてを調べる方法はすぐに使えなくなる。
$n\ge3$ とし、頂点 $1,2,\dots,n$ と辺 $12,23,\dots,(n-1)n$ からなる道グラフ $P_n$ を考える。$1,2,\dots,n$ は Hamilton 路であるが、$P_n$ には閉路が 1 つもない（木 である）ので Hamilton 閉路はない。この例は「Hamilton 路をもてば Hamilton 閉路をもつ」という含意を破る。頂点 $1$ の次数が $1$ であることが原因で、Hamilton 閉路をもつグラフではすべての頂点の次数が $2$ 以上である（閉路の上で各頂点は 2 本の辺に接続する）。
$n\ge2$ とする。$\{0,1\}^n$ を頂点集合とし、ちょうど 1 つの座標だけが異なる 2 頂点を辺で結んだグラフ（$n$ 次元の超立方体グラフ $Q_n$）は Hamilton 閉路をもつ。
$n$ に関する帰納法で、$Q_n$ の頂点の並べ方 $w_1,\dots,w_{2^n}$ で、隣り合うもの（$w_{2^n}$ と $w_1$ も含む）がちょうど 1 座標だけ異なるものを作る。$n=2$ では $00,01,11,10$ がそれである。$n$ で $w_1,\dots,w_{2^n}$ が得られたとし、頭に $0$ または $1$ を付けて
$$
0w_1,\ 0w_2,\ \dots,\ 0w_{2^n},\ 1w_{2^n},\ \dots,\ 1w_2,\ 1w_1
$$
と並べる。これは $\{0,1\}^{n+1}$ の元をちょうど 1 回ずつ含む。前半と後半の中では隣り合う 2 つは $w$ の部分がちょうど 1 座標だけ異なり、$0w_{2^n}$ と $1w_{2^n}$、および最後の $1w_1$ と最初の $0w_1$ は先頭の座標だけが異なる。長さ $2^{n+1}\ge3$ なので、これは $Q_{n+1}$ の Hamilton 閉路を定める。$\square$
$n=3$ の場合が冒頭の立方体の道順である。この並べ方は反射 Gray符号 とよばれる。$Q_1$ は 2 頂点と 1 辺だけで閉路をもたないので、$n\ge2$ の仮定は必要である。
正十二面体のグラフは次のように描ける。外側の五角形の頂点 $a_0,\dots,a_4$（$a_i$ と $a_{i+1}$ が隣接）、中間の十角形の頂点 $b_0,\dots,b_9$（$b_j$ と $b_{j+1}$ が隣接）、内側の五角形の頂点 $c_0,\dots,c_4$（$c_i$ と $c_{i+1}$ が隣接）をとり、$a_i$ と $b_{2i}$、$c_i$ と $b_{2i+1}$ を結ぶ（添字は $a,c$ では $5$ を法、$b$ では $10$ を法として読む）。頂点は 20 個、辺は 30 本で、どの頂点の次数も $3$ である。このグラフで
$$
a_0,a_4,b_8,b_9,b_0,b_1,c_0,c_4,c_3,b_7,b_6,a_3,a_2,b_4,b_5,c_2,c_1,b_3,b_2,a_1
$$
と進んで $a_0$ に戻る道順は、隣り合う頂点がすべて辺で結ばれていて、20 頂点をちょうど 1 回ずつ通るので、Hamilton 閉路である。
存在のための必要条件
$G=(V,E)$ が Hamilton 閉路をもつとする。$S\subset V$ を空でない部分集合で $S\ne V$ とするとき、$G$ から $S$ の頂点とそれに接続する辺を除いたグラフ $G-S$ の連結成分の個数は $|S|$ 以下である。
Hamilton 閉路を $v_1,v_2,\dots,v_n,v_1$ とし、頂点を円周上にこの順に並べて考える。$S$ の $s:=|S|$ 個の頂点を円周から取り除くと、残りの頂点は、円周上で連続して並ぶ（$S$ の頂点をはさまない）頂点の極大な列に分かれる。各列は $S$ の頂点の直後から始まるので、列の個数は $s$ 以下である。1 つの列の中で隣り合う頂点は閉路の辺で結ばれていて、その辺は $G-S$ の辺でもあるから、各列の頂点はすべて $G-S$ の同じ連結成分に属する。$G-S$ の頂点はどれかの列に属するので、連結成分の個数は列の個数 $s$ 以下である。$\square$
とくに $S$ を 1 頂点とすると、Hamilton 閉路をもつグラフは、どの 1 頂点を除いても連結のままである。
$G$ を二部分割 $(A,B)$ をもつ二部グラフとする。$G$ が Hamilton 閉路をもてば $|A|=|B|$ である。
二部グラフの辺は $A$ の頂点と $B$ の頂点を結ぶので、閉路 $v_1,\dots,v_n,v_1$ をたどると頂点は $A$ と $B$ に交互に属する。$v_n$ と $v_1$ も隣接するので、$A$ に属する $v_i$ と $B$ に属する $v_i$ は同数である。Hamilton 閉路はすべての頂点を 1 回ずつ通るので $|A|=|B|$ である。$\square$
完全二部グラフ $K_{2,3}$（$A=\{x,y\}$、$B=\{p,q,r\}$、$A$ と $B$ の頂点どうしをすべて結ぶ）は連結で、すべての頂点の次数が $2$ 以上であるが、$|A|=2\ne3=|B|$ なので prop-ham-cycle-bipartite により Hamilton 閉路をもたない。prop-ham-cycle-components からも分かる：$S=A$ を除くと $p,q,r$ の 3 つの孤立点が残り、連結成分が $3>|S|=2$ 個になる。この例は「連結で最小次数が $2$ 以上なら Hamilton 閉路をもつ」という含意を破る。
次の Petersen グラフは、長さ $5$ の閉路をもつので二部グラフではなく（prop-ham-cycle-bipartite は使えない）、すべての頂点の次数が $3$ で辺も多いが、Hamilton 閉路をもたない例として有名である（KT17 §5.3、図 5.17、PDF p. 103–104 は証明なしで述べている）。
頂点を $u_0,\dots,u_4,v_0,\dots,v_4$ とし、添字を $5$ を法として読んで、辺を
$$
u_iu_{i+1}\ (\text{外側の五角形}),\qquad v_iv_{i+2}\ (\text{内側の星形}),\qquad u_iv_i\ (\text{スポーク})\qquad(i=0,\dots,4)
$$
の 15 本とするグラフを Petersenグラフ という。すべての頂点の次数は $3$ である。Petersen グラフは Hamilton 閉路をもたない。
Hamilton 閉路 $C$（辺は 10 本）があるとして矛盾を導く。各頂点は $C$ のちょうど 2 本の辺に接続し、次数は $3$ なので、$C$ に含まれない辺はちょうど 1 本である。よって $C$ に含まれない 5 本の辺の集合 $F$ は、どの頂点もちょうど 1 本の辺に接続する（完全マッチング(グラフ理論)である）。
外側の頂点の集合 $U=\{u_i\}$ と内側の頂点の集合 $W=\{v_i\}$ の間を結ぶ辺はスポークだけである。$C$ をひと回りたどると $U$ と $W$ の間を行き来し、出発点に戻るので、$C$ に含まれるスポークの本数は偶数である。$C$ は $U$ と $W$ の両方の頂点を通るのでその本数は $2$ 以上であり、スポークは 5 本しかないので、$C$ に含まれるスポークは 2 本か 4 本、$F$ に含まれるスポークは 3 本か 1 本である。
（$F$ のスポークが 3 本の場合）$F$ のスポークで覆われない外側の頂点は 2 つあり、それらは $F$ の外側の辺で互いに結ばれるので、外側の五角形で隣り合う $u_a,u_{a+1}$ である。すると $F$ のスポークで覆われない内側の頂点は $v_a,v_{a+1}$ であり、これらも $F$ の辺で結ばれなければならない。しかし $v_a$ に隣接する内側の頂点は $v_{a+2}$ と $v_{a-2}$ だけで、$v_{a+1}$ ではない。矛盾である。
（$F$ のスポークが 1 本の場合）$i\mapsto i+1$ と添字をずらす写像はグラフの同型なので、そのスポークは $u_0v_0$ としてよい。$u_1,\dots,u_4$ は $F$ の外側の辺で互いに組にされ、使える外側の辺は $u_1u_2,u_2u_3,u_3u_4$ だけなので、組は $u_1u_2$ と $u_3u_4$ に決まる。$v_1,\dots,v_4$ の間の内側の辺は $v_1v_3,\ v_1v_4,\ v_2v_4$ だけで、$v_2$ に使えるのは $v_2v_4$ だけなので、組は $v_2v_4$ と $v_1v_3$ に決まる。よって
$$
F=\{u_0v_0,\ u_1u_2,\ u_3u_4,\ v_1v_3,\ v_2v_4\}
$$
であり、$C$ は残りの 10 本の辺からなる。とくに $u_0u_1,\ u_1v_1,\ v_1v_4,\ v_4u_4,\ u_4u_0$ は $C$ の辺で、これらは長さ $5$ の閉路をなす。この 5 頂点はそれぞれ $C$ のちょうど 2 本の辺に接続するが、その 2 本はどれもこの長さ $5$ の閉路の辺なので、$C$ をこの閉路からたどって外に出ることができない。したがって $C$ はこの長さ $5$ の閉路そのものになり、10 頂点を通ることに反する。$\square$
Petersen グラフには Hamilton 路はある。たとえば $u_0,u_1,v_1,v_3,v_0,v_2,v_4,u_4,u_3,u_2$ がそうである。
十分条件：Ore の定理と Dirac の定理
$G=(V,E)$ を頂点数 $n\ge3$ の有限グラフとする。隣接しない相異なる 2 頂点 $u,v$ のすべてについて
$$
\deg(u)+\deg(v)\ge n
$$
が成り立つならば、$G$ は Hamilton 閉路をもつ。
（連結性）隣接しない相異なる 2 頂点 $u,v$ をとる。$u$ の隣接頂点の集合 $N(u)$ と $v$ の隣接頂点の集合 $N(v)$ はどちらも $n-2$ 個の元からなる集合 $V\setminus\{u,v\}$ に含まれ、$|N(u)|+|N(v)|\ge n>n-2$ なので、共通の元 $w$ がある。よって $u,w,v$ は $u$ と $v$ を結ぶ道であり、$G$ は連結である（どの 2 頂点も隣接するなら明らかに連結）。
（最長の道）$G$ の道のうち長さ（辺の本数）$k$ が最大のもの $P=v_0,v_1,\dots,v_k$ をとる。$G$ は連結で $n\ge3$ なので辺をもち、$k\ge1$ である。さらに $k\ge2$ である。実際、$k=1$ とすると、最長の道 $x,y$ の $x$ や $y$ に第 3 の頂点 $z$ が隣接すれば $z,x,y$ や $x,y,z$ が長さ $2$ の道になるので、$x,y$ はほかの頂点と隣接せず、連結性と $n\ge3$ に反する。$v_0$ の隣接頂点 $w$ が $P$ の上になければ、$w,v_0,v_1,\dots,v_k$ は長さ $k+1$ の道になり、$k$ の最大性に反する。よって $v_0$ の隣接頂点はすべて $v_1,\dots,v_k$ のどれかであり、同様に $v_k$ の隣接頂点はすべて $v_0,\dots,v_{k-1}$ のどれかである。
（閉路を作る）$v_0$ と $v_k$ が隣接するなら、$v_0,v_1,\dots,v_k,v_0$ は長さ $k+1\ge3$ の閉路である。隣接しないとき、
$$
S:=\{\,i\mid 0\le i\le k-1,\ v_0v_{i+1}\in E\,\},\qquad T:=\{\,i\mid 0\le i\le k-1,\ v_iv_k\in E\,\}
$$
とおく。上で見たことから $|S|=\deg(v_0)$、$|T|=\deg(v_k)$ であり、仮定より $|S|+|T|\ge n$ である。$P$ の頂点は相異なるので $k+1\le n$、すなわち $k< n$ である。$S,T$ はどちらも $k$ 個の元からなる集合 $\{0,1,\dots,k-1\}$ に含まれ、$|S|+|T|\ge n>k$ なので、共通の元 $i$ がある。$v_0$ と $v_k$ は隣接しないので $0\notin T$、$k-1\notin S$ であり、$1\le i\le k-2$ である。このとき
$$
v_0,\ v_1,\ \dots,\ v_i,\ v_k,\ v_{k-1},\ \dots,\ v_{i+1},\ v_0
$$
は、辺 $v_iv_k$（$i\in T$）と $v_{i+1}v_0$（$i\in S$）を使う長さ $k+1$ の閉路である。どちらの場合も、$P$ の頂点全体を通る閉路 $C$ が得られた。
（すべての頂点を通ること）$C$ に含まれない頂点があるとする。$G$ は連結なので、$C$ の頂点 $x$ と $C$ の外の頂点 $y$ を結ぶ辺 $xy$ がある（$C$ の頂点から $C$ の外の頂点への道をとり、初めて $C$ の外に出る辺を選べばよい）。$C$ を $x$ から出発して 1 周し、$x$ の直前の頂点で止めると、$C$ の $k+1$ 個の頂点をすべて通る長さ $k$ の道が得られ、その先頭に $y$ を付け加えると長さ $k+1$ の道になる。これは $k$ の最大性に反する。よって $C$ はすべての頂点を通り、Hamilton 閉路である。$\square$
$G$ を頂点数 $n\ge3$ の有限グラフとし、すべての頂点の次数が $n/2$ 以上である（$\delta(G)\ge n/2$）とする。このとき $G$ は Hamilton 閉路をもつ。
どの 2 頂点 $u,v$ についても $\deg(u)+\deg(v)\ge\frac n2+\frac n2=n$ なので、thm-ham-cycle-ore の仮定が成り立つ。$\square$
- 頂点数 $n\ge3$ の仮定は外せない。2 頂点を 1 本の辺で結んだ $K_2$ は $n=2$、$\delta(K_2)=1=n/2$ を満たすが、閉路（長さ $3$ 以上）をもたないので Hamilton 閉路をもたない。
- 次数の下界 $n/2$ は下げられない。$m\ge1$ とし、完全二部グラフ $K_{m,m+1}$ を考える。頂点数は $n=2m+1\ge3$、最小次数は $m=\frac{n-1}{2}$ で $n/2$ にわずかに届かない。両側の頂点数が異なるので、prop-ham-cycle-bipartite により Hamilton 閉路をもたない（$m=2$ が ex-ham-cycle-k23 の $K_{2,3}$ である）。Ore の定理の仮定で見ても、$m+1$ 個の側の隣接しない 2 頂点の次数の和は $2m=n-1< n$ である。
- 逆は成り立たない。$n\ge5$ の閉路グラフ $C_n$ は Hamilton 閉路そのものであるが、最小次数は $2< n/2$ である。Dirac の定理と Ore の定理は十分条件であり、必要条件ではない。
cor-ham-cycle-dirac は Dirac による（Dir52）。KT17 §5.3 の定理 5.18（印刷 p. 80／PDF p. 104）は、頂点数 $n\ge3$ の仮定を書かずに「各頂点が $\lceil n/2\rceil$ 個以上の隣接頂点をもてば Hamilton グラフ」と述べている。同書は Hamilton 閉路を「すべての頂点を 1 回ずつ含む頂点の列 $x_1,\dots,x_n$ で、$x_ix_{i+1}$ と $x_1x_n$ が辺であるもの」と定義しており（PDF p. 103）、この定義では $K_2$ の列 $x_1,x_2$ も条件を満たすので、同書の中では矛盾はない。本記事のように閉路の長さを $3$ 以上とする定義（グラフ の記事の定義）では、ex-ham-cycle-dirac-sharp の (1) のとおり $n\ge3$ が必要である。thm-ham-cycle-ore は Ore による（Ore60）。本記事の証明は最長の道を組み替える方法で、KT17 の定理 5.18 の証明と同じ考え方である。
補足
与えられた有限グラフが Hamilton 閉路をもつかどうかを判定する問題は NP完全 である。この問題は Karp が 1972 年に NP 完全であることを示した 21 の問題の 1 つである（Kar72）。したがって、P対NP問題で P $\ne$ NP が正しければ、頂点数の多項式時間で判定する方法は存在しない。Lev §2.4.3（印刷 pp. 144–145／PDF p. 164–165）も、Hamilton 路の有無には簡単な判定法が知られておらず、NP 完全な問題の例であると述べている。これに対して Euler閉路 の有無は、各頂点の次数の偶奇と連結性を調べるだけで判定できる（同記事の注意「Hamilton 閉路との違い」）。
関連項目
- 前提: グラフ, 次数(グラフ), 連結グラフ, 二部グラフ
- 比較: Euler閉路, マッチング(グラフ理論)
- 例: 完全グラフ, 超立方体グラフ, Petersenグラフ
- 発展: 巡回セールスマン問題, NP完全, 四色定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
