Day 115-Q2 | 一般グラフの最大マッチング（Blossom Algorithm）

問題

$N$ 頂点 $M$ 辺の無向単純グラフが与えられる（二部グラフとは限らない）。マッチング（どの2辺も頂点を共有しない辺の集合）の最大サイズを求め、その一例を出力せよ。

入力形式

N M
u_1 v_1
u_2 v_2
...
u_M v_M

制約

$2 \le N \le 200$

$0 \le M \le N(N-1)/2$

$1 \le u_i,v_i \le N$, $u_i \ne v_i$

多重辺なし

入出力例

入力例1

出力例1

2
1 2
3 4

頂点1,2,3は三角形をなし、頂点4は3にのみ接続する。三角形の内部の辺だけではマッチングを2本取れないため、1-2と3-4を選ぶのが唯一の最大マッチング。

概念図: 奇閉路（ブロッサム）の縮約

ヒント（段階的開示）

ヒント1: 方向性

二部グラフなら通常の増加路探索（DFS/BFSベースの最大マッチングやHopcroft-Karp法）で解けるが、一般グラフでは奇閉路が邪魔をして単純な増加路探索が失敗することがある。奇数長の閉路上でマッチング辺と非マッチング辺が交互に並ぶ経路を辿ると、探索が閉路の中をぐるぐる回ってしまい正しい増加路を見失う。この現象がなぜ起きるか、小さい奇閉路（例えば5頂点の閉路）で考えてみる。

ヒント2: アプローチ

探索中に奇閉路（花、blossom）を検出したら、その閉路全体を1つの頂点に「縮約」して考えると、縮約後のグラフで見つけた増加路は元のグラフの増加路に対応させることができる。実装では実際にグラフの形を変えるのではなく、各頂点が「今どの縮約頂点（base）に属しているか」を管理するbase[]配列を使うのが一般的。交互木をBFSで広げながら、非マッチング辺で既に訪問済みの頂点にぶつかったときにその2頂点の最近共通祖先（LCA）を求め、そこまでの経路上の頂点すべてを同じbaseにまとめる。

ヒント3: 誘導（コード骨格）

def find_path(root):
    # base[], p[] を初期化してBFS
    # v -> to の辺を見て:
    #   同じbaseに属する、またはマッチング辺なら無視
    #   to == root か、to が既にマッチ済みで p[match[to]] が設定済みなら奇閉路検出
    #     -> curbase = lca(v, to); mark_path で経路上の頂点を curbase に統合
    #   to が未訪問(p[to]==0)なら:
    #     p[to] = v
    #     match[to]==0 なら to を返す（増加路発見）
    #     そうでなければ match[to] を訪問済みにしてキューへ

模範解答 (Python)

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx + 1]); idx += 2
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = int(data[idx]), int(data[idx + 1]); idx += 2
        graph[u].append(v)
        graph[v].append(u)

    match = [0] * (N + 1)
    p = [0] * (N + 1)
    base = [0] * (N + 1)
    used = [False] * (N + 1)
    blossom = [False] * (N + 1)

    def lca(a, b):
        used2 = [False] * (N + 1)
        x = a
        while True:
            x = base[x]
            used2[x] = True
            if match[x] == 0:
                break
            x = p[match[x]]
        y = b
        while True:
            y = base[y]
            if used2[y]:
                return y
            y = p[match[y]]

    def mark_path(v, b, child):
        while base[v] != b:
            blossom[base[v]] = True
            blossom[base[match[v]]] = True
            p[v] = child
            child = match[v]
            v = p[match[v]]

    def find_path(root):
        nonlocal used, p, base
        used = [False] * (N + 1)
        p = [0] * (N + 1)
        for i in range(1, N + 1):
            base[i] = i
        used[root] = True
        q = deque([root])
        while q:
            v = q.popleft()
            for to in graph[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != 0 and p[match[to]] != 0):
                    curbase = lca(v, to)
                    for i in range(1, N + 1):
                        blossom[i] = False
                    mark_path(v, curbase, to)
                    mark_path(to, curbase, v)
                    for i in range(1, N + 1):
                        if blossom[base[i]]:
                            base[i] = curbase
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif p[to] == 0:
                    p[to] = v
                    if match[to] == 0:
                        return to
                    else:
                        used[match[to]] = True
                        q.append(match[to])
        return 0

    result = 0
    for v in range(1, N + 1):
        if match[v] == 0:
            u = find_path(v)
            if u:
                result += 1
                while u:
                    pv = p[u]
                    ppv = match[pv]
                    match[u] = pv
                    match[pv] = u
                    u = ppv

    print(result)
    pairs = []
    seen = [False] * (N + 1)
    for i in range(1, N + 1):
        if match[i] and not seen[i]:
            seen[i] = seen[match[i]] = True
            pairs.append((min(i, match[i]), max(i, match[i])))
    pairs.sort()
    for a, b in pairs:
        print(a, b)

