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

グラフ理論の問題

難易度 2教科書の演習問題レベル大学数学グラフ理論

頂点集合 $V = {u_{0}, u_{1}, u_{2}, u_{3}, u_{4}, w_{0}, w_{1}, w_{2}, w_{3}, w_{4}}$ と、次の $15$ 本の辺からなる単純無向グラフ $G$ を考える（五角柱グラフ）。ただし添字は $5$ を法として考える（ $u_{5} = u_{0}$ , $w_{5} = w_{0}$ ）。
$u_{i} u_{i + 1} (i = 0, 1, 2, 3, 4), w_{i} w_{i + 1} (i = 0, 1, 2, 3, 4), u_{i} w_{i} (i = 0, 1, 2, 3, 4)$
頂点の部分集合 $C \subseteq V$ が $G$ の頂点被覆であるとは、 $G$ のどの辺も少なくとも一方の端点が $C$ に属することをいう。 $G$ の頂点被覆に含まれる頂点の個数の最小値を求めよ。

この問題で使うもの

最大独立集合と最小頂点被覆（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

頂点被覆の大きさの下界を、グラフに含まれる部分グラフから考えましょう。

ヒント 2

$u_{0}, \dots, u_{4}$ は長さ $5$ の閉路をなします。1 つの頂点はこの閉路の辺を $2$ 本しか覆えないことに注目しましょう。

ヒント 3

各 5 頂点の閉路を覆うには $3$ 個以上の頂点が必要なので、全体では $6$ 個以上必要です。あとは縦の辺 $u_{i} w_{i}$ もすべて覆うように $6$ 個を選べるか確かめましょう（補集合が独立集合になるように選ぶと考えやすいです）。

答えと解説

答えを見る

6

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

解説を読む

下界 $u_{0}, u_{1}, u_{2}, u_{3}, u_{4}$ とその間の $5$ 本の辺は長さ $5$ の閉路 $C_{5}$ をなす。 $C_{5}$ の $5$ 本の辺を覆うには、1 つの頂点が覆える閉路の辺は $2$ 本だけなので、 $2$ 個の頂点では高々 $4$ 本しか覆えず、少なくとも $3$ 個の頂点が必要である。 $w_{0}, \dots, w_{4}$ の閉路についても同じで、2 つの閉路は頂点を共有しないから、頂点被覆 $C$ は
$∣ C ∣ \geq 3 + 3 = 6$
を満たす。

$6$ 個で覆える例 $C = {u_{1}, u_{3}, u_{4}, w_{0}, w_{2}, w_{4}}$ とすると、
- $u$ 側の閉路の辺 $u_{0} u_{1}, u_{1} u_{2}$ は $u_{1}$ 、 $u_{2} u_{3}, u_{3} u_{4}$ は $u_{3}$ 、 $u_{4} u_{0}$ は $u_{4}$ で覆われる
- $w$ 側の閉路の辺 $w_{0} w_{1}, w_{4} w_{0}$ は $w_{0}$ または $w_{4}$ 、 $w_{1} w_{2}, w_{2} w_{3}$ は $w_{2}$ 、 $w_{3} w_{4}$ は $w_{4}$ で覆われる
- 縦の辺 $u_{0} w_{0}$ は $w_{0}$ 、 $u_{1} w_{1}$ は $u_{1}$ 、 $u_{2} w_{2}$ は $w_{2}$ 、 $u_{3} w_{3}$ は $u_{3}$ 、 $u_{4} w_{4}$ は $u_{4}$ で覆われる

ので、 $C$ は頂点被覆である。（補集合 ${u_{0}, u_{2}, w_{1}, w_{3}}$ はどの 2 頂点も隣接しない独立集合になっている。）

よって頂点被覆の頂点数の最小値は $6$ である。

別解

頂点被覆 $C$ の補集合 $V ∖ C$ は独立集合であり、逆も成り立つ。よって最小頂点被覆の大きさは $10 - α (G)$ （ $α$ は最大独立集合の大きさ）。

上界: 独立集合は、上の 5 サイクル $u_{0} u_{1} u_{2} u_{3} u_{4}$ から高々 2 個（奇サイクル $C_{5}$ の独立数は $⌊ 5/2 ⌋ = 2$ ）、下の 5 サイクルからも高々 2 個なので $α (G) \leq 4$ 。
構成: ${u_{0}, u_{2}, w_{1}, w_{3}}$ は独立集合。実際、 $u_{0}, u_{2}$ は $C_{5}$ 上で隣接せず、 $w_{1}, w_{3}$ も隣接せず、 $u_{i}$ に隣接する $w$ は $w_{i}$ のみで、 $w_{0}, w_{2}$ は含まれない。よって $α (G) = 4$ 。

したがって最小頂点被覆は $10 - 4 = 6$ 。
検算: 補集合 ${u_{1}, u_{3}, u_{4}, w_{0}, w_{2}, w_{4}}$ が全 15 辺を覆うか確認する。上の辺 $u_{0} u_{1}$ （ $u_{1}$ ）、 $u_{1} u_{2}$ （ $u_{1}$ ）、 $u_{2} u_{3}$ （ $u_{3}$ ）、 $u_{3} u_{4}$ （ $u_{3}$ ）、 $u_{4} u_{0}$ （ $u_{4}$ ）。下の辺 $w_{0} w_{1}$ （ $w_{0}$ ）、 $w_{1} w_{2}$ （ $w_{2}$ ）、 $w_{2} w_{3}$ （ $w_{2}$ ）、 $w_{3} w_{4}$ （ $w_{4}$ ）、 $w_{4} w_{0}$ （ $w_{0}$ ）。縦の辺 $u_{0} w_{0}$ （ $w_{0}$ ）、 $u_{1} w_{1}$ （ $u_{1}$ ）、 $u_{2} w_{2}$ （ $w_{2}$ ）、 $u_{3} w_{3}$ （ $u_{3}$ ）、 $u_{4} w_{4}$ （ $u_{4}$ ）。すべて覆われている。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題