グラフ理論の問題

難易度 1教科書の例題レベル大学数学グラフ理論

次の $5$ つの単純無向グラフ $G_{1}, G_{2}, G_{3}, G_{4}, G_{5}$ のうち、ハミルトン閉路（すべての頂点をちょうど $1$ 回ずつ通って出発点に戻る閉路）をもつものの番号をすべて求め、集合で答えよ。

$G_{1}$ ：完全 2 部グラフ $K_{2, 3}$
$G_{2}$ ：完全 2 部グラフ $K_{3, 3}$
$G_{3}$ ：頂点集合 ${1, 2, 3, 4, 5}$ 、辺集合 ${12, 13, 23, 34, 35, 45}$
$G_{4}$ ：頂点集合 ${1, 2, 3, 4, 5, 6}$ 、辺集合 ${12, 13, 24, 34, 35, 46, 56}$
$G_{5}$ ：頂点集合 ${1, 2, 3, 4, 5, 6, 7}$ 、辺集合 ${12, 14, 23, 34, 45, 56, 67, 72}$

ただし、辺 $ij$ は頂点 $i$ と頂点 $j$ を結ぶ辺を表す。

この問題で使うもの

ハミルトン閉路の有無（説明と入口の問題）

この問題を解けるようになるまで（8 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「ハミルトン閉路の有無」の技能を使う。ありそうなグラフは閉路を具体的に書き、なさそうなグラフは 2 部グラフの部集合の大きさか、頂点を除いたときの連結成分の数で否定する。

ヒント 2

2 部グラフのハミルトン閉路では 2 つの部集合の頂点が交互に現れるので、部集合の大きさが等しくないといけない。また、1 頂点を除いてグラフが 2 つ以上に分かれるなら、ハミルトン閉路はない。

ヒント 3

$G_{1}$ は部集合の大きさが $2 \neq = 3$ なので閉路なし。 $G_{3}$ は頂点 $3$ を除くと ${1, 2}$ と ${4, 5}$ に分かれる。 $G_{5}$ を 2 色に塗り分けて部集合の大きさを調べ、 $G_{2}$ , $G_{4}$ については閉路を実際に探してみよう。

答えと解説

答えを見る

{2, 4}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

ハミルトン閉路があることは閉路を $1$ つ具体的に書いて示し、ないことは「2 部グラフの部集合の大きさ」または「頂点を除いたときの連結成分の数」で示す。

$G_{1} = K_{2, 3}$ ：部集合の大きさは $2$ と $3$ である。ハミルトン閉路があるとすると、2 部グラフの辺は必ず異なる部集合の頂点を結ぶので、閉路をたどると $2$ つの部集合の頂点が交互に現れる。閉路では最後に出発点へ戻るので、両方の部集合の頂点数は等しくなければならない。 $2 \neq = 3$ なので、 $G_{1}$ はハミルトン閉路をもたない。

$G_{2} = K_{3, 3}$ ：部集合を ${u_{1}, u_{2}, u_{3}}$ , ${w_{1}, w_{2}, w_{3}}$ とすると、異なる部集合の頂点どうしはすべて辺で結ばれているから
$u_{1} \to w_{1} \to u_{2} \to w_{2} \to u_{3} \to w_{3} \to u_{1}$
はハミルトン閉路である。よって $G_{2}$ はハミルトン閉路をもつ。

$G_{3}$ ：頂点 $3$ を除くと、残りの辺は $12$ , $45$ だけになり、グラフは ${1, 2}$ と ${4, 5}$ の $2$ つの連結成分に分かれる。もしハミルトン閉路があれば、そこから頂点 $3$ を除いたものは残りの $4$ 頂点すべてを通る $1$ 本の道になるので、残りのグラフは連結のはずである。これは連結成分が $2$ つあることに矛盾する。よって $G_{3}$ はハミルトン閉路をもたない。

$G_{4}$ ：
$1 \to 2 \to 4 \to 6 \to 5 \to 3 \to 1$
を考えると、使う辺は $12, 24, 46, 65, 53, 31$ で、すべて辺集合に含まれ、 $6$ 頂点をちょうど $1$ 回ずつ通っている。よって $G_{4}$ はハミルトン閉路をもつ。

$G_{5}$ ：頂点を 2 色に塗り分ける。頂点 $1$ を A とすると、隣接する $2, 4$ は B、 $2$ に隣接する $3, 7$ は A、 $4$ に隣接する $5$ は A、 $5$ に隣接する $6$ は B となる。すべての辺 $12, 14, 23, 34, 45, 56, 67, 72$ について両端の色が異なることが確かめられるので、 $G_{5}$ は部集合 ${1, 3, 5, 7}$ （ $4$ 個）と ${2, 4, 6}$ （ $3$ 個）をもつ 2 部グラフである。 $G_{1}$ と同じ理由で、部集合の大きさが異なる 2 部グラフはハミルトン閉路をもたない。

以上より、ハミルトン閉路をもつのは $G_{2}, G_{4}$ であり、答えは ${2, 4}$ である。

別解

各グラフについて調べる。

$G_{1} = K_{2, 3}$ ：2部グラフでハミルトン閉路は両側の頂点数が等しいことが必要。2≠3 なので閉路をもたない。

$G_{2} = K_{3, 3}$ ：頂点を A={a1,a2,a3}, B={b1,b2,b3} とすると、a1-b1-a2-b2-a3-b3-a1 がハミルトン閉路。よりもつ。

$G_{3}$ ：頂点 3 は 1,2,4,5 と隣接し、辺は 12,13,23,34,35,45。頂点 1 の次数は 2（隣接 2,3）、頂点 2 の次数は 2（隣接 1,3）、頂点 4 の次数は 2（隣接 3,5）、頂点 5 の次数は 2（隣接 3,4）。ハミルトン閉路では次数 2 の頂点の辺はすべて使うので、辺 12,13,23 がすべて使われ、三角形 1-2-3 が閉路になってしまい、5 頂点すべてを通れない。また頂点 3 は切断点（3 を除くと {1,2} と {4,5} に分かれる）なので、ハミルトン閉路をもたない。

$G_{4}$ ：辺 12,13,24,34,35,46,56。次数は 1:2(2,3), 2:2(1,4), 3:3(1,4,5), 4:3(2,3,6), 5:2(3,6), 6:2(4,5)。次数 2 の頂点の辺をすべて使う：12,13（頂点1）、12,24（頂点2）、35,56（頂点5）、46,56（頂点6）。使う辺は 13,12,24,35,56,46 の 6 本。これで閉路 3-1-2-4-6-5-3 となり、6 頂点すべてを通る。辺 34 は不要。よりもつ。

$G_{5}$ ：辺 12,14,23,34,45,56,67,72。次数は 5:2(4,6), 6:2(5,7), 7:2(6,2), 3:2(2,4)。頂点 5,6,7 の辺より 45,56,67,72 を使い、頂点 3 の辺より 23,34 を使う。すると頂点 2 は 72,23 の 2 本、頂点 4 は 45,34 の 2 本で、閉路 2-3-4-5-6-7-2 が成立し、頂点 1 が通れない。頂点 1 の次数は 2（2,4）なので 12,14 も使う必要があるが、頂点 2 の次数が 3 以上になり矛盾。よってもたない。

検算：G4 の閉路の辺 31,12,24,46,65,53 はすべて辺集合に含まれる。G2 の閉路も確認済み。

答え：{2, 4}

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる