Day 106-Q5 | König's Edge Coloring（二部グラフの辺彩色）

問題

左側頂点$L=\{1,\dots,N\}$、右側頂点$R=\{1,\dots,N\}$を持つ、常に$\Delta$-正則（全頂点の次数が$\Delta$）な二部多重グラフが与えられる。辺総数は$M=N\Delta$。

同じ頂点に接続する2辺には異なる色が付くように辺彩色したい。König の定理（二部グラフの辺彩色数は最大次数$\Delta$に等しい）に基づき、ちょうど$\Delta$色を使った辺彩色を構築せよ。

入力形式

N Δ
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 200$

$1 \le \Delta \le 50$

入力は常に$\Delta$-正則な二部多重グラフ

出力: Special Judge（複数の正解あり）

入出力例

入力例1

出力例1（正当な出力の一例）

1〜3番目の辺は完全マッチング（色1）、4〜6番目も完全マッチング（色2）。左2-右3を結ぶ辺が2本あるが色1と色2で異なるため正しい。

概念図: 奇数なら完全マッチングを剥がす／偶数ならオイラー閉路で半分割

ヒント（段階的開示）

ヒント1: 方向性

「各辺を順に見て両端点で未使用の最小色を貪欲に割り当てる」方法では、一般グラフでは$2\Delta-1$色まで必要になることがある。二部グラフに限れば必ず$\Delta$色で彩色できる（König の定理）が、それには「1本ずつ塗る」のではなく「グラフ全体を段階的に分割していく」発想が必要。

ヒント2: アプローチ

$\Delta$-正則二部グラフには2つの性質がある。①$\Delta$が偶数なら各連結成分はオイラー閉路を持ち、閉路を辿って辺を交互に2グループへ振り分けると各グループが$\Delta/2$-正則になる（二部性から証明できる）。②$\Delta$が奇数なら必ず完全マッチングを持つ（Hallの定理）ので、それを1色として剥がせば残りは$(\Delta-1)$-正則（偶数）に帰着する。「奇数なら剥がす・偶数なら半分に割る」を再帰すれば必要な色数はちょうど$\Delta$になる。

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

