[알고리즘] 매트로이드

매트로이드(matroid)란 다음 성질을 만족하는 구조이다. 

 

$M =(X, I)$인 매트로이드 $M$이 존재한다고 하자.

1. $X$ 는 유한집합이다.

2. $I$는 $X$의 부분집합이면서 independent set이다. 공집합은 independent set이다.

3. $A, B$가 independent일 때 $|A| < |B|$이면 $x \in B-A$에 대해 $A \cup \{x\}$도 independent인 $x$가 존재한다.

 

위와 같은 성질을 만족하면 매트로이드라고 한다. 1번은 쉽게 이해할 수 있지만 2, 3번에 나오는 independent가 아직 와닿지 않는다. "어떤 규칙" 정도로 이해하고 넘어가자. 예를들어 $X = \{1, 2, 3, 4, 5\}$이고 $I$의 크기가 3보다 작은 집합이 indepnedent set이라고 하면 $I = \{1, 2\}$는 independent하고 $\{1, 2, 3\}$은 dependent하다고 한다.

 

용어

Ground set

매트로이드에서 집합 $X$를 ground set이라고 한다. 매트로이드에서 모든 independent set $I$는 ground set $X$의 부분집합이 된다.

 

Bases

Bases는 매트로이드에서 가장 큰 independent set이다. 위의 예시에서 $\varnothing, \{1\}, \{2\}, \{1, 2\}$가 모두 independent set인데 이 중 가장 큰 $\{1, 2\}$가 Bases가 된다. 이 예시는 유일하지만 매트로이드에서 Bases가 여러개인 경우가 있어서 복수형태로 사용하는 것 같다. 단수로는 Basis라고 표현한다. Basis는 다른 Basis의 부분집합이 될 수 없다. 크기가 같기 때문에 당연하다.

 

Circuit

어떤 dependent set에서 진부분집합이 모두 independent라면 그 dependent set을 circuit이라고 한다. $\{1, 2, 3\}$가 circuit중 하나가 된다. 집합 내 아무 수를 제거하면 independent가 되기 때문이다. circuit역시 다른 circuit의 부분집합이 될 수 없다. 이것도 정의를 생각하면 당연하다.

 

Rank

Rank는 Bases의 크기이다. 이를 따로 정의하는 이유는 사용할 때 편리한점이 많기 때문이다. 보통 집합 $S (\subset X)$의 rank를 $r(S)$같이 함수 형태로 나타내는 경우가 많다. 

rank의 성질을 알아보자.

1. $r(S) \le |S|$

2. $r(S) = |S|$, $S$는 independent set

3. $r(X)$는 matroid의 rank, $r(\varnothing) = 0$

4. $R \subset S \rightarrow r(R) \le r(S)$

5. $x \notin S$에서 $r(S) \le r(S \cup \{x\}) \le r(S) + 1$

 

Independence  Oracle

Independence oracle(이하 oracle)은 어떤 집합이 independence한지 확인하는 함수이다. 매트로이드의 성능(시간복잡도)는 이 함수의 호출 횟수에 따라 결정된다. 위의 예시에서 oracle은 집합의 모든 원소를 돌면서 각 원소가 3보다 작은지 확인하면 되므로 $O(|S|)$만큼의 호출을 하게 된다.

 

기본적인 용어는 어느정도 됐고 매트로이드가 되려면 ground set과 independent 조건을 정의한 후 매트로이드의 성질을 만족하는지 확인하면 된다. 이제 매트로이드의 예시를 보자.

 

매트로이드 종류

Uniform Matroid

$X$는 모든 유한집합이 될 수 있고 $S \in X$에서 $|S| \le k$일때 independent라고 한다. 여기서 $k$는 미리 정한 상수이다. (위에서 말한 예시가 uniform matroid이다.)

즉, $X = \{1, 2, 3, 4, 5\}$이고 $k = 3$이면 $\{1, 2\}$는 independent하고 $\{1, 3, 4, 5\}$는 dependent하다.

우리가 접한 첫 매트로이드이므로 자세히 관찰해보자. 일단 매트로이드의 성질을 만족하는가?

1. $X$는 유한집합이다.

2. independent set인 $S$는 $|S| \le k \le |X|$이다. $|\varnothing| = 0 \le k$이므로 공집합도 independent하다.

3. $A = \{1, 2\}, B = \{1, 3, 4\}$일 때 $3 \in B-A$를 $A$에 추가해도 $\{1, 2, 3\}$이므로 independent를 유지한다.

위 세 조건을 만족하므로 uniform matroid는 매트로이드이다.

 

Bases는 $|S|=k$인 $X$의 모든 부분집합 될 수 있다. $\{1, 2, 3\}, \{1, 2, 4\}, ...$가 그 예시이다.

Circuit은 $|S|=k+1$인 $X$의 모든 부분집합이 될 수 있다. $\{1, 2, 3, 4\}, ...$가 그 예시이다.

Rank $r(X) = 3$이다.

Oracle은 집합의 크기가 $k$보다 작거나 같은지 확인하는 함수이다.

 

Linear Algebra Matroid

