ハミルトン閉路の有無

具体的なグラフについて、ハミルトン閉路を構成して存在を示せる。また、2 部グラフの部集合の大きさ（ $K_{m, n}$ は $m = n \geq 2$ のときに限る）や、頂点を除いたときの連結成分の数を使って、ハミルトン閉路がないことを示せる

前提

2 部グラフと奇閉路（大学数学グラフ理論）

この技能までの道筋（7 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）

説明

グラフのすべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路を、ハミルトン閉路といいます。この技能では、具体的なグラフについてハミルトン閉路を実際に書き出して「ある」ことを示す方法と、2 部グラフの部集合の大きさや頂点を除いたときの連結成分の数を使って「ない」ことを示す方法を学びます。巡回ルートの設計や、グラフの構造の調べ上げなどで使います。

なぜそうしてよいのか

頂点数 $n \geq 3$ のグラフ $G$ で、頂点を $v_{1}, v_{2}, \dots, v_{n}$ と重複なく並べ、 $v_{1} v_{2}, v_{2} v_{3}, \dots, v_{n - 1} v_{n}, v_{n} v_{1}$ がすべて辺になっているとき、閉路 $v_{1} v_{2} \dots v_{n} v_{1}$ をハミルトン閉路といいます。辺はすべて使う必要はありません（すべての辺を 1 回ずつ通るオイラー閉路とは別物です）。「ある」ことは、こうした並びを 1 つ見せれば示せます。また、閉路は各頂点で 2 本の辺を使うので、次数 1 以下の頂点があればハミルトン閉路はありません。

「ない」ことを示す道具の 1 つ目は 2 部グラフです。 $G$ が部集合 $A, B$ をもつ 2 部グラフなら、辺は必ず $A$ と $B$ を結ぶので、閉路をたどると $A, B, A, B, \dots$ と交互に頂点が現れ、出発点に戻ります。ハミルトン閉路はすべての頂点を 1 回ずつ通るので $∣ A ∣ = ∣ B ∣$ でなければなりません（閉路の長さ $n$ が偶数になるのは、前提の「2 部グラフは奇閉路をもたない」とも合っています）。たとえば $K_{m, n}$ は、 $m \neq = n$ ならハミルトン閉路をもちません。逆に $m = n \geq 2$ なら、 $A = {a_{1}, \dots, a_{n}}$ 、 $B = {b_{1}, \dots, b_{n}}$ として $a_{1} b_{1} a_{2} b_{2} \dots a_{n} b_{n} a_{1}$ がハミルトン閉路です（ $m = n = 1$ の $K_{1, 1}$ は頂点が 2 個で閉路をもちません）。

2 つ目は頂点の除去です。空でない頂点集合 $S$ （ $k = ∣ S ∣$ 個）を $G$ から除いたグラフを $G - S$ とし、その連結成分の個数を $c (G - S)$ と書きます。ハミルトン閉路 $C$ から $k$ 個の頂点を除くと、円周を $k$ か所で切るのと同じで、残りは高々 $k$ 本の道（ひとつながりの部分）に分かれます。 $C$ の辺は $G$ の辺なので、それぞれの道は $G - S$ のどれか 1 つの連結成分に入り、しかも $G - S$ のすべての頂点がどれかの道に乗っています。よって $c (G - S) \leq ∣ S ∣$ です。したがって、 $c (G - S) > ∣ S ∣$ となる $S$ が 1 つでも見つかれば、ハミルトン閉路はありません。

手順

頂点数が $3$ 以上であることと、各頂点の次数が $2$ 以上であることを確認する（次数 $1$ 以下の頂点があればハミルトン閉路はない）。
すべての頂点を重複なく並べた列 $v_{1} v_{2} \dots v_{n} v_{1}$ を試し、隣り合う頂点の組と $v_{n} v_{1}$ がすべて辺かを確かめる。見つかればハミルトン閉路が「ある」。
見つからないときは 2 部グラフかどうかを 2 色の塗り分けで調べ、2 部グラフで部集合の大きさが $∣ A ∣ \neq = ∣ B ∣$ ならハミルトン閉路は「ない」。
頂点集合 $S$ を除いて連結成分を数え、 $c (G - S) > ∣ S ∣$ となる $S$ があればハミルトン閉路は「ない」。次数の大きい頂点や、グラフをつないでいる「要」の頂点を $S$ に選ぶと見つけやすい。

