← 루비 V

일반 매칭

블로섬 알고리즘 — 홀수 사이클을 접어 매칭한다.

그래프

루비 V

선수 지식: 이분 매칭

1강 블로섬: 홀수 사이클을 접는다 공식

일반 그래프의 최대 매칭

이분 그래프에서는 증가 경로(augmenting path)를 BFS/DFS로 찾아 매칭을 키운다. 일반 그래프에서도 베르주 정리(Berge's theorem) 가 그대로 성립한다.

매칭 $$M$$ 이 최대 매칭일 필요충분조건은 $$M$$ 에 대한 증가 경로가 존재하지 않는 것이다.

문제는 증가 경로 탐색 자체다. 이분 그래프에서는 홀수 길이 사이클이 없어 단순 BFS로 충분하지만, 일반 그래프에는 홀수 사이클이 생긴다.

블로섬(blossom)이란

매칭 $$M$$ 이 주어졌을 때 노출 정점(매칭되지 않은 정점)에서 출발하는 교대 경로(alternating path)를 생각하자. 정점을 출발점으로부터의 거리 홀짝에 따라 odd/even으로 분류한다.

탐색 도중 두 even 정점 $$u, v$$ 사이에 간선이 발견되고, 둘이 공통 조상 $$b$$ (베이스)를 가지면, 길이 $$2k+1$$ 의 홀수 사이클이 만들어진다. 이 사이클을 블로섬이라 부른다.

핵심 통찰: 블로섬 안의 모든 정점은 베이스를 통해 even 상태로 도달 가능하다. 따라서 블로섬 전체를 하나의 슈퍼 정점으로 수축(contract) 해도 증가 경로의 존재 여부가 보존된다.

수축의 정당성

블로섬 $$B$$ 를 수축한 그래프를 $$G/B$$ 라 하자. 에드몬즈의 정리:

$$G/B$$ 에 증가 경로가 있을 필요충분조건은 $$G$$ 에 증가 경로가 있는 것이다.

증명 스케치: 블로섬은 베이스를 제외한 모든 정점이 사이클 내부에서 매칭되어 있으므로, 슈퍼 정점을 지나는 경로는 블로섬 둘레를 따라 적절한 방향으로 펼치면 항상 원본 그래프의 교대 경로로 복원된다. 홀수 둘레 덕분에 양쪽 방향 중 하나는 반드시 매칭 간선으로 시작/끝난다.

알고리즘 골격

노출 정점에서 BFS로 교대 숲(forest)을 만든다.
even–even 간선을 만나면:
- 서로 다른 트리면 → 증가 경로 발견, 따라 가며 $$M$$ 반전.
- 같은 트리면 → 블로섬 발견, LCA를 베이스로 수축.
더 이상 증가 경로가 없을 때까지 반복.

복잡도

각 노출 정점에서의 탐색이 $$O(V^2)$$ , 노출 정점이 $$O(V)$$ 개이므로 단순 구현은 $$O(V^3)$$ . 실제 구현에서는 union-find로 블로섬을 관리해 $$O(VE)$$ 또는 그 이하로 줄인다.

항목	이분 그래프	일반 그래프
핵심 난점	없음	홀수 사이클
도구	BFS	블로섬 수축
복잡도	$$O(VE)$$	$$O(V^3)$$

다음 강의에서 union-find 기반의 구현을 본다.

2강 블로섬 알고리즘 구현 공식

union-find 기반 블로섬

블로섬을 매번 실제로 수축하면 비싸다. 대신 base[] 배열 + union-find 로 "이 정점이 속한 블로섬의 베이스"를 추적한다. 표준 $$O(V^3)$$ 구현을 보자.

상태 정의

match[v]: $$v$$ 의 짝 (없으면 -1)
p[v]: 교대 숲에서의 부모
base[v]: $$v$$ 가 속한 블로섬의 베이스
color[v]: 0=흰색(미방문), 1=검정(odd), 2=회색은 사용 안 함 — 여기선 used[]로 even 표시

LCA로 블로섬 베이스 찾기

int lca(int a, int b) {
    static vector<bool> used(n, false);
    fill(used.begin(), used.end(), false);
    while (true) {                       // a를 따라 루트까지 표시
        a = base[a];
        used[a] = true;
        if (match[a] == -1) break;
        a = p[match[a]];
    }
    while (true) {                       // b를 따라가다 표시된 정점이 LCA
        b = base[b];
        if (used[b]) return b;
        b = p[match[b]];
    }
}

블로섬 표시(마킹)

void markPath(int v, int b, int child, vector<int>& p,
              vector<int>& base, vector<bool>& blossom) {
    while (base[v] != b) {
        blossom[base[v]] = true;
        blossom[base[match[v]]] = true;
        p[v] = child;                    // 블로섬 내부 간선 방향 재설정
        child = match[v];
        v = p[match[v]];
    }
}

증가 경로 탐색(BFS)

int findPath(int root) {
    fill(used.begin(), used.end(), false);
    iota(base.begin(), base.end(), 0);   // base[v] = v
    fill(p.begin(), p.end(), -1);
    queue<int> q; q.push(root); used[root] = true;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : g[v]) {
            if (base[v] == base[to] || match[v] == to) continue;
            if (to == root || (match[to] != -1 && p[match[to]] != -1)) {
                int cur = lca(v, to);    // 블로섬 발견
                vector<bool> blossom(n, false);
                markPath(v, cur, to, p, base, blossom);
                markPath(to, cur, v, p, base, blossom);
                for (int i = 0; i < n; i++)
                    if (blossom[base[i]]) {
                        base[i] = cur;
                        if (!used[i]) { used[i] = true; q.push(i); }
                    }
            } else if (p[to] == -1) {
                p[to] = v;
                if (match[to] == -1) return to;   // 증가 경로 끝
                used[match[to]] = true;
                q.push(match[to]);
            }
        }
    }
    return -1;
}

매칭 갱신과 전체 루프

int maxMatching() {
    int res = 0;
    fill(match.begin(), match.end(), -1);
    for (int v = 0; v < n; v++) if (match[v] == -1) {
        int u = findPath(v);
        while (u != -1) {                // 경로를 따라 반전
            int pv = p[u], ppv = match[pv];
            match[u] = pv; match[pv] = u;
            u = ppv;
        }
        if (match[v] != -1) res++;       // 정확히는 짝지어진 정점 절반이 답
    }
    return res;                          // 매칭 간선 수 = (짝지어진 정점)/2
}

연습

짝수 정점 그래프에서 완전 매칭 존재 판정.
일반 그래프 최대 매칭으로 환원되는 격자/그리드 문제(도미노 타일링은 이분이지만, 일반 매칭이 필요한 비이분 변형 연습).
검증: 매칭 간선 수가 $$V/2$$ 면 완전 매칭.

복잡도는 $$O(V^3)$$ . $V \le 500$ 정도까지 안정적으로 통과한다.