main()

計算量: 1回のfind_pathが $O(V^2)$、これを最大 $V$ 回行うので全体 $O(V^3)$。$N \le 200$程度が現実的なPythonでの実行上限の目安。ランダムグラフ・完全グラフ・複数の奇閉路を含むグラフで総当たり（bitDP）による最大マッチングと一致することを確認済み。

Step-by-Step 解説

1交互木のBFS探索とp[]（親）配列
未マッチ頂点rootから交互木（マッチング辺・非マッチング辺が交互に並ぶ木）をBFSで広げる。p[v]は交互木上でのvの親。

2lca(v, w) — 縮約後のbaseを辿って最近共通祖先を求める
v側はbase[x]→p[match[x]]を辿って根まで進みながら訪問済み集合に記録し、w側も同様に辿って初めて訪問済みに入っている頂点が最近共通祖先。

3mark_path — 花に含まれる頂点をマークしbase[]を更新する
LCAからv, wそれぞれへの経路上の頂点をblossom[]にマークし、まとめてbase[i]をcurbaseに張り替える。

4増加路が見つかったらmatch[]を反転する
find_pathが未マッチ頂点uを返したら、p[]を逆順に辿りながらmatch[u]=p[u]、match[p[u]]=uを交互に設定し増加路全体のマッチング状態を反転する。

5全頂点について探索を繰り返す
まだマッチしていない頂点それぞれについてfind_pathを呼び、増加路が見つかるたびにマッチング数を1増やす。

よくあるミス

ミス	原因	正しい書き方
二部グラフ用のアルゴリズムをそのまま一般グラフに適用してしまう	奇閉路の存在を考慮していない	ブロッサムを検出したら`base[]`を更新して縮約してから探索を続ける
ブロッサム内の頂点をキューに入れる際に`used`を確認しない	「baseが変わったら全部入れ直す」と誤解	`blossom[base[i]]`が真の頂点のうち、まだ`used[i]`が偽のものだけをキューに追加する
増加路発見後、`match[]`更新の向きを逆にしてしまう	`p[]`と`match[]`の関係を混同	未マッチ点`u`から`p[u]`, `match[p[u]]`の順に辿り、`match[u]=p[u]`と`match[p[u]]=u`を対で設定する
$O(V^3)$の計算量を見落とし大きすぎる$N$で実行してしまう	増加路探索1回が$O(V^2)$、それを最大$V$回行うため	Pythonでの実行を考えると$N \le 200$程度を目安にする

次のステップ

発展: 重み付き一般マッチング（Weighted Blossom Algorithm）に拡張してみる
発展: 二部グラフに限定した場合にHopcroft-Karp法へ切り替え、実行時間を比較する
発展: 完全マッチングが存在するための必要十分条件（Tutteの定理）を調べ、今回の問題の判定に応用してみる

自己評価

完全理解おおむね理解要復習

Day 115-Q2 — 一般グラフの最大マッチング（Blossom Algorithm / Edmondsの花アルゴリズム）

問題