def color(edges, d):
    if d == 0: return
    if d == 1:
        edges 全体に新しい色を1つ割り当てる
        return
    if d % 2 == 1:
        matching = 完全マッチング(edges)  # Kuhn法
        matching に新しい色を割り当てる
        color(edges - matching, d - 1)
    else:
        g1, g2 = オイラー閉路(Hierholzer法)で辺を交互に2分割
        color(g1, d // 2)
        color(g2, d // 2)

模範解答 (Python)

import sys
from collections import defaultdict

sys.setrecursionlimit(1000000)


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    delta = int(data[idx]); idx += 1
    m = n * delta
    edge_list = []
    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        edge_list.append((u, v))

    colorof = [0] * m
    next_color = [1]

    def kuhn_matching(edges_here):
        adj = defaultdict(list)
        left_nodes = []
        seen_left = set()
        for eid in edges_here:
            u, v = edge_list[eid]
            adj[u].append((v, eid))
            if u not in seen_left:
                seen_left.add(u)
                left_nodes.append(u)
        match_right = {}

        def try_kuhn(u, visited):
            for v, eid in adj[u]:
                if v in visited:
                    continue
                visited.add(v)
                if v not in match_right or try_kuhn(match_right[v][0], visited):
                    match_right[v] = (u, eid)
                    return True
            return False

        for u in left_nodes:
            try_kuhn(u, set())
        matched_eids = set(info[1] for info in match_right.values())
        remaining = [eid for eid in edges_here if eid not in matched_eids]
        return matched_eids, remaining

    def euler_split(edges_here):
        adj = defaultdict(list)
        for eid in edges_here:
            u, v = edge_list[eid]
            adj[('L', u)].append([('R', v), eid])
            adj[('R', v)].append([('L', u), eid])
        used_edge = set()
        ptr = defaultdict(int)
        g1, g2 = [], []
        for start in list(adj.keys()):
            has_unused = any(eid not in used_edge for _, eid in adj[start])
            if not has_unused:
                continue
            it_stack = [start]
            walk_edges = []
            while it_stack:
                v = it_stack[-1]
                adv = adj[v]
                p = ptr[v]
                while p < len(adv) and adv[p][1] in used_edge:
                    p += 1
                ptr[v] = p
                if p < len(adv):
                    nxt, eid = adv[p]
                    used_edge.add(eid)
                    ptr[v] = p + 1
                    it_stack.append(nxt)
                    walk_edges.append(eid)
                else:
                    it_stack.pop()
            for i2, eid in enumerate(walk_edges):
                (g1 if i2 % 2 == 0 else g2).append(eid)
        return g1, g2

    def color_regular(edges_here, d):
        if d == 0:
            return
        if d == 1:
            c = next_color[0]
            next_color[0] += 1
            for eid in edges_here:
                colorof[eid] = c
            return
        if d % 2 == 1:
            matched, remaining = kuhn_matching(edges_here)
            c = next_color[0]
            next_color[0] += 1
            for eid in matched:
                colorof[eid] = c
            color_regular(remaining, d - 1)
        else:
            g1, g2 = euler_split(edges_here)
            color_regular(g1, d // 2)
            color_regular(g2, d // 2)

    color_regular(list(range(m)), delta)
    print("\n".join(map(str, colorof)))


solve()

計算量: マッチング抽出$O(\Delta \cdot N\Delta)$、オイラー閉路分割は各段で$O(N\Delta)$を$O(\log\Delta)$段。ランダム多数ケースで彩色の正当性（隣接辺の色重複なし・使用色数=Δ）を検証済み。

Step-by-Step 解説

1再帰の不変条件
color_regular(edges, d)は「edgesが張るグラフが必ずd-正則」を不変条件とする。d=1の葉では残りが自動的にちょうど1つの完全マッチングになる。

2奇数のとき: 完全マッチングを剥がす
d-正則二部グラフは必ず完全マッチングを持つ（Hallの結婚定理）。Kuhn法で1つ求め色を割り当て、残りを(d-1)-正則として再帰する。

3偶数のとき: オイラー閉路による半分割
各連結成分は偶数次数dなのでHierholzer法でオイラー閉路を構築できる。閉路を辿った順で辺を交互に2グループへ振り分けると両方がd/2-正則になる。

4色数の見積もり
再帰木の深さは高々O(log Δ)段、生成される色（d=1の葉）の数は必ずちょうどΔ個になる。

よくあるミス

ミス	原因	正しい書き方
オイラー閉路の辺を頂点到着順で交互分割する	基準を誤ると片方だけ次数が偏りd/2-正則にならない	閉路をたどって辺をpush/popした順序で交互に振り分ける
Kuhn法のvisitedを右頂点で管理し忘れる	同じ右頂点を1回の探索で複数回訪問し無限再帰の恐れ	各try_kuhn呼び出し内で訪問済み右頂点集合を必ず管理する
多重辺を(u,v)キーの辞書で管理する	同じ頂点ペアの多重辺の一方しか塗れない	辺は入力順の辺idで管理し、頂点ペアでなく辺idに色を対応づける
Kuhnの再帰でPython再帰上限に達する	Nが大きいと再帰深さがNに達しうる	sys.setrecursionlimitを十分大きく設定する

次のステップ

発展: 一般グラフの辺彩色をVizingの定理に基づき$\Delta+1$色で構築する（Misra & Griesのアルゴリズム）
発展: 正則とは限らない一般の二部グラフをダミー頂点・辺で正則化してから本アルゴリズムに帰着する
次回予告: Leftist Heap（左偏ヒープ）に立ち戻り、Skew Heapとの実装比較で総復習

自己評価

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

Day 106-Q5 — König's Edge Coloring（二部グラフの辺彩色）

問題