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

グラフ理論の問題

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

頂点集合 $V = {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, q_{1}, q_{2}, q_{3}, q_{4}}$ （ $9$ 個の頂点）と、次の $9$ 本の辺からなる辺集合 $E$ をもつ単純無向グラフ $G = (V, E)$ を考える。
$p_{1} q_{1}, p_{1} q_{2}, p_{2} q_{1}, p_{3} q_{2}, p_{4} q_{1}, p_{4} q_{2}, p_{5} q_{2}, p_{5} q_{3}, p_{5} q_{4}$
$G$ は ${p_{1}, \dots, p_{5}}$ と ${q_{1}, \dots, q_{4}}$ を 2 つの部分とする 2 部グラフである。 $G$ の最大マッチングの大きさ $ν (G)$ を増加道を用いて求め、ケーニヒの定理を利用して、 $G$ の独立数 $α (G)$ （最大独立集合の頂点数）を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

最大マッチングを増加道で求め、2 部グラフに対するケーニヒの定理 $ν (G) = τ (G)$ と、関係式 $α (G) + τ (G) = ∣ V ∣$ を順に使います。

ヒント 2

マッチング ${p_{1} q_{1}, p_{5} q_{2}}$ から始めて、未飽和頂点 $p_{3}$ から出る交互道 $p_{3} - q_{2} - p_{5} - q_{3}$ を考えてみましょう。

ヒント 3

増加道で入れ替えると ${p_{1} q_{1}, p_{3} q_{2}, p_{5} q_{3}}$ が得られ、これ以上増加道はありません。頂点被覆 ${q_{1}, q_{2}, p_{5}}$ からも $ν (G) \leq 3$ がわかります。あとは $τ (G)$ と $∣ V ∣ = 9$ から $α (G)$ を計算します。

答えと解説

答えを見る

6

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

解説を読む

手順 1：マッチングを作り、増加道で大きくする。

