Introduction to matroid
Matroid
정의 1. matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $\mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다.
- $\phi \in \mathcal{I}$
- $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$
- $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재
매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인 예 몇 가지를 살펴보자.
예시 1. Vector matroid
체 $\mathbb{F}$ 상에서 정의된 $m \times n$ 행렬 $A$을 생각하자. $v_i$를 $A$의 $i$번째 column vector라 하면 $v_i$들은 벡터공간 $\mathbb{F}^m$의 벡터이다. $S = \left\{1, 2, .., n \right\}$ , $\mathcal{I} = \left\{ I : I \subset S, \left\{v_i\right\}_{i \in I} \: are \: linearly \: independent \right\}$ 로 놓으면 $\mathcal{M} = (S, \mathcal{I})$는 matroid가 됨을 쉽게 알 수 있다. (1, 2번 조건은 자명하고, 3번의 경우 $\lvert X \rvert < \lvert Y \rvert$이고 둘 모두 independent한 vector들의 집합이므로 $X$의 벡터들이 $Y$의 벡터공간 전체를 span할 수 없다)
예시 2. Graphic matroid
$G = (V, E)$가 무향 그래프일 때, $\mathcal{I} = \left\{I : I \subset E, I \: induces \: a \: forest \: in \: G \right\}$로 놓으면 $\mathcal{M} = (E, \mathcal{I})$는 matroid가 된다. 1, 2번 조건은 앞서와 마찬가지로 자명하고, 3번 조건의 경우 $X$에 포함된 edge들을 모두 이었을 때 component의 개수는 $N - \lvert X \rvert$이고, $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재하지 않는다면 $Y$의 edge들의 두 끝점이 한 component에 들어가야 하므로 $Y$에 포함된 edge들을 모두 이었을 때 component의 개수는 $N-\lvert X \rvert$ 이상인데 이것은 $N-\lvert Y \rvert$와 같아야 하므로 $\lvert X \rvert <\lvert Y \rvert$에 모순이다. 따라서, 3번 조건 역시 만족한다. Graphic matroid의 경우는 뒤에 다룰 minimum spanning tree를 구하는 kruskal 알고리즘의 증명에 이용된다.
예시 2-1. Graphic matroid의 변형
그래프에서 matroid는 예시 2처럼만 정의할 수 있는 것이 아니다. $G = (V, E)$가 무향 연결 그래프일 때, $\mathcal{I} = \left\{I : I \subset E, E - I \: connects \: all \: vertex \: in \: G \right\}$로 두면 $\mathcal{M} = (E, \mathcal{I})$는 matroid이다. $\mathcal{I}$가 공집합을 포함해야 하므로 $G$가 connected가 아닌 경우에는 matroid가 되지 않음에 주의해야 한다. 또 다른 예시로는 어떤 edge 집합으로 induced되는 그래프에서 각 component의 edge 개수가 vertex 개수를 넘지 않는 경우를 독립집합으로 정의하면 matroid가 된다. (즉, 각 컴포넌트가 트리 형태를 띠거나 하나의 cycle에 tree가 붙어 있는 형태인 경우) 두 가지 matroid 모두 정의 3이 간단히 증명되며, 나중에 소개할 maximum weight independent set algorithm을 이용하면 재미있는 결과를 얻을 수 있다.
예시 3. Uniform matroid
Uniform matroid는 어쩌면 생각할 수 있는 가장 쉬운 matroid이다. 어떠한 $k$를 정한 후 $S$에서 크기가 $k$ 이하인 모든 부분집합을 independent set으로 놓으면 uniform matroid가 된다.
예시 4. Partition matroid
Partition matroid는 Uniform matroid의 일반화라고 볼 수 있다. $S_1, S_2, …, S_n$이 $S$의 분할이고, $k_1, k_2, …, k_n$이 양의 정수일 때, $\mathcal{I} = \left\{ I : I \subset S, \lvert I \cap S_i \rvert \le k_i \: for \: all \: 1 \le i \le n \right\}$ 로 정의하면 $\mathcal{M} = (S, \mathcal{I})$는 matroid이다. partition matroid나 uniform matroid 같은 경우는 matroid임이 자명하기 때문에 이것이 매트로이드라는 것이 특별한 것은 아니지만, 다음 포스팅에서 다룰 matroid intersection의 경우 graphic matroid나 vector matroid 등 다른 matroid와의 maximal matroid intersection / maximum weight matroid intersection을 구하는 문제 등에서 사용된다.
예시 5. Transversal matroid
$G = (V, E)$가 bipartition $V_1$과 $V_2 $를 가지는 이분그래프(bipartite graph)일 때,
$\mathcal{I} = \left\{ I : I \subset V_1, \exists \: a \: matching \: M \: in \: G \: that \: covers \: I \right\}$ 로 두면 $\mathcal{M} = (V_1, \mathcal{I})$ 은 matroid이다. 3번 조건의 경우 $X$ 와 $Y$ 각각에 매칭된 vertex들을 생각하면 자명하다.
예시 6. Matching matroid
무향그래프 $G = (V, E)$에서 $\mathcal{I} = \left\{ I : I \subset V, \exists \: a \: matching \: M \: in \: G \: that \: covers \: I \right\}$ 로 두면 $\mathcal{M} = (V, \mathcal{I})$ 은 matroid이다.
매트로이드에서 쓰이는 기본 용어 및 성질
정의 2. $\mathcal{M} = (S, \mathcal{I})$가 매트로이드일 때, $S$의 부분집합 중 $\mathcal{I}$에 포함되지 않는 것을 $\mathcal{M}$의 dependent set이라 한다.
정의 3. $\mathcal{M} = (S, \mathcal{I})$가 매트로이드일 때, $S$의 원소 $s$에 대해 $s$ 하나만으로 이루어진 집합이 dependent하다면 $s$를 loop이라고 한다.
loop은 어떠한 independent set에도 포함될 수 없기 때문에 maximal independent set을 구할 때 보통 처음부터 제외시키고 생각한다.
정의 4. $\mathcal{M}$의 independent set $I$에 대해 $I$를 진부분집합으로 갖는 independent set이 없다면 $I$를 $\mathcal{M}$의 base라고 한다.
성질 1. $\mathcal{M}$의 모든 base들의 크기는 동일하다. 또한, base와 크기가 같은 independent set은 base이다.
증명. 이것은 정의 1의 조건 3에 의해 간단히 증명할 수 있다. 두 base의 크기가 다르다면 둘 중 크기가 작은 base에 원소를 하나 추가시켜도 independent하도록 만들 수 있는데 이는 base가 maximal이라는 정의에 모순이기 때문이다. base와 크기가 같은 independent set이 base가 아니라면 maximal이 아닌 것이므로 더 크기가 큰 independent set이 존재해야 하는데 이는 base들의 크기가 동일하다는 것과 대치된다.
성질 2. $\mathcal{M}$의 서로 다른 두 base $B_1$, $B_2$에 대해 $x \in B_1 \setminus B_2$, $y \in B_2 \setminus B_1$이 존재하여 $B_1 - x + y$가 $\mathcal{M}$의 base이다.
증명. $B_1$이 base이므로 $B_1 - x$는 independent set이고, $B_1 - x$와 $B_2$는 서로 다른 independent set이며 모든 base의 크기가 같기 때문에 $B_2$의 크기가 $B_1 - x$보다 크므로 $y \in B_2 \setminus B_1 - x$가 존재하여 $B_1 - x + y$는 independent이다. 이는 $B_1$, $B_2$와 크기가 같은 independent set이므로 base이다.
정의 5. $\mathcal{M} = (S, \mathcal{I})$ 가 matroid이고 $S’ \subset S$ 일 때, $\mathcal{I}’ = \left\{ I : I \subset S’, I \in \mathcal{I} \right\}$ 로 두면 $\mathcal{M}’ = (S’, \mathcal{I}’)$ 역시 matroid이고 이를 $\mathcal{M}$의 $S’$에 대한 restriction이라고 한다. restriction이 matroid임은 정의에 의해 자명하다.
정의 6. matroid에서 minimal dependent set을 circuit이라 한다. 즉, $C \subset S$가 circuit일 조건은 $C \notin \mathcal{I}$이면서 $\forall x \in C, C-x \in \mathcal{I}$를 만족하는 경우이다.
graphic matroid에서의 circuit은 matroid가 정의된 그래프에서 simple cycle을 이룬다. 또한, 모든 loop은 그 자체로 circuit이다.
성질 3. $C_1$, $C_2$가 서로 다른 두 circuit이고 $x \in C_1 \cap C_2$ 라 하자. $C_1 \cup C_2- x$은 dependent하다. 즉, circuit을 포함한다.
증명. $C_1 \cup C_2- x$가 independent하다고 가정하자. $\mathcal{M}$의 $C_1 \cup C_2$에 대한 restriction을 생각했을 때, $B = C_1 \cup C_2- x$은 base이다. $C_1$과 $C_2$가 circuit이므로 $I = C_1 \cap C_2$는 independent하다. matroid 정의 중 조건 3을 이용해서 $I$가 $B$와 크기가 같아지기 전까지 $I$에 포함되지 않고 $B$에는 포함되는 원소를 계속 추가하여 independent함을 유지할 수 있다. 그렇게 만들어진 $B$와 크기가 같은 집합을 $B’$라 하자. $\lvert B’ \rvert = \lvert C_1 \cup C_2 \rvert - 1$ 이고 $C_1 \cap C_2 \subset B’$ 이므로 $C_1 \subset B’$ 또는 $C_2 \subset B’$가 성립한다. 그런데 이는 $B’$는 independent함을 유지하면서 만들어진 집합이라는 것에 모순이다. 따라서, . $C_1 \cup C_2- x$은 dependent하다.
성질 4. $\mathcal{M} = (S, \mathcal{I})$ 가 matroid라 하자. $X \in \mathcal{I}, y \notin X$ 이면 $X+y \in \mathcal{I}$ 이거나 $X+y$가 unique한 circuit $C$를 포함하며, 그 경우 모든 $\widehat{y} \in C$ 에 대해 $X+y-\widehat{y} \in \mathcal{I}$ 가 성립한다.
증명. $X+y \notin \mathcal{I}$이면 $X + y$는 적어도 하나의 circuit을 포함한다. 이를 $C_1$이라 하자. 만약 $X + y$가 다른 circuit $C_2$도 포함한다면 $X$는 independent하기 때문에 $C_1$과 $C_2$는 모두 $y$를 포함한다. $C_1 \cup C_2 - y$는 성질 3에 의해 dependent한데 이는 $C_1 \cup C_2 - y \subset X$에 모순이므로 $X+y$는 단 하나의 circuit만을 가진다. 이를 $C$라 하면 circuit의 정의에 의해 $X+y$의 모든 dependent set은 $C$를 포함해야 한다. 따라서 모든 $\widehat{y} \in C$ 에 대해 $X+y-\widehat{y} \in \mathcal{I}$ 가 성립한다.
Finding a maximum weight independent set in a matroid
matroid가 주어졌을 때, maximum weight independent set은 매우 빠른 시간에 계산할 수 있다. 또한, 음 아닌 정수 $k$가 주어졌을 때 size가 $k$인 independent set 중 weight가 maximum인 set도 쉽게 구할 수 있다. (minimum은 -1을 곱하면 maximum과 같은 방법으로 구해진다)
정리 1. 다음의 greedy 알고리즘은 $\mathcal{M} = (S, \mathcal{I})$의 maximum weight independent set을 올바르게 구한다.
- $e \in S $의 weight을 $w(e)$로 표시하자. $e$가 loop(그 자체로 dependent한 원소)이거나 $w(e) \le 0$인 원소이면 무시한다.
- 1에서 무시한 원소를 제거했을 때 $S = \left\{e_1, …, e_n\right\}$ 에서 $w(e_1) \ge w(e_2) \ge … \ge w(e_n)$ 이라 하자.
- 초기 상태에서 $X \leftarrow \phi$.
- $i$를 1부터 $n$까지 증가시키면서 $X + e_i$가 $\mathcal{I}$의 원소이면 $X \leftarrow X + e_i$를 대입한다.
- $X$는 maximum weight independent set이다.
정리 1의 증명.
1번 step을 거치고 나면 $S = \left\{e_1, …, e_n\right\}$ 에서 $w(e_1) \ge w(e_2) \ge … \ge w(e_n) > 0$ 이라 가정할 수 있다. 여기서 $e_1$을 포함하는 optimal solution(maximum weight independent set)이 항상 존재함을 보이면 $\mathcal{M}$의 $S-e_1$에 대한 restriction 역시 matroid이므로 수학적 귀납법에 의해 위의 greedy한 방법이 항상 optimal solution을 구한다는 것을 쉽게 보일 수 있다.
claim : $e_1$을 포함하는 maixmum weight independent set이 존재한다.
$I^*$이 maximum weight independent set 중 하나라고 하자. $e_1 \in I^*$인 경우, claim을 만족하였다. $e_1 \notin I^*$인 경우 $I^*+e_1$은 dependent하므로 circuit을 가진다. 성질 4에 의해 $I^* - e + e_1 \in \mathcal{I}$을 만족하는 $e \in I^*$가 존재하고, $w(e) \le w(e_1)$이므로 $I^* - e +e_1$은 $e_1$을 포함하는 maximum weight independent set이 된다. 따라서, claim을 증명하였다.
위의 알고리즘으로 해결할 수 있는 대표적인 문제로는 graph의 minimum weight spanning tree를 구하는 문제가 있다. 예시 2의 graphic matroid에서 알고리즘을 적용하기만 하면 된다. 이를 Kruskal’s algorithm이라 한다. Graphic matroid에서만 이 알고리즘이 성립하는 것은 아니기 때문에 1의 vector matroid에도 이를 적용할 수 있다. 실제 적용 예를 다음 장에서 다룰 것이다.
문제 풀이
다음과 같은 문제를 생각하자.
$N$개의 수로 이루어진 집합 $A = \left\{a_1, a_2, …, a_N\right\}$ 가 주어졌을 때 $S \subset A$를 골라 $S$의 어떤 공집합이 아닌 부분집합도 원소의 xor값이 0이 되지 않도록 하는 $S$ 중 원소의 합이 가장 큰 $S$를 구하여라.
각 $a_i$들은 이진법으로 나타내면 체 $GF(2)$ 에서 정의된 벡터로 볼 수 있고, $S$의 모든 공집합이 아닌 부분집합의 xor이 0이 아닌 것과 $S$의 각 벡터들이 independent한 것이 동치이므로 매트로이드를 정의할 수 있다. 따라서, 큰 수부터 추가하면서 조건이 유지되는 것만 확인해주면 된다. 원소를 추가했을 때 linearly independent한지 확인하는 것은 벡터공간의 basis를 유지하면서 새로 추가하고자 하는 vector가 이미 있는 vector들로 span되는지 확인해주면 충분하다.
실제 구현한 코드는 아래와 같다.
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, A[101000];
int Basis[32];
long long sum = 0;
bool Ins(int a) {
int i;
for (i = 30; i >= 0; i--) {
if ((a >> i) & 1) {
a ^= Basis[i];
if ((a >> i) & 1) {
Basis[i] = a;
return true;
}
}
}
return false;
}
int main() {
int i;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
sort(A + 1, A + n + 1);
vector<int>Res;
for (i = n; i >= 1; i--) {
if (Ins(A[i])) {
sum += A[i];
Res.push_back(A[i]);
}
}
printf("%d %lld\n", Res.size(), sum);
for (auto &t : Res)printf("%d ", t);
}
Codeforces Round #441 Div. 1 F. Royal Questions
이 문제는 weighted bipartite graph $G = (V,E)$, $V = V_1 + V_2$에서 $V_1$의 모든 vertex $v_1$에 대해 $v_1$의 차수가 2이고 연결된 두 edge의 weight가 같다는 조건을 만족할 때 $G$에서 maximum weighted matching을 구하는 문제이다. 언뜻 보면 이 문제는 weighted bipartite matching을 써야만 해결할 수 있는 문제로 보이지만, $N$ 제한이 20만으로 매우 크기 때문에 weighted bipartite matching을 해결하는 Hungarian method로는 시간 제한 안에 답을 구할 수 없다.
그러나 이 문제는 예시 2-1에서 다룬 graphic matroid의 변형으로 환원할 수 있다. 새로운 그래프 $G’ = (V_2, E’)$를 정의하자. $G$에서 $v_1$과 연결된 두 edge의 가중치가 $w$, 끝점이 각각 $u_1$과 $u_2$였다면 $G’$에서는 $u_1$과 $u_2$ 사이에 가중치 $w$인 간선을 잇는다. 만약 $G$에서 $M= \left\{e_1, e_2, …, e_K\right\}$ 가 matching을 이룬다면, 즉 $M$의 edge들의 양 끝점이 모두 서로 다르다면 $M$의 양 끝점 중 $V_1$에 포함되는 vertex들을 $M_1 = \left\{v_1, v_2, …, v_K\right\}$ 라 할 때 $M_1$에 포함되는 vertex들 각각에 대해 인접한 $V_2$의 vertex 두 개 중 하나를 잘 선택하면 서로 겹치지 않게 선택할 수 있다는 뜻이다. 이것은 $G’$에서 $M_1$에 의해 만들어지는 edge들만 놓고 보았을 때 edge들의 방향을 잘 주면 $G’$에서 각 vertex의 indegree가 1 이하가 되도록 할 수 있다는 것과 동치이다. 그리고 그것은 각 component에서 vertex의 개수가 edge의 개수보다 같거나 많아야 한다는 것과 동치임을 쉽게 알 수 있다.
따라서, $G$에서 maximum weighted matching을 구하는 문제는 $G’$에서 edge들을 잘 골라서 각 component의 vertex의 개수가 edge의 개수보다 적지 않도록 할 때, 선택된 edge들의 weight 합을 최대화하는 문제가 된다. $\mathcal{M} = (E’, \mathcal{I})$는 matroid이므로, 앞서 설명한 알고리즘으로 해결할 수 있다. 즉, $E’$에서 weight가 큰 edge부터 추가하면서 disjoint set union 자료구조로 서로소집합을 관리하면 각 component의 vertex 개수와 edge 개수를 저장할 수 있으므로 $O(M log M)$ 시간에 문제를 해결할 수 있다.
실제 구현한 코드는 아래와 같다.
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, SZ[201000], UF[201000];
long long res;
struct point {
int a, b, c;
bool operator <(const point &p)const {
return c < p.c;
}
}w[201000];
int Find(int a) {
if (a == UF[a])return a;
return UF[a] = Find(UF[a]);
}
int main() {
int i, a, b;
scanf("%d%d", &n, &m); // number of vertices in V2 and V1
for (i = 0; i < m; i++) {
scanf("%d%d%d", &w[i].a, &w[i].b, &w[i].c); // vertex i+1 in V1 is connected to vertex w[i].a and w[i].b with weight w[i].c
}
sort(w, w + m);
for (i = 1; i <= n; i++)UF[i] = i, SZ[i] = 1; // UF : union-find, SZ : (# of vertices) - (# of edges) in component
for (i = m - 1; i >= 0; i--) {
a = Find(w[i].a), b = Find(w[i].b);
if (SZ[a] + SZ[b] == 0)continue; // Add an edge when SZ >= 0 is satisfied after adding the edge
res += w[i].c;
if (a == b) {
SZ[a]--;
}
else {
UF[b] = a;
SZ[a] += SZ[b] - 1;
}
}
printf("%lld\n", res);
}
위 문제는 예시 2-1에서 소개된 변형된 graph matroid 말고도 Transversal matroid라고 볼 수도 있다.
$\mathcal{I} = \left\{ I : I \subset V_1, \exists \: a \: matching \: M \: in \: G \: that \: covers \: I \right\}$ 로 두면 $\mathcal{M} = (V_1, \mathcal{I})$는 matroid이고, 각 vertex의 weight는 연결된 두 edge의 weight으로 놓으면 된다. 하지만 각 vertex를 independent set에 추가할 수 있는지 빠르게 확인하기 위해서는 앞서 본 관찰을 하는 것이 필요하기 때문에 이것만으로는 빠른 시간에 문제를 해결하기 부족하다. 문제를 풀 때 matroid 구조를 찾기만 하면 해결되는 문제도 있지만 이처럼 그렇지 않은 경우 역시 존재한다.
Next article - matroid intersection
다음 편에는 같은 집합에서 정의된 두 매트로이드 $\mathcal{M}_1 = (S, \mathcal{I}_1)$, $\mathcal{M}_2 = (S, \mathcal{I}_2)$에서 모두 independent한 $S$의 부분집합 중 원소의 개수가 가장 많은 (maximum) 집합 또는 가중치가 가장 큰 집합을 구하는 matroid intersection 알고리즘에 대해 다룰 것이다. matroid intersection 알고리즘을 이용하면 다른 방법으로는 절대 풀리지 않을 것처럼 보이는 어려운 문제들도 해결할 수 있다.