Sign in Subscribe
Computer Science

Matroid Theory - 1. What is Matroid?

알고리즘 문제 해결 분야의 다양한 문제를 접하다 보면, 이른바 'Proof by AC(Accepted)'라고 불리는 상황을 자주 접하게 된다. 온라인 저지에서는 내 코드가 맞았다고 하긴 하는데... 정작 코드를 작성한 본인은 해당 로직이 왜 작동하는지 이해하지 못하는 상황. 이러한 상황이 발생하는 대표적인 사례는 정당성 증명을 생략한 상태로 그리디 알고리즘 기반의 코드를 작성한 상황이다.

그리디 알고리즘(Greedy algorithm)은 이름에서 알 수 있듯, 매 순간 최적이라고 생각되는 선택을 반복적으로 수행하는 알고리즘을 말한다. 그리디 알고리즘은 작동 방법이 굉장히 단순하다는 장점이 있지만, 항상 최적의 해를 찾을 수 있다는 보장이 없는 치명적인 단점이 존재한다. 실제로 대부분의 상황에서 그리디 알고리즘은 최적해를 제시하지 못하며, 그리디 알고리즘으로 해결 가능한 몇몇 특수한 알고리즘 문제의 난이도는 대부분 그리디 알고리즘이 해당 문제의 최적해를 보장함을 관찰/증명하는 부분에서 기인한다.

그런데, 항상 그리디 알고리즘을 통해 최적의 해를 찾을 수 있음이 보장되는 상황이 있다면 어떨까? 놀랍게도, 매트로이드(Matriod)라 불리는 대수적 구조 하에서는 항상 그리디 알고리즘이 최적해를 찾는다는 사실이 보장된다. 심지어 일반적으로는 다항 시간 내에 해결 가능함이 보장되지 않은 문제도 매트로이드 구조 하에서는 특정 알고리즘을 통해 보다 효율적인 시간복잡도에 해결 가능하다. 본 포스트에서는 이처럼 강력한 도구인 매트로이드가 무엇이고, 매트로이드라는 대수적 구조가 가지는 다양한 특징에는 무엇이 있는지 소개하고자 한다.

  • 본 포스트의 내용은 logicae summit 2025의 매트로이드 발표와 경기과학고등학교 가해군 강연회의 발표 원고를 기반으로 작성되었습니다.

매트로이드의 정의

우선 매트로이드를 형식적으로 정의하자.

ground set $S$와 그 부분집합들의 모임 $\mathcal{I} \subseteq 2^S$에 대하여, 다음 조건들을 만족시키면 $\mathcal{M}(S, \mathcal{I})$를 매트로이드(matroid)라 한다.

- $\emptyset \in \mathcal{I}$
- $I \in \mathcal{I}$이고 $J \subseteq I$이면 $J \in \mathcal{I}$
- $I, J \in \mathcal{I}$이고 $|I| < |J|$이면, $J \setminus I$의 어떤 원소 $e$에 대하여 $I \cup \{e\} \in \mathcal{I}$

당장은 이 정의의 의미가 잘 와닿지 않을 수 있다. 특히 3번 조건은 다소 생소하게 느껴질 수 있다. 따라서 우선 몇 가지 용어를 정의한 후, 예시를 통해 매트로이드의 개념을 좀 더 직관적으로 이해해보자.

매트로이드 $\mathcal{M}(S, \mathcal{I})$에 대해, $\mathcal{I}$의 원소들을 독립 집합(independent set)이라 한다. 또 $\mathcal{I}$에 속하지 않는 $2^S$의 원소들을 종속 집합(dependent set)이라 한다.

즉, 매트로이드의 정의에서 $\mathcal{I}$는 임의의 $S$의 부분집합이 독립 집합인지 여부를 판단하는 일종의 기준으로 이해할 수 있다. 정의에 의해 부분집합이 $\mathcal{I}$에 포함된다면 독립 집합, 그렇지 않다면 독립 집합이다.

매트로이드의 예시

간단한 몇 가지 예시를 통해 매트로이드의 개념을 직관적으로 이해해보자.

$S$를 $|S| = n$인 유한 집합, $k$를 $n$ 이하의 양의 정수라고 하자. 이때, $U^{k}_{n} = \{I \subseteq S : |I| \leq k\}$ 로 정의하면, $\mathcal{M}(S, U^{k}_{n})$는 매트로이드이다.
이를 uniform matroid라 한다.

Uniform matroid는 매트로이드의 가장 단순한 예시 중 하나이다. 이 매트로이드에서 독립 집합은 단순히 크기가 $k$ 이하인 부분집합들로 정의되며, 매트로이드의 3가지 조건을 만족한다는 사실을 쉽게 확인할 수 있다.

