Day 117-Q2 — König's theorem（最小頂点被覆と最大マッチング）

2026-08-09 赤色 Master / Phase 8+ ★★★★★★★★★ 二部グラフ・最大マッチング・最小頂点被覆の構成

問題

左側頂点 $L_1,\dots,L_N$、右側頂点 $R_1,\dots,R_M$ からなる二部グラフが与えられる。辺は $E$ 本あり、$i$番目の辺は $L_{a_i}$ と $R_{b_i}$ を結ぶ。

全ての辺について、両端点の少なくとも一方が含まれるように頂点の部分集合（頂点被覆）を選びたい。頂点被覆に含める頂点数の最小値を求めよ。

入力形式

N M E
a_1 b_1
a_2 b_2
:
a_E b_E

制約

$1 \le N, M \le 500$
$0 \le E \le N \times M$
$1 \le a_i \le N,\ 1 \le b_i \le M$

入出力例

入力例1

5 4 7
1 1
2 1
2 2
3 2
3 3
4 3
5 4

出力例1

4

入力例2

2 2 2
1 1
2 2

出力例2

2

概念図: 交互路DFSによる最小頂点被覆の構成（入力例1）

L4 と L5 は未マッチ側→ L4 から交互路探索、L5 は独立成分 L1 L2 L3 L4 L5 R1 R2 R3 R4 緑塗り = L1,L2,L3,L5（被覆から除外）　黄 = L4（被覆に含む）　赤枠 = R1,R2,R3（被覆に含む）　灰 = R4（除外）

交互路DFSはL4から始まり点線（非マッチング辺）でR3へ、実線（マッチング辺）でL3へ戻り…と伝播し、最終的にL1,L2,L3とR1,R2,R3が到達集合Zに入る。最小頂点被覆は「Zに含まれない左頂点(=L5)」∪「Zに含まれる右頂点(=R1,R2,R3)」= サイズ4。

ヒント（段階的開示）

ヒント1: 方向性
二部グラフにおいては「最大マッチングのサイズ」と「最小頂点被覆のサイズ」が必ず一致するという König's theorem（ケーニッヒの定理） が成り立つ。まずは最大マッチングを求めれば、答えの数自体はすぐに分かる。問題はその先で、実際にどの頂点を選べば最小頂点被覆になるかを構成する部分にある。
ヒント2: アプローチ
最大マッチング $M$ を1つ固定し、左側のマッチされていない頂点全てを始点として、「マッチしていない辺で右へ・マッチしている辺で左へ」を交互にたどれる頂点集合 $Z$ を求める（交互路DFS/BFS）。このとき最小頂点被覆は $(L \setminus Z) \cup (R \cap Z)$ で与えられる。
ヒント3: 誘導（コード骨格） 
# 1. Kuhn法（増加路DFS）で最大マッチングを求める
# 2. マッチされていない左頂点 v それぞれから
#    「非マッチング辺で右へ」「マッチング辺で右→左へ戻る」を繰り返し到達可能な頂点集合 Z を求める
# 3. 答え = (Zに含まれない左頂点の数) + (Zに含まれる右頂点の数)
#    これが最大マッチングのサイズと一致することを確認せよ（Königの定理）

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    e = int(data[idx]); idx += 1

    adj = [[] for _ in range(n + 1)]
    for _ in range(e):
        a = int(data[idx]); b = int(data[idx + 1]); idx += 2
        adj[a].append(b)

    match_r = [0] * (m + 1)  # match_r[b] = a （Rのbに対応するLの頂点、0なら未マッチ）
    match_l = [0] * (n + 1)

    def try_kuhn(v, visited):
        for to in adj[v]:
            if not visited[to]:
                visited[to] = True
                if match_r[to] == 0 or try_kuhn(match_r[to], visited):
                    match_r[to] = v
                    match_l[v] = to
                    return True
        return False

    matching = 0
    for v in range(1, n + 1):
        visited = [False] * (m + 1)
        if try_kuhn(v, visited):
            matching += 1

    # König's theorem: 未マッチの左頂点から交互路で到達可能な集合 Z を求める
    visited_l = [False] * (n + 1)
    visited_r = [False] * (m + 1)

    def alt_dfs(v):
        visited_l[v] = True
        for to in adj[v]:
            if not visited_r[to]:
                visited_r[to] = True
                if match_r[to] != 0:
                    alt_dfs(match_r[to])

    for v in range(1, n + 1):
        if match_l[v] == 0:
            alt_dfs(v)

    cover_size = sum(1 for v in range(1, n + 1) if not visited_l[v])
    cover_size += sum(1 for v in range(1, m + 1) if visited_r[v])

    print(cover_size)


solve()
計算量: Kuhn法は $O(N \cdot E)$（$N,M\le500$ 程度なら十分高速。より大規模なら Hopcroft-Karp 法で $O(E\sqrt{N})$ に改善できる）。入力例1で実際に最大マッチング4、頂点被覆 $\{L_5, R_1, R_2, R_3\}$（サイズ4、全辺を被覆することを確認済み）が得られることを検証済み。

Step-by-Step 解説

1最大マッチングを求める
標準的なKuhn法（増加路探索）で左頂点を1つずつマッチさせていく。入力例1では $L_1\text{-}R_1,\ L_2\text{-}R_2,\ L_3\text{-}R_3,\ L_5\text{-}R_4$ のようなマッチングが得られ（$L_4$は未マッチ）、サイズは4になる。
2なぜKönigの定理が成り立つのか
任意のグラフで $\tau \ge \nu$（頂点被覆はマッチングの各辺ごとに少なくとも1頂点必要）が成り立つ。二部グラフに限っては逆向きの $\tau \le \nu$ も成り立つため $\tau=\nu$ となる。
3交互路で被覆を構成する
未マッチの左頂点から出発し、非マッチング辺で右へ、マッチング辺で左に戻る交互路をたどって到達可能な集合 $Z$ を作る。$(L\setminus Z)\cup(R\cap Z)$ が最小頂点被覆になる。
4サイズの一致を確認
cover_size は必ず最大マッチングのサイズと一致する。実装時にこの一致をassertしておくとバグに気づきやすい。
5計算量の確認
$N,M\le500$ 程度なら Kuhn法の $O(NE)$ でも余裕を持って動作する。

よくあるミス

ミス原因正しい書き方
交互路DFSを「全ての左頂点」から始めてしまうKönigの定理の構成が「未マッチ頂点から」であることを見落とす交互路DFSは未マッチの左頂点のみを始点にする
被覆に $Z\cap L$ と $Z\cap R$ を両方入れてしまう定理の式の左右非対称性を誤解する左側は「$Z$に含まれない」頂点、右側は「$Z$に含まれる」頂点を選ぶ
マッチングが複数存在することに戸惑う被覆の具体的な集合は求め方に依存するがサイズは不変ということを理解していないどのような最大マッチングから構成しても被覆のサイズは必ず一致する
一般グラフにも同じ構成が使えると誤解するKönigの定理が二部グラフ限定であることを忘れる一般グラフでは $\tau > \nu$ になりうる（例: 奇閉路）

次のステップ

  • 発展: 同じグラフの最大独立集合（$N+M-$最大マッチング）を実際に構成してみる
  • 次回予告: 複数文字列の最長共通部分文字列（Generalized Suffix Array）

自己評価

自分の回答

気づき・メモ