Day 148-Q3 | Dulmage-Mendelsohn分解

問題

左側$X=\{0,\dots,p-1\}$、右側$Y=\{0,\dots,q-1\}$の二部グラフが与えられる。最大マッチング$M$を1つ求め、次の手順で各頂点を分類せよ。

$X$側の未マッチ頂点から「非マッチング辺→マッチング辺」を交互に辿って到達可能な集合$Z$を求める。
$Y$側の未マッチ頂点から対称に到達可能な集合$W$を求める。
$v\in Z$なら`H`、$v\notin Z$かつ$v\in W$なら`V`、どちらでもなければ`C`とする。

$X$の分類文字列、$Y$の分類文字列、最大マッチングのサイズを出力せよ（この分類はマッチングの選び方に依存しない一意な値になることがDM定理で保証されている）。

入力形式

p q m
x_1 y_1
:
x_m y_m

制約

$1 \le p, q \le 10$

$0 \le m \le 30$

入出力例

入力例1

出力例1

3
CHHV
CHVV

入力例2

出力例2

3
CCC
CCC

概念図：3つの成分（入力例1）

ヒント（段階的開示）

ヒント1（方向性）

Königの定理の証明で使う「未マッチ頂点からの交互到達可能集合」を思い出す。今回は両方向（$X$側の未マッチから、$Y$側の未マッチから）で計算し、重なり方でグラフを3領域に切り分ける。

ヒント2（アプローチ）

最大マッチングであれば$Z$の中に$Y$側の未マッチ頂点は含まれず、$W$の中に$X$側の未マッチ頂点は含まれない。さらに$Z\cap W=\emptyset$も最大性から従う。

ヒント3（誘導）

from collections import deque

def reach_from_free_X(p, q, adj, matchX, matchY):
    visitedX = [False]*p
    visitedY = [False]*q
    dq = deque()
    for x in range(p):
        if matchX[x] == -1:
            visitedX[x] = True
            dq.append(('X', x))
    while dq:
        side, u = dq.popleft()
        if side == 'X':
            for y in adj[u]:
                if not visitedY[y]:
                    visitedY[y] = True
                    dq.append(('Y', y))
        else:
            x2 = matchY[u]
            if x2 != -1 and not visitedX[x2]:
                visitedX[x2] = True
                dq.append(('X', x2))
    return visitedX, visitedY

模範解答 (Python)

import sys
from collections import deque

def max_matching(p, q, adj):
    matchX = [-1]*p
    matchY = [-1]*q

    def try_kuhn(x, visited):
        for y in adj[x]:
            if not visited[y]:
                visited[y] = True
                if matchY[y] == -1 or try_kuhn(matchY[y], visited):
                    matchX[x] = y
                    matchY[y] = x
                    return True
        return False

    for x in range(p):
        visited = [False]*q
        try_kuhn(x, visited)
    return matchX, matchY


def dm_decompose(p, q, edges):
    adj = [[] for _ in range(p)]
    radj = [[] for _ in range(q)]
    for x, y in edges:
        adj[x].append(y)
        radj[y].append(x)

    matchX, matchY = max_matching(p, q, adj)

    def reach_from_free_X():
        visitedX = [False]*p
        visitedY = [False]*q
        dq = deque()
        for x in range(p):
            if matchX[x] == -1:
                visitedX[x] = True
                dq.append(('X', x))
        while dq:
            side, u = dq.popleft()
            if side == 'X':
                for y in adj[u]:
                    if not visitedY[y]:
                        visitedY[y] = True
                        dq.append(('Y', y))
            else:
                x2 = matchY[u]
                if x2 != -1 and not visitedX[x2]:
                    visitedX[x2] = True
                    dq.append(('X', x2))
        return visitedX, visitedY

    def reach_from_free_Y():
        visitedX = [False]*p
        visitedY = [False]*q
        dq = deque()
        for y in range(q):
            if matchY[y] == -1:
                visitedY[y] = True
                dq.append(('Y', y))
        while dq:
            side, u = dq.popleft()
            if side == 'Y':
                for x in radj[u]:
                    if not visitedX[x]:
                        visitedX[x] = True
                        dq.append(('X', x))
            else:
                y2 = matchX[u]
                if y2 != -1 and not visitedY[y2]:
                    visitedY[y2] = True
                    dq.append(('Y', y2))
        return visitedX, visitedY

    zx, zy = reach_from_free_X()
    wx, wy = reach_from_free_Y()

    catX = ''.join('H' if zx[x] else ('V' if wx[x] else 'C') for x in range(p))
    catY = ''.join('H' if zy[y] else ('V' if wy[y] else 'C') for y in range(q))

    size = sum(1 for x in matchX if x != -1)
    return size, catX, catY


def main():
    data = sys.stdin.read().split()
    idx = 0
    p, q, m = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
    edges = []
    for _ in range(m):
        x, y = int(data[idx]), int(data[idx+1]); idx += 2
        edges.append((x, y))
    size, catX, catY = dm_decompose(p, q, edges)
    print(size)
    print(catX)
    print(catY)


main()

Step-by-Step 解説

1最大マッチングを求める
通常のKuhn法で最大マッチングを1つ求める。DM定理によりどのマッチングを選んでも分類結果は変わらない。

22方向の交互到達可能性
$X$側からの$Z$はKönigの証明と同じ計算。$Y$側からの$W$を対称に計算する。

3分類ルールの意味
`H`はある最大マッチングでは未マッチになりうる不足側、`V`は逆に過剰側、`C`は常に完全マッチされる安定した核。

4$Z\cap W=\emptyset$の理由
重なると未マッチX頂点から未マッチY頂点への増加路が構成でき最大性に矛盾するため、交わらないことが保証される。

よくあるミス

ミス	原因	正しい書き方
`H`と`V`の判定順序を逆にする	理論上重ならないはずが実装ミスで重なった場合に結果が変わる	「まず$Z$なら`H`、そうでなく$W$なら`V`」の順で判定する
交互到達のBFSでマッチング辺/非マッチング辺の使い分けを逆にする	$X\to Y$は非マッチング、$Y\to X$はマッチングという交互性を忘れる	`adj`全体と`matchY`のみを使い分けて実装する
マッチングを変えると結果も変わると誤解する	分解結果がマッチング非依存であることを知らない	別の増加路順序で実行しても`H/V/C`が変わらないことを確認する
孤立成分を`H`/`V`に誤分類	連結成分をまたいだ到達可能性と混同	BFSは連結成分ごとに独立に伝播することを確認する
出力文字列の順序が頂点番号順でない	訪問順とインデックス順を混同	`for x in range(p)`のように番号順に組み立てる

次のステップ

発展: 核（`C`）部分を強連結成分分解し、疎行列のブロック三角化まで求めよ。
次回予告: Pollard's p-1法（整数の素因数分解・$p-1$が滑らかな数のときに有効な決定的手法）

自己評価

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

Day 148-Q3 — Dulmage-Mendelsohn分解（二部グラフの最大マッチング構造分解）

問題