이제 좀 더 복잡한 예시를 살펴보자.

$S$를 크기가 $m$인 벡터 $n$개로 구성된 집합이라고 하자. 이때, \[ \mathcal{I} = \{I \subseteq S : I\mbox{에 속한 벡터들이 선형 독립}\} \] 으로 정의하면, $\mathcal{M}(S, \mathcal{I})$는 매트로이드이다.
이를 linear matroid라 한다.

Linear matroid는 벡터 공간에서의 선형 독립 개념을 매트로이드의 독립 집합 개념으로 확장한 예시이다. 특히, linear matroid에서 매트로이드의 3번째 조건은 벡터공간의 기저 확장 정리와 상당히 유사하다는 사실을 관찰할 수 있다. (사실, 매트로이드가 벡터 공간의 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이므로 어느 정도 자명한 사실이기도 하다.)

마지막으로 다소 뜬금없어 보이는 예시를 살펴보자.

$G = (V, E)$를 유한 그래프라고 하자. 이때, \[ \mathcal{I} = \{I \subseteq E : I\mbox{ is forest}\} \] 으로 정의하면, $\mathcal{M}(E, \mathcal{I})$는 매트로이드이다. 이를 graphic matroid라 한다.

(이때 forest는 사이클이 없는 그래프를 말한다. 즉, 각 연결 성분이 tree인 그래프다 .)

Graphic matroid는 매트로이드의 확장성을 잘 보여준다. 앞선 예시와 마찬가지로 1번과 2번 조건은 자명하지만, 3번 조건은 다소 직관적이지 않다. Graphic matroid가 3번 조건을 만족한다는 사실은 다음과 같이 증명 가능하다.

💡
proof $I, J \in \mathcal{I}$이고 $|I| < |J|$라고 하자. 즉, $I$와 $J$는 각각 그래프 $G$의 사이클이 없는 부분집합이며, $J$가 $I$보다 더 많은 간선을 포함하고 있다. 이제 $J \setminus I$의 어떤 원소 $e$에 대하여 $I \cup \{e\} \in \mathcal{I}$임을 보이면 충분하다.

사이클이 없다는 점 때문에 모든 컴포넌트는 반드시 트리 형태이고, 따라서 각 컴포넌트의 간선 개수는 정점 개수보다 1 작다. $|I| < |J|$이므로, $J$에는 $I$에서 같은 컴포넌트에 속하지 않는 간선이 적어도 하나 존재하며, 이 간선을 $e$로 잡으면 $I \cup \{e\}$가 사이클을 형성하지 않는다.

한 가지 재미있는 사실은 graphic matroid는 linear matroid의 특수한 경우라는 점이다. 즉, 모든 그래픽 매트로이드는 선형 매트로이드로 표현할 수 있다. 어떤 그래프 G를 $|V|\times|E|$의 인접행렬로 나타내자. 이 행렬의 열벡터들은 그래프 G의 간선들에 대응하며, 하나의 간선이 연결하는 두 정점에 임의로 1과 -1의 값을 주면 이 linear matroid에서 $I$를 만드는 행위는 graphic matroid와 동치이다.

이외에도 partition matroid, matching matroid 등 다양한 매트로이드의 유형이 있다. 어떤 종류의 매트로이드가 존재하는지 일일이 알 필요는 없지만, 다양한 예시를 통해 매트로이드에 대한 몇 가지 중요한 직관을 얻을 수 있다. 특히, linear matroid와 graphic matroid의 직관적 성질들은 이후에 다룰 용어와도 큰 관련이 있는 등 가장 기본적이면서도 핵심적인 유형이라 볼 수 있다.

Basis, Circuir, Rank


논의를 이어가기에 앞서 매트로이드에서 중요하게 다뤄지는 몇 가지 중요한 용어를 정의해보자.

basis

매트로이드의 독립 집합, 즉 \mathcal{I}의 원소 중 최대 크기를 갖는 것을 basis라 한다.

매트로이드 $\mathcal{M}(S, \mathcal{I})$에 대하여, $\mathcal{B} = {B \in \mathcal{I} : \nexists I \in \mathcal{I}, |I| > |B|}$ 로 정의하면, $\mathcal{B}$의 원소들을 기저(basis)라 한다.

