この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

グラフ理論の問題

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

次の 4 つの単純無向グラフ $G_{1}, G_{2}, G_{3}, G_{4}$ を考える。

$G_{1}$ ：完全 2 部グラフ $K_{3, 3}$
$G_{2}$ ：完全 2 部グラフ $K_{2, 3}$
$G_{3}$ ：頂点集合 ${1, 2, 3, 4, 5}$ 、辺集合 ${12, 13, 23, 34, 35, 45}$
$G_{4}$ ：頂点集合 ${1, 2, 3, 4, 5, 6}$ 、辺集合 ${14, 13, 25, 26, 36, 45, 23}$

ここで辺 $ij$ は頂点 $i$ と頂点 $j$ を結ぶ辺を表す。ハミルトン閉路（すべての頂点をちょうど 1 回ずつ通って出発点に戻る閉路）をもつグラフ $G_{i}$ の番号 $i$ の集合を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

技能「ハミルトン閉路の有無」を使う。あると思うグラフは閉路を実際に作り、ないと思うグラフは 2 部グラフの部集合の大きさや、頂点を除いたときの連結成分の数で理由をつける。

ヒント 2

2 部グラフのハミルトン閉路は 2 つの部集合を交互に通るので、部集合の大きさが等しくなければならない。また、ハミルトン閉路があるグラフでは、1 個の頂点を除いても連結のままである。

ヒント 3

$K_{3, 3}$ は $a_{1} b_{1} a_{2} b_{2} a_{3} b_{3} a_{1}$ という閉路をもつ。 $K_{2, 3}$ は部集合の大きさが異なる。 $G_{3}$ は頂点 $3$ を除くと 2 つに分かれる。残る $G_{4}$ は、次数 2 の頂点 $4$ は必ず辺 $14$ と $45$ を使うことに注目して閉路をたどってみよう。

答えと解説

答えを見る

{1, 4}

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

解説を読む

各グラフについて、ハミルトン閉路を実際に作って「ある」ことを示すか、作れない理由を示して「ない」ことを示す。

$G_{1} = K_{3, 3}$ ：部集合を ${a_{1}, a_{2}, a_{3}}$ , ${b_{1}, b_{2}, b_{3}}$ とする。完全 2 部グラフなので $a_{i}$ と $b_{j}$ はすべて隣接している。よって
$a_{1} \to b_{1} \to a_{2} \to b_{2} \to a_{3} \to b_{3} \to a_{1}$
はすべての頂点をちょうど 1 回ずつ通る閉路であり、ハミルトン閉路をもつ。

$G_{2} = K_{2, 3}$ ：2 部グラフの辺は必ず異なる部集合の頂点を結ぶので、閉路は 2 つの部集合の頂点を交互に通る。したがってハミルトン閉路があれば、2 つの部集合の頂点数は等しくなければならない。しかし部集合の大きさは $2$ と $3$ で異なる（あるいは、ハミルトン閉路の長さは $5$ で奇数だが、2 部グラフは奇数長の閉路をもたない）。よってハミルトン閉路をもたない。

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

$G_{4}$ ：辺 $14, 45, 52, 26, 63, 31$ がすべて辺集合に含まれることを確かめると、
$1 \to 4 \to 5 \to 2 \to 6 \to 3 \to 1$
は 6 個の頂点をちょうど 1 回ずつ通る閉路である。よってハミルトン閉路をもつ。

以上より、求める集合は ${1, 4}$ である。

別解

$G_{1} = K_{3, 3}$ ：両側が 3 頂点ずつなので、 $a_{1} b_{1} a_{2} b_{2} a_{3} b_{3} a_{1}$ とたどれる。これはハミルトン閉路である。

$G_{2} = K_{2, 3}$ ：2 部グラフでハミルトン閉路があれば両側の頂点数は等しい。ところが 2≠3 なので、ハミルトン閉路はない。

$G_{3}$ ：三角形 123 と三角形 345 が頂点 3 だけを共有している。頂点 3 を除くとグラフが非連結になる（切断点）。ハミルトン閉路があれば 3 を除いても連結のままのはずなので、矛盾する。よってハミルトン閉路はない。

$G_{4}$ ：閉路 $1 \to 4 \to 5 \to 2 \to 6 \to 3 \to 1$ を考える。使う辺 14, 45, 52, 26, 63, 31 はすべて辺集合に含まれ、6 頂点をちょうど 1 回ずつ通る。よってハミルトン閉路がある。

以上より、答えは ${1, 4}$ 。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題