매트로이드

독립성의 공리화

집합 \(E\)(원소들)와 그 부분집합 모임 \(\mathcal{I}\)(독립 집합들)의 쌍 \(M = (E, \mathcal{I})\)가 매트로이드 라는 것은 다음 세 공리를 만족하는 것이다.

1. (비공집합성) \(\emptyset \in \mathcal{I}\).
2. (유전성) \(A \in \mathcal{I}\)이고 \(B \subseteq A\)이면 \(B \in \mathcal{I}\).
3. (교환 공리) \(A, B \in \mathcal{I}\)이고 \(|A| < |B|\)이면, 어떤 \(x \in B \setminus A\)가 존재해 \(A \cup \{x\} \in \mathcal{I}\).

세 번째가 매트로이드의 본질이다. "더 큰 독립 집합이 있으면, 작은 쪽을 항상 한 원소 늘릴 수 있다."

대표 예시

그래프 매트로이드의 교환 공리가 곧 "신장 트리는 모두 같은 크기"라는 사실이다.

랭크 함수

\(r(S) = \max\{|A| : A \subseteq S,\ A \in \mathcal{I}\}\)를 랭크 라 한다. 랭크는 서브모듈러:

$$ r(A) + r(B) \ge r(A \cup B) + r(A \cap B). $$

매트로이드의 모든 극대 독립 집합(=base)은 크기가 같고 그 크기가 \(r(E)\)다. 이는 교환 공리의 직접 따름.

그리디 정리

원소에 가중치 \(w: E \to \mathbb{R}\)가 주어졌을 때, 최대 가중치 독립 집합을 다음 그리디가 항상 최적으로 푼다.

가중치 내림차순으로 원소를 본다.
현재 집합에 넣어도 독립이면 넣는다.

정리. 위 그리디가 최적해를 주는 것은 \((E, \mathcal{I})\)가 매트로이드일 필요충분조건 이다.

정당성 증명 스케치

그리디 해 \(G = \{g_1, \dots, g_k\}\)(가중치 내림차순)와 임의의 최적해 \(O\)를 비교한다. 교환 공리를 반복 적용하면, 매 단계에서 \(g_i\)의 가중치가 \(O\)의 \(i\)번째로 큰 원소 가중치 이상임을 귀납적으로 보일 수 있다. 따라서 \(\sum w(g_i) \ge \sum w(o_i)\). 역방향(매트로이드가 아니면 그리디 실패)은 교환 공리가 깨지는 반례를 직접 구성해 보인다.

이것이 크루스칼 알고리즘이 최소 신장 트리를 주는 진짜 이유 다. MST = 그래프 매트로이드에서 그리디.

정리

• 매트로이드 = 독립성 + 교환 공리.
• 모든 base는 동일 크기, 랭크는 서브모듈러.
• 그리디 최적성 ⟺ 매트로이드. 다음 강의에서 사례 연구.

이 강의의 목표

매트로이드는 코드 한 덩어리로 요약되지 않는다. 핵심은 문제를 매트로이드로 인식 하는 것. 네 가지 사례로 훈련한다.

사례 1: MST는 그래프 매트로이드 그리디

크루스칼은 "사이클을 만들지 않으면 추가"하는 그리디. 독립 = 숲, 가중치 = 간선 비용(최소화는 부호 반전). union-find가 독립성 오라클이다.

sort(edges.begin(), edges.end());        // 가중치 오름차순
for (auto [w, u, v] : edges)
    if (find(u) != find(v)) {            // 넣어도 숲이면(독립)
        unite(u, v); total += w;         // 추가
    }

사례 2: 작업 스케줄링 (분할 매트로이드)

마감 시한 \(d_i\), 이익 \(p_i\)인 단위 작업들. 각 작업을 어떤 시간 슬롯 에 배치하되 슬롯당 하나. "선택한 작업 집합이 슬롯에 충돌 없이 배치 가능"이 독립성이고, 이는 횡단 매트로이드 구조. 이익 내림차순 그리디 + (역방향으로 빈 슬롯 찾기) 가 최적.

sort(jobs.rbegin(), jobs.rend());        // 이익 내림차순
for (auto& j : jobs)
    for (int t = min(maxSlot, j.deadline); t >= 1; t--)
        if (!used[t]) { used[t] = true; profit += j.profit; break; }

독립성을 매트로이드로 증명 했기에 그리디가 옳다고 단언할 수 있다.

사례 3: 색 제한이 있는 신장 트리

"각 색 간선을 정확히 \(c\)개씩 쓰는 신장 트리"는 그래프 매트로이드 ∩ 분할 매트로이드의 base 문제다. 단일 매트로이드 그리디로는 안 되고, 두 매트로이드의 교집합이 필요 — 다음 단계 주제(매트로이드 교집합)로 이어진다. 인식 자체가 중요한 단계.

사례 4: 일차독립 부분집합 (선형 매트로이드)

\(\mathbb{F}_2\) 위 벡터(예: XOR 기저)에서 최대 가중치 일차독립 집합. 독립성 오라클 = 가우스 소거(기저에 추가 가능?).

// XOR 선형 매트로이드: 가중치 내림차순으로 기저 삽입 시도
long long basis[60] = {0};
sort(vec.rbegin(), vec.rend());          // 가중치 내림차순
for (auto& [w, x] : vec) {
    long long cur = x;
    for (int b = 59; b >= 0; b--) if ((cur >> b) & 1) {
        if (!basis[b]) { basis[b] = cur; ans += w; break; }
        cur ^= basis[b];                 // 종속이면 소거
    }
    // cur == 0 이면 기존 기저에 종속 → 버림
}

이는 "가중치 최대 XOR 기저" 문제이며, 선형 매트로이드 그리디의 직접 응용이다.

인식 체크리스트

문제에서 "부분집합을 고르되 어떤 제약하에 가중치 최대화"가 보이면 자문하라.

1. 독립성(제약)이 유전적 인가? (부분집합도 유효한가)
2. 교환 공리 가 성립하는가? (작은 유효 집합을 항상 키울 수 있나)
3. 둘 다 yes면 → 가중치 그리디가 최적.

함정

• "유전적이지만 교환 공리가 깨지는" 구조(예: 일반 그래프 매칭의 간선 집합)에는 그리디가 틀린다. 매트로이드인지 반드시 확인.
• 두 제약의 동시 만족(예: 색 제한 + 비순환)은 단일 매트로이드가 아니다 → 교집합 알고리즘 필요.

매트로이드의 힘은 알고리즘이 아니라 언어 다. 문제를 매트로이드로 번역하면, 그리디의 정당성이 공짜로 따라온다.