例題

次のア〜ウのグラフのうち、ハミルトン閉路をもつものをすべて選べ。
ア: $K_{3, 3}$
イ: $K_{2, 4}$
ウ: 頂点集合 ${1, 2, 3, 4, 5}$ 、辺集合 ${12, 13, 23, 14, 15, 45}$ のグラフ

例題の解答

ア: $K_{3, 3}$ の部集合を ${a_{1}, a_{2}, a_{3}}$ 、 ${b_{1}, b_{2}, b_{3}}$ とする。どの $a_{i}$ と $b_{j}$ も辺で結ばれているので、手順 2 により、列 $a_{1} b_{1} a_{2} b_{2} a_{3} b_{3} a_{1}$ は 6 頂点すべてを 1 回ずつ通り、隣り合う組はすべて辺である。よってハミルトン閉路をもつ。

イ: $K_{2, 4}$ は部集合の大きさが $2$ と $4$ の 2 部グラフである。手順 3 により、ハミルトン閉路があれば頂点は 2 つの部集合から交互に現れるので部集合の大きさは等しくなるはずだが、 $2 \neq = 4$ なのでハミルトン閉路はない。（手順 4 でも、大きさ 2 の部集合を $S$ として除くと 4 つの孤立点が残り $c (G - S) = 4 > 2$ となって確かめられる。）

ウ: 手順 1 で次数を見ると、頂点 1 の次数は 4、ほかの頂点の次数は 2 で、すべて 2 以上なのでこれだけでは判定できない。手順 4 で $S = {1}$ とすると、残る辺は $23$ と $45$ だけなので、 $G - S$ の連結成分は ${2, 3}$ と ${4, 5}$ の 2 個である。 $c (G - S) = 2 > 1 = ∣ S ∣$ なのでハミルトン閉路はない。

以上より、ハミルトン閉路をもつのはアだけである。

答え:

ア

よくある誤り

部集合の大きさが等しい 2 部グラフなら必ずハミルトン閉路があるとしてしまう誤り。 $∣ A ∣ = ∣ B ∣$ は必要条件にすぎない。たとえば頂点 ${1, 2, 3, 4}$ 、辺 ${12, 23, 34}$ の道は部集合 ${1, 3}, {2, 4}$ の大きさが等しいが、頂点 1 の次数が 1 なのでハミルトン閉路はない。正しくは、 $∣ A ∣ \neq = ∣ B ∣$ のときに「ない」と結論できるだけである。
連結成分が 2 個以上に分かれたらハミルトン閉路はないとしてしまう誤り。比べる相手は除いた頂点の個数で、 $c (G - S) > ∣ S ∣$ のときに限り「ない」といえる。たとえば $C_{4}$ （閉路 $12341$ ）から $S = {1, 3}$ を除くと連結成分は 2 個だが、 $c (G - S) = 2 = ∣ S ∣$ なので矛盾はなく、実際 $C_{4}$ 自身がハミルトン閉路である。
どの $S$ についても $c (G - S) \leq ∣ S ∣$ が成り立つことを確かめただけで、ハミルトン閉路があるとしてしまう誤り。この条件も必要条件にすぎない。たとえばペテルセングラフはすべての $S$ でこの条件を満たすが、ハミルトン閉路をもたないことが知られている。「ある」ことを示すには、実際に閉路 $v_{1} v_{2} \dots v_{n} v_{1}$ を書き出す必要がある。
すべての辺を 1 回ずつ通るオイラー閉路と混同し、使わない辺があってはいけないと考えてしまう誤り。ハミルトン閉路が通る必要があるのはすべての頂点で、辺は $n$ 本だけ使えばよい。たとえば $K_{4}$ （辺 6 本）のハミルトン閉路 $12341$ は辺を 4 本しか使わない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

ハミルトン閉路の有無

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題