Day 095-Q5 | Dilworthの定理（最小鎖分割・DAG最小パス被覆）

問題

$N$ 個の要素からなる半順序集合が、$M$ 本の有向辺（$u\to v$ は「$u

この半順序集合を、要素を共有しない鎖（chain）にすべて分割するとき、必要な鎖の最小個数を求めよ。Dilworthの定理より、この最小鎖数は「反鎖（antichain）」の最大サイズに一致する。本問では最小鎖数を、DAGの推移閉包から構成した二部グラフの最大マッチングを用いて求める（最小鎖数 $=N-$最大マッチング数）。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 300$

$0 \le M \le \frac{N(N-1)}{2}$

辺が定めるグラフはDAG（閉路なし）

入出力例

入力例1

出力例1

ダイヤモンド型($1<2<4$, $1<3<4$)。反鎖の最大サイズは{2,3}で2。鎖分割は{1,2,4}と{3}の2本。辺なし(N=3,M=0)の場合は3。

概念図

ヒント（段階的開示）

ヒント1: 方向性

半順序集合における「鎖」は、DAGの推移閉包上での「有向路（パス）」に対応する。つまり本問は「DAGの頂点をなるべく少ない本数のパスで覆い尽くす」という最小パス被覆問題に帰着できる。

ヒント2: アプローチ

まず与えられた辺の推移閉包（全頂点対の到達可能性）を求める（$N\le300$ならFloyd-Warshall流で$O(N^3)$）。次に「左側頂点$u$」と「右側頂点$v$」からなる二部グラフを作り、到達可能な$(u,v)$（$u\neq v$）に辺を張る。この二部グラフの最大マッチングを$M^*$とすると、最小鎖数は$N-M^*$になる。

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

reach = [[False]*n for _ in range(n)]
for u,v in edges: reach[u][v] = True
for k in range(n):
    rk = reach[k]
    for i in range(n):
        if reach[i][k]:
            ri = reach[i]
            for j in range(n):
                if rk[j]: ri[j] = True

adj = [[v for v in range(n) if v != u and reach[u][v]] for u in range(n)]
# adj上で二部マッチング(Kuhnのアルゴリズム)を行い、matching_sizeを得る
answer = n - matching_size

模範解答 (Python)

import sys


def main():
    sys.setrecursionlimit(10000)
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    reach = [[False] * n for _ in range(n)]
    for _ in range(m):
        a = int(data[idx]) - 1; idx += 1
        b = int(data[idx]) - 1; idx += 1
        reach[a][b] = True

    # 推移閉包 (Floyd-Warshall流)
    for k in range(n):
        rk = reach[k]
        for i in range(n):
            if reach[i][k]:
                ri = reach[i]
                for j in range(n):
                    if rk[j]:
                        ri[j] = True

    adj = [[v for v in range(n) if v != u and reach[u][v]] for u in range(n)]

    match_right = [-1] * n

    def try_kuhn(u, visited):
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or try_kuhn(match_right[v], visited):
                    match_right[v] = u
                    return True
        return False

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

    print(n - matching)


main()

計算量: 推移閉包の計算が$O(N^3)$。Kuhnのアルゴリズムによる二部マッチングは最悪$O(N\cdot E)=O(N^3)$。全体で$O(N^3)$。

Step-by-Step 解説

1推移閉包の構築
直接の関係だけでは比較可能性の判定が不完全なため、Floyd-Warshall流のビット伝播で全頂点対の到達可能性を求める。

2二部グラフの構成
各頂点を左右のコピーに持つ二部グラフを考え、reach[u][v]が真のペアに辺を張る。

3最大マッチングと最小パス被覆
マッチング辺は2頂点を同じ鎖に連結することに対応し、$N$個から始めて$M^*$回連結すると鎖数は$N-M^*$になる。

4Dilworthの定理との対応
この$N-M^*$が最小鎖分割数であり、最大反鎖のサイズと一致する。

よくあるミス

ミス	原因	正しい書き方
推移閉包を取らず与えられた辺だけで二部グラフを作ってしまう	比較可能性が推移的であることの見落とし	必ずFloyd-Warshall等で`reach`を全頂点対について求める
二部グラフの最大マッチングを一般マッチングと混同する	問題設定の違いの誤解	左右のコピーを分けた二部グラフでKuhnのアルゴリズムを使う
答えを$M^*$そのものとして出力してしまう	最小鎖数の式を誤解	正しくは$N-M^*$
DAGでない入力を想定した実装をしてしまう	制約「DAGである」の見落とし	入力がDAGであることを前提としてよい

次のステップ

発展: 最大反鎖そのものを構成する具体的な要素集合を復元する方法（König定理経由）
発展: Mirskyの定理（双対：最小反鎖分割数 = 最長鎖の長さ）との対比
次回予告（次セッション）: ローテーション継続

自己評価

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

Day 095-Q5 — Dilworthの定理（最小鎖分割・DAG最小パス被覆）

問題