매트로이드의 기저는 벡터 공간에서의 기저와 유사한 역할을 한다. 특히 매트로이드의 3번 공리로부터, 모든 기저는 같은 크기를 갖는다는 사실을 알 수 있다. (관심이 있다면 $S={1,2,3}, \mathcal{I}={(),(1),(2),(3),(1,2),(2,3)}$에서 매트로이드 $\mathcal{M}(S, \mathcal{I})$가 가지는 기저를 손으로 직접 구해보자.) 이러한 성질은 선형대수학의 기저 대체 정리와 유사한 방법으로 증명할 수 있다.

circuit

한편으로, '최대 독립' 집합을 basis로 정의한 것 처럼 '최소 종속' 집합 역시 circuit이라는 이름으로 정의된다.

매트로이드 $\mathcal{M}(S, \mathcal{I})$에 대하여, $ \mathcal{C} = {C \subseteq S : C \notin \mathcal{I}, \forall C' \subsetneq C, C' \in \mathcal{I}} $ 로 정의하면, $\mathcal{C}$의 원소들을 회로(circuit)라 한다.

circuit 용어의 근원에 관해 재미있는 사실이 있다. basis의 경우 쉽게 유추할 수 있듯 선형대수학에서 벡터 공간의 기저로부터 유래한 용어이지만, circuit의 경우 그래프 이론에서의 회로로부터 유래한 용어이다. 실제로 graphic matroid에서 circuit은 그래프 이론에서 말하는 회로(사이클) 개념과 일치한다는 사실을 알 수 있다.

rank

마지막으로 매트로이드의 랭크에 대해 알아보자.

매트로이드 $\mathcal{M}(S, \mathcal{I})$에 대하여, $r(X) = \max{|I| : I \subseteq X, I \in \mathcal{I}}$ 로 정의되는 함수 $r:2^S \rightarrow \mathbb{N}$을 랭크 함수(rank function)라 한다.

매트로이드의 랭크는 매트로이드의 기저의 크기와 같다. 즉, 매트로이드 $\mathcal{M}(S, \mathcal{I})$에 대하여, 모든 $B \in \mathcal{B}$에 대하여 $|B| = r(\mathcal{M})$이다. 랭크는 $2^S$를 정의역으로, $\mathbb{N}$를 치역으로 하는 특별한 성질을 가진 함수로도 이해할 수 있다. 당장은 basis나 circuit에 비해 비교적 덜 친숙한 용어겠지만, 이후 매트로이드가 가지는 여러 중요한 성질을 증명하기 위해 필수적으로 필요하다.

새로운 용어를 정의했으니, 이들의 간단한 특징 몇 가지를 살펴보자. 우선 basis에 관한 두 가지 성질을 알아보자.

$B$, $B'$이 매트로이드 $\mathcal{M}(S, \mathcal{I})$의 두 기저라고 하자. 이때, $|B| = |B'|$이다.
💡
proof $|B| < |B'|$라고 가정하자. 매트로이드의 3번 공리에 의해, $B' \setminus B$의 어떤 원소 $e$에 대하여 $B \cup {e} \in \mathcal{I}$이다. 이는 $B$가 기저라는 가정에 모순된다. 마찬가지로 $|B| > |B'|$라고 가정해도 모순이 발생하므로, $|B| = |B'|$이다.
[Strong Base Exchange Theorem] $B, B'$이 매트로이드 $\mathcal{M}(S, \mathcal{I})$의 서로 다른 두 기저이고, $e \in B \setminus B'$라고 하자. 이때, $B' \setminus B$의 어떤 원소 $f$에 대하여 $B \setminus {e} \cup {f}$도 기저이다.
💡
proof 매트로이드의 3번 공리에 의해, $B' \setminus B$의 어떤 원소 $f$에 대하여 $B \setminus {e} \cup {f} \in \mathcal{I}$이다. 이제 $B \setminus {e} \cup {f}$가 기저임을 보이면 충분하다. 만약 $B \setminus {e} \cup {f}$가 기저가 아니라고 가정하면, $\mathcal{I}$에 속하는 어떤 집합 $C$가 존재하여 $|C| > |B \setminus {e} \cup {f}|$이다. 그런데 $|B \setminus {e} \cup {f}| = |B|$이므로, $|C| > |B|$이다. 이는 $B$가 기저라는 가정에 모순된다. 따라서 $B \setminus {e} \cup {f}$도 기저이다.

다음은 Strong Base Exchange Theorem의 중요한 따름정리와 증명이다.