まず適当にマッチング $M = {p_{1} q_{1}, p_{5} q_{2}}$ をとる。 $M$ に含まれない頂点（未飽和頂点） $p_{3}$ から、 $M$ に入らない辺と $M$ の辺を交互にたどると
$p_{3} - q_{2} - p_{5} - q_{3}$
となり、両端 $p_{3}, q_{3}$ はどちらも未飽和である。これは増加道なので、この道の上で「 $M$ に入る辺」と「入らない辺」を入れ替えると、 $p_{5} q_{2}$ を除いて $p_{3} q_{2}, p_{5} q_{3}$ を加えることになり、
$M^{'} = {p_{1} q_{1}, p_{3} q_{2}, p_{5} q_{3}}$
という大きさ $3$ のマッチングが得られる。

手順 2： $M^{'}$ が最大であることを確かめる。

$M^{'}$ について未飽和な頂点は $p_{2}, p_{4}, q_{4}$ である。
- $p_{2}$ から： $p_{2} - q_{1} - p_{1} - q_{2} - p_{3}$ と進むと、 $p_{3}$ の隣接頂点は $q_{2}$ だけで行き止まり。
- $p_{4}$ から： $p_{4} - q_{1} - p_{1} - q_{2} - p_{3}$ 、 $p_{4} - q_{2} - p_{3}$ など、どの交互道も $q_{1}, q_{2}$ を経由して $p_{1}, p_{3}$ で行き止まりになり、未飽和な $q$ 側の頂点 $q_{4}$ には到達しない。

よって増加道は存在せず、ベルジュの定理により $M^{'}$ は最大マッチングである。したがって $ν (G) = 3$ 。

（確認）頂点集合 $C = {q_{1}, q_{2}, p_{5}}$ は頂点被覆である。実際、 $p_{1} q_{1}, p_{2} q_{1}, p_{4} q_{1}$ は $q_{1}$ で、 $p_{1} q_{2}, p_{3} q_{2}, p_{4} q_{2}, p_{5} q_{2}$ は $q_{2}$ で、 $p_{5} q_{3}, p_{5} q_{4}$ は $p_{5}$ で覆われる。マッチングの各辺は異なる被覆頂点を必要とするので $ν (G) \leq ∣ C ∣ = 3$ となり、上の結果と一致する。

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

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

手順 4： $α (G) + τ (G) = ∣ V ∣$ を使う。

$α (G) = ∣ V ∣ - τ (G) = 9 - 3 = 6.$
実際、最小頂点被覆 ${q_{1}, q_{2}, p_{5}}$ の補集合 ${p_{1}, p_{2}, p_{3}, p_{4}, q_{3}, q_{4}}$ は、 $p_{1}, \dots, p_{4}$ が $q_{1}, q_{2}$ としか隣接せず、 $q_{3}, q_{4}$ が $p_{5}$ としか隣接しないので、確かに大きさ $6$ の独立集合である。

答え： $α (G) = 6$

別解

【最大マッチング】まず $M_{0} = {p_{1} q_{1}}$ から始める。
1. 非飽和の $p_{3}$ から出発し、 $p_{3} - q_{2}$ は $q_{2}$ が非飽和なので増加道になる。 $M_{1} = {p_{1} q_{1}, p_{3} q_{2}}$ とする。
2. 非飽和の $p_{2}$ から出発し、 $p_{2} - q_{1} - p_{1} - q_{2} - p_{3}$ と進むが行き止まり。別の始点として $p_{4}$ を考えても同様に増加道が見つからない。そこで $p_{5}$ から出発し、 $p_{5} - q_{3}$ は $q_{3}$ が非飽和なので増加道になる。 $M_{2} = {p_{1} q_{1}, p_{3} q_{2}, p_{5} q_{3}}$ とする（大きさ $3$ ）。
3. $M_{2}$ に対する非飽和頂点は $p_{2}, p_{4}, q_{4}$ である。 $p_{2}$ からは $q_{1}$ へ行き、 $q_{1}$ は $p_{1}$ とマッチしているので $p_{1}$ へ進む。 $p_{1}$ から $q_{2}$ へ行き、 $q_{2}$ は $p_{3}$ とマッチしているので $p_{3}$ へ進む。 $p_{3}$ の隣接頂点は $q_{2}$ だけなので行き止まり。 $p_{4}$ からは $q_{1}$ または $q_{2}$ に行き、同様に $p_{1}, p_{3}$ で行き止まり。 $q_{4}$ からは $p_{5}$ へ行き、 $p_{5}$ は $q_{3}$ とマッチしているので $q_{3}$ へ進むが、 $q_{3}$ の隣接頂点は $p_{5}$ だけなので行き止まり。よって非飽和頂点どうしを結ぶ増加道は存在しない。ベルジュの定理より $M_{2}$ は最大マッチングで、 $ν (G) = 3$ 。

（別の確認） $q_{3}, q_{4}$ の隣接頂点は $p_{5}$ のみなので、この 2 頂点を同時にマッチングできない。したがって $ν \leq 3$ であり、上の結果と一致する。

【ケーニヒの定理】2 部グラフでは最小点被覆数 $τ (G) = ν (G) = 3$ 。実際 ${q_{1}, q_{2}, p_{5}}$ は 9 本の辺すべてを被覆する。
- $p_{1} q_{1}, p_{2} q_{1}, p_{4} q_{1}$ は $q_{1}$ で被覆される。
- $p_{1} q_{2}, p_{3} q_{2}, p_{4} q_{2}, p_{5} q_{2}$ は $q_{2}$ で被覆される。
- $p_{5} q_{3}, p_{5} q_{4}$ は $p_{5}$ で被覆される。

独立集合の補集合は点被覆であるから、 $α (G) = ∣ V ∣ - τ (G) = 9 - 3 = 6$ 。

【検算】 ${p_{1}, p_{2}, p_{3}, p_{4}, q_{3}, q_{4}}$ は、 $q_{3}, q_{4}$ の隣接頂点が $p_{5}$ だけなので、この集合内に辺がなく独立集合である。大きさは $6$ で一致する。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題