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

グラフ理論の問題

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

頂点集合 $V = {u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, w_{1}, w_{2}, w_{3}, w_{4}, w_{5}}$ と、次の $9$ 本の辺からなる辺集合 $E$ をもつ単純無向グラフ $G = (V, E)$ を考える。
$u_{1} w_{1}, u_{1} w_{2}, u_{2} w_{1}, u_{3} w_{1}, u_{3} w_{3}, u_{4} w_{2}, u_{4} w_{4}, u_{4} w_{5}, u_{5} w_{2}$
$G$ の独立数 $α (G)$ （互いに隣接しない頂点からなる集合の要素の個数の最大値）を求めよ。

この問題で使うもの

最大マッチングとケーニヒの定理（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

最大マッチングとケーニヒの定理を使います。 $G$ が 2 部グラフであることを確かめ、増加道を探して最大マッチングの大きさ $ν (G)$ を求めましょう。

ヒント 2

2 部グラフでは $τ (G) = ν (G)$ （ケーニヒの定理）が成り立ちます。さらに $α (G) + τ (G) = ∣ V ∣$ を使います。

ヒント 3

マッチング ${u_{1} w_{1}, u_{3} w_{3}, u_{4} w_{2}}$ から、増加道 $u_{2} - w_{1} - u_{1} - w_{2} - u_{4} - w_{4}$ で入れかえると大きさ $4$ のマッチングが得られます。頂点被覆 ${w_{1}, w_{2}, u_{3}, u_{4}}$ を使うと、これ以上大きくできないことがわかります。

答えと解説

答えを見る

6

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

解説を読む

手順 1：2 部グラフであることの確認

どの辺も $U = {u_{1}, \dots, u_{5}}$ の頂点と $W = {w_{1}, \dots, w_{5}}$ の頂点を結んでいる。したがって $G$ は $U, W$ を 2 つの部分とする 2 部グラフである。

手順 2：増加道を使って最大マッチングを求める

まず、適当に辺を選んでマッチング $M = {u_{1} w_{1}, u_{3} w_{3}, u_{4} w_{2}}$ （大きさ $3$ ）をつくる。 $M$ に含まれない頂点（自由頂点）は $u_{2}, u_{5}, w_{4}, w_{5}$ である。

自由頂点 $u_{2}$ から出発し、「 $M$ に含まれない辺」と「 $M$ に含まれる辺」を交互にたどると、
$u_{2} - w_{1} - u_{1} - w_{2} - u_{4} - w_{4}$
という道が得られる。ここで $u_{2} w_{1}, u_{1} w_{2}, u_{4} w_{4}$ は $M$ に含まれず、 $w_{1} u_{1}, w_{2} u_{4}$ は $M$ に含まれる。両端 $u_{2}, w_{4}$ はともに自由頂点なので、これは増加道である。

この道の上で、 $M$ に含まれる辺と含まれない辺を入れかえると、
$M^{'} = {u_{2} w_{1}, u_{1} w_{2}, u_{4} w_{4}, u_{3} w_{3}}$
となり、大きさは $4$ に増える。したがって $ν (G) \geq 4$ である。

手順 3： $ν (G) = 4$ であることの確認

頂点の集合 $C = {w_{1}, w_{2}, u_{3}, u_{4}}$ を考える。各辺について調べると、
- $u_{1} w_{1}, u_{2} w_{1}$ は $w_{1}$ を含む
- $u_{1} w_{2}, u_{5} w_{2}$ は $w_{2}$ を含む
- $u_{3} w_{1}, u_{3} w_{3}$ は $u_{3}$ を含む
- $u_{4} w_{2}, u_{4} w_{4}, u_{4} w_{5}$ は $u_{4}$ を含む

となるので、 $C$ は頂点被覆である。マッチングの辺は互いに端点を共有しないから、頂点被覆の 1 つの頂点が覆えるのはマッチングの辺のうち高々 1 本である。よって、どのマッチングの大きさも $∣ C ∣ = 4$ 以下であり、 $ν (G) \leq 4$ となる。手順 2 と合わせて $ν (G) = 4$ である。

手順 4：ケーニヒの定理で $τ (G)$ を求める

$G$ は 2 部グラフなので、ケーニヒの定理より
$τ (G) = ν (G) = 4$
である。

手順 5：独立数を求める

$α (G) + τ (G) = ∣ V ∣$ と $∣ V ∣ = 10$ より、
$α (G) = 10 - 4 = 6$
である。実際、 $C$ の補集合 ${u_{1}, u_{2}, u_{5}, w_{3}, w_{4}, w_{5}}$ の頂点は互いに隣接しておらず、大きさ $6$ の独立集合になっている。

よって $α (G) = 6$ である。

別解

G は $U = {u_{1}, \dots, u_{5}}$ と $W = {w_{1}, \dots, w_{5}}$ の間にだけ辺がある二部グラフである。König の定理より、二部グラフでは $α (G) = ∣ V ∣ - ν (G)$ （ $ν$ は最大マッチングの大きさ）が成り立つ。

最大マッチングを求める。 $u_{2} w_{1}, u_{5} w_{2}, u_{3} w_{3}, u_{4} w_{4}$ は互いに頂点を共有しないので、大きさ $4$ のマッチングがある。

大きさ $5$ のマッチングは存在しない。 ${u_{1}, u_{2}, u_{5}}$ の隣接頂点は ${w_{1}, w_{2}}$ の $2$ 個で、集合の大きさ $3$ より小さい。Hall の条件が成り立たないので、 $U$ のすべての頂点を含むマッチングはない。よって $ν = 4$ である。

したがって $α (G) = 10 - 4 = 6$ 。

検算として、大きさ $6$ の独立集合 ${u_{1}, u_{2}, u_{5}, w_{3}, w_{4}, w_{5}}$ を挙げる。 $u_{1}, u_{2}, u_{5}$ の隣接頂点は $w_{1}, w_{2}$ だけである。また $W$ 内、 $U$ 内には辺がない。よってこれは独立集合になる。上界 $6$ とも一致する。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題