$I_1, I_2$가 매트로이드 $\mathcal{M}(S, \mathcal{I})$의 서로 다른 두 독립 집합이고, $e \in I_1 \setminus I_2$라고 하자. 이때, $I_2 \setminus I_1$의 어떤 원소 $f$에 대하여 $I \setminus {e} \cup {f}$도 독립 집합이다.
💡
$|I_1|=|I_2|=K$라고 하자. $\mathcal{I'}$을 $\mathcal{I}$의 원소 중 크기가 $K$ 이하인 것들의 집합이라고 하자. 이때 $\mathcal{M'}(S, \mathcal{I'})$는 매트로이드이다. 이제 $I_1, I_2$는 $\mathcal{M'}$의 기저이므로, Theorem\autoref{thm:exchange}에 의해 $I_2 \setminus I_1$의 어떤 원소 $f$에 대하여 $I_1 \setminus {e} \cup {f}$도 기저이다. 따라서 $I_1 \setminus {e} \cup {f} \in \mathcal{I}$.

basis에 관한 성질은 선형대수학의 언어에 익숙하다면 직관적으로 이해할 수 있을 것이다. 특히 Strong Base Exchange Theorem와 lemma의 결과는 추후 다룰 matroid intersection에서도 핵심적으로 사용된다.

다음으로 circuit의 성질을 알아보자.

[Unique Circuit Property] $C$가 매트로이드 $\mathcal{M}(S, \mathcal{I})$의 회로라고 하자. 이때, 임의의 $e \in C$에 대하여 $C \setminus {e} \in \mathcal{I}$이다.
$C_1$, $C_2$가 매트로이드 $\mathcal{M}(S, \mathcal{I})$의 서로 다른 두 회로이고, $e \in C_1 \cap C_2$라고 하자. 이때, $(C_1 \cup C_2) \setminus {e}$에는 적어도 하나의 회로가 포함되어 있다.

위 정리에 대한 증명은 직접 고민해 보길 바란다. unique circuit property를 활용하여 증명할 수 있다.

circuit의 성질에 관한 직관은 그래프를 다루는 것에 익숙하다면 쉽게 얻을 수 있다. 마지막으로 rank 함수의 성질을 알아보자.

💡
매트로이드 $\mathcal{M}(S, \mathcal{I})$의 임의의 부분집합 $X, Y \subseteq S$에 대하여, 다음이 성립한다.
- $0 \leq r(X) \leq |X|$
- $X \subseteq Y$이면, $r(X) \leq r(Y)$
- (submodularity) $r(X \cup Y) + r(X \cap Y) \leq r(X) + r(Y)$

3번 성질에서 부등호가 대신 $=$이라면 modular하다고 하며, 반대로 $\geq$가 되면 supermodular하다고 한다. 1번과 2번 성질의 경우 어느 정도 직관적으로 받아들일 수 있지만, 3번 성질의 경우 직관적으로 이해하기 다소 어렵다. 엄밀한 증명은 당장은 생략하지만, 추후 matroid intersection을 다루며 엄밀성과 함께 충분한 직관을 얻을 수 있을 것이다.

매트로이드의 쓸모

매트로이드의 정의와 기본적인 용어, 성질에 대해 간단히 다뤄보았다. basis, circuit, rank 등 몇 가지 핵심적인 용어와 각각이 가지는 성질 및 증명을 알아보았지만, 사실 아직 매트로이드가 어떻게 활용될 수 있는지는 잘 감이 잡히지 않을 것이라고 생각한다. 매트로이드 이론은 총 세 번에 걸쳐 소개할 예정인데, 다음 글에서는 앞서 서두에서 언급한 그리디 알고리즘과 매트로이드의 관계에 대해 소개한다. 또, PS(Problem Solving) 분야에서 매트로이드의 쓰임 역시 간단히 소개할 예정이다.

사실 2편에서의 내용은 1편에서 소개한 용어의 정의 정도만 이해한다면 어렵지 않게 이해할 수 있을 것이다. 다만 매트로이드 이론의 꽃이라고 볼 수 있는 matroid intersection의 내용을 3편에 다룰 예정인데, 평소 수학과 PS에 관심이 있는 독자라면 많은 아름다움을 느낄 수 있으리라 생각한다.

참고자료

Read next

연속 속도 변화 환경에서의 최단 시간 경로 분석

연속 속도 변화 환경에서의 최단 시간 경로 분석

본 포스트는 본인이 제작한 2025학년도 경기과학고등학교 수학II 과목 자율탐구보고서의 내용을 기반으로 작성되었습니다. 서론 공간상의 각 위치에서 이동 속도가 주어질 때, 한 점에서 다른 점으로 이동하는 최단 시간 경로를 찾는 문제는 실생활의 다양한 사례와 연계된다. 대표적으로 해변가에서 최단 구조 시간 경로를 찾는 문제는 한 직선을 기준으로 두 평면에서 이동 속도가 다를
Kim Minjae

Comments ()