$X$는 모든 벡터가 될 수 있고 $S$가 linearly independent하다면 independent라고 한다.

실제로 선형대수학에서 사용되는 많은 용어들(basis, rank, independent...)이 매트로이드에서 사용되고 있다. 매트로이드가 선형대수학에서 기인했을 수 있다고 한다.

Linear Algebra Matroid에서 basis, rank, independent는 선형대수학에서 사용되는 의미를 그대로 갖는다.

 

Colorful Matroid

$X$는 colored element들의 집합이다. 각 element는 하나의 color가 있고 $S$에서 같은 color를 가지는 element가 없으면 independent라고 한다.

$r(X)$는 서로 다른 색의 개수 이고 Bases는 모든 색을 하나씩 포함한 집합이 된다.

 

Graphic Matroid

$X$는 간선집합, cycle이 없으면 independent라고 한다.

이게 실제로 무의식중에 많이 사용하던 건데 우리가 최소신장트리를 구할 때 kruskal 알고리즘을 많이 사용했을 것이다. 해당 알고리즘을 추상화 한게 Graphic matroid이다.

Bases는 spanning tree가 되고 Circuit은 단순 루프가 된다. 또한 Bases가 트리이므로 rank는 $n-1$이 된다. ($n$은 정점 개수) oracle은 루프가 있는지 확인하는 작업이므로 dfs, bfs, dsu등이 될 수 있다.

 

매트로이드의 여러 예시들을 확인했는데 이런 구조가 어떻게 쓰일 수 있을까?

Rado-Edmond Algorithm

Rado-Edmond Algorithm은 주어진 matroid에서 bases를 찾는 알고리즘이다. Graphic Matroid에서 kruskal을 사용하여 spanning tree를 찾던 그 작업이라고 보면 되는데 해당 과정과 비교하면서 보면 재밌을 것이다.

알고리즘은 간단하다.

1. $S = \varnothing$에서 시작한다.

2. $X$의 각 원소를 돌면서 $S \cup \{x\}$가 independent한지 확인한다. ($x \in X$)

3. independent하다면 $S := S \cup \{x\}$한다.

4. 위 작업을 모든 $X$의 원소에 대해 수행하면 $S$는 bases중 하나가 된다.

 

2번 작업에서 independent를 확인하기 위해 oracle을 사용한다. 즉 oracle이 총 $n$번 호출된다. ($n = |X|$)

크루스칼 알고리즘과 정말 비슷하지 않나요?

그런데 각 원소에 weight가 있는 경우는 어떻게 할까? 그리고 bases중 weight의 합이 최소/최대인 basis를 찾으려면 어떻게 할까?

 

Minimum weighted bases

예를 들어 Graphic Matroid에서 edge가 있는데 weight를 가지고 있어 bases중 합이 최소인 basis를 찾으라는 문제가 있으면 어떻게 해결할 것인가? 우리는 이미 답을 알고 있다. 간선을 weight로 정렬한 후 위의 Rado-Edmond Algorithm을 수행하면 되고 이는 Kruskal Algorithm이랑 정확히 일치한다.

실제로 Graphic Matroid외에 다른 matroid도 matroid구조만 이룬다면 weight로 정렬한 후 Rado-Edmond Algorithm을 수행하면된다. 이는 그리디한 선택을 사용하는 전략이 되므로 Matroid로 해결하는 문제는 Greedy한 문제가 된다.

 

그런데 위 전략을 사용하는게 어떻게 정당하다고 할 수 있죠? 

매트로이드의 3번 성질을 사용하면 정당성을 증명할 수 있다.

minimum weighted bases를 구하는 과정 중 어떤 minimum weighted independent set $A, B$가 있다고 하자. $|A| = k, |B| = k+1$이다. 3번 성질에 의해 $y \in B-A$이고 $A' = A \cup \{y\}$를 하면 $|A'| = k+1 = |B|$가 된다.

$|B|$는 크기가 $k+1$인 집합 중 minimum weighted이므로 $w(B) \le w(A \cup \{y\})$가 된다.

또한 $A$는 크기가 $k$인 집합 중 minimum weighted이므로 $w(A) \le w(B - \{y\})$가 된다. 여기에 양변에 $\{y\}$를 추가하면 $w(A \cup \{y\}) \le w(B)$가 된다.

위 두 부등식을 합치면 $w(B) \le w(A \cup \{y\}) \le w(B)$가 되므로 크기가 $k$인 minimum weighted independent set에서 원소를 하나 추가하여 크기가 $k+1$인 minimum weighted independent set을 만들 수 있다.

$k = 0$일때는 $w(\varnothing) = 0$이므로 자명하다. 최종적으로 $k = r(X)$일때까지 반복하면 minimum weighted basis를 얻을 수 있게 된다. 따라서 위 전략은 정당하다. $\Box$

 

Rado-Edmond Algorithm의 시간복잡도는 $O(N(\log N + T))$이다. $N$은 $|X|$이고 $T$는 oracle의 시간복잡도이다. 로그는 정렬때문에 붙게 된다.

 

Super Thanks

https://codeforces.com/blog/entry/69287

Introduction to algorithm (a.k.a. CLRS)