Matroid

최종 수정:

1정의

매트로이드(matroid) M = (E, ℐ)는 유한 지반 집합(ground set) E와 ℐ ⊆ 2E로 이루어지며, ℐ의 원소를 독립 집합이라 한다. ℐ는 다음 세 공리를 만족한다.

  • (I1) ∅ ∈ ℐ.
  • (I2) I ∈ ℐ이고 J ⊆ I이면 J ∈ ℐ. (유전성)
  • (I3) I, J ∈ ℐ이고 |I| < |J|이면 ∃x ∈ J\I s.t. I ∪ {x} ∈ ℐ. (확장 공리)

ℐ에 속하지 않는 집합을 종속 집합이라 한다.

2예시

2.1그래프 매트로이드

그래프 G = (V, E)에서 E를 지반 집합으로 놓고 ℐ = { F ⊆ E : F는 비순환 }으로 정의한다. 이 매트로이드 M(G)를 G의 그래프 매트로이드(graphic matroid)라 한다.

(I1)과 (I2)는 자명하다. (I3): F, F' ∈ ℐ이고 |F| < |F'|이다. 비순환 부분 그래프의 연결 컴포넌트 수는 |V| − |간선 수|이므로, F의 컴포넌트 수가 F'보다 많다. 따라서 F'에서는 같은 컴포넌트에 속하지만 F에서는 다른 컴포넌트에 속하는 두 정점 u, v가 존재한다. F'의 u–v 경로 위에서 F에 없는 간선 e를 고르자. F ∪ {e}에 사이클이 생기면 u, v가 F에서 연결되어 모순이므로 F ∪ {e} ∈ ℐ이다. ■

2.2선형 매트로이드

체 𝔽 위의 벡터 집합 E를 지반 집합으로 놓고 ℐ = { S ⊆ E : S는 선형 독립 }으로 정의한다. 이를 선형 매트로이드(linear matroid)라 한다.

(I1)과 (I2)는 자명하다. (I3): S, T ∈ ℐ이고 |S| < |T|이다. ∀v ∈ T\S에 대해 S ∪ {v} ∉ ℐ라 가정하면 T\S의 모든 벡터가 span(S)에 속한다. S ⊆ span(S)이므로 T ⊆ span(S)이고, T의 선형 독립성에 의해 |T| ≤ dim span(S) = |S|이다. 이는 모순이므로 ∃v ∈ T\S s.t. S ∪ {v} ∈ ℐ이다. ■

2.3균일 매트로이드

E = {1, ⋯, n}이고 ℐ = { S ⊆ E : |S| ≤ k }로 정의한 매트로이드를 균일 매트로이드(uniform matroid) Uk,n이라 한다.

(I1), (I2)는 자명하다. (I3): |S| < |T| ≤ k이면 |S ∪ {x}| = |S| + 1 ≤ k인 x ∈ T\S가 존재한다. ■

3베이스

베이스(base)는 극대 독립 집합이다.

3.1베이스 크기 정리

M의 모든 베이스의 크기는 같다.

B1, B2가 베이스이고 |B1| < |B2|라 하자. (I3)에 의해 ∃x ∈ B2\B1 s.t. B1 ∪ {x} ∈ ℐ인데, 이는 B1의 극대성에 모순이다. B1과 B2를 교환하면 |B1| = |B2|이다. ■

베이스와 크기가 같은 독립 집합은 모두 베이스이다. 모든 베이스의 공통 크기를 M의 랭크라 한다.

3.2보조 정리 1 (베이스 교환)

B1, B2가 베이스이고 x ∈ B1\B2이면 ∃y ∈ B2\B1 s.t. (B1\{x}) ∪ {y}도 베이스이다.

|B1\{x}| = |B1| − 1 < |B2|이므로 (I3)에 의해 ∃y ∈ B2\(B1\{x}) s.t. (B1\{x}) ∪ {y} ∈ ℐ이다. x ∉ B2이고 y ∈ B2이므로 y ≠ x, 따라서 y ∈ B2\B1이다. (B1\{x}) ∪ {y}는 크기 |B1|의 독립 집합이므로 베이스이다. ■

4회로

회로(circuit)는 극소 종속 집합이다. 즉, C ∉ ℐ이고 ∀C' ⊊ C: C' ∈ ℐ인 집합 C이다.

집합이 독립이면 회로를 포함하지 않고, 종속이면 회로를 포함한다.

4.1보조 정리 2 (회로 소거)

C1 ≠ C2가 회로이고 e ∈ C1 ∩ C2이면, D = (C1 ∪ C2)\{e}는 종속이다.

D ∈ ℐ라 가정하자. I = C1 ∩ C2로 두면, 두 회로는 서로를 포함할 수 없으므로 I ⊊ C1이고 I ∈ ℐ이다. C1 ⊄ C2이고 C2 ⊄ C1이므로 |D| = |C1 ∪ C2| − 1 ≥ |C1 ∩ C2| + 1 > |I|이다.

I, D ∈ ℐ이고 |I| < |D|이므로 (I3)을 반복 적용하여 I에 D\I의 원소들을 추가한 크기 |D|의 독립 집합 I'을 얻는다. I ⊆ C1 ∪ C2이고 추가한 원소들이 D ⊆ (C1 ∪ C2)\{e}에서 오며 e ∈ I ⊆ I'이므로 I' ⊆ C1 ∪ C2이다.

C1 ∩ C2 = I ⊆ I'이고 |I'| = |C1 ∪ C2| − 1이므로 I' = (C1 ∪ C2)\{y}인 y가 존재한다. y ∉ C1 ∩ C2이므로 y ∈ C1\C2 또는 y ∈ C2\C1이다. 일반성을 잃지 않고 y ∈ C1\C2라 하면 C2 ⊆ I'인데, C2 ∉ ℐ이고 I' ∈ ℐ이므로 (I2)에 모순이다. ■

4.2보조 정리 3 (기본 회로)

A ∈ ℐ이고 a ∉ A일 때 A ∪ {a} ∉ ℐ이면, A ∪ {a}에 포함되는 회로 B가 유일하게 존재하고 ∀b ∈ B: (A ∪ {a})\{b} ∈ ℐ이다.

A ∈ ℐ이므로 A ∪ {a}의 회로 B는 a를 포함한다. 또 다른 회로 C ⊆ A ∪ {a} (C ≠ B)가 존재한다면 마찬가지로 a ∈ C이다. 회로 소거에 의해 (B ∪ C)\{a}는 종속이다. 그런데 (B ∪ C)\{a} ⊆ A이므로 A ∈ ℐ에 모순이다. 따라서 B는 유일하다.

b ∈ B에 대해 B ⊄ (A ∪ {a})\{b}이므로, A ∪ {a}의 유일한 회로가 B인 것에 의해 (A ∪ {a})\{b} ∈ ℐ이다. ■

5탐욕 알고리즘

w: E → ℝ를 가중치 함수라 하고 W(X) = ∑x ∈ X w(x)로 정의한다.

  1. E의 원소를 w(e1) ≥ w(e2) ≥ ⋯ ≥ w(en)이 되도록 정렬한다.
  2. R = ∅으로 초기화한다.
  3. i = 1부터 n까지: w(ei) > 0이고 R ∪ {ei} ∈ ℐ이면 R에 ei를 추가한다.

5.1탐욕 정리

위 알고리즘이 구한 R은 W(R)이 최대인 독립 집합이다.

w(e) ≤ 0인 원소는 없다고 가정한다. Rk를 ek까지 처리한 후의 R로 두자 (R0 = ∅).

∀0 ≤ k ≤ n에 대해 Rk ⊆ Ak이고 Ak\Rk ⊆ {ek+1, ⋯, en}인 최대 W 베이스 Ak가 존재함을 귀납법을 사용한다.

기저 (k = 0): W(X)가 최대인 X ∈ ℐ를 A0으로 둔다. 양의 가중치만 있으므로 A0은 베이스이다.

귀납 (k ≥ 1): 귀납 가설에 의해 Ak−1이 존재한다.

  • Rk−1 ∪ {ek} ∉ ℐ (ek를 추가하지 않는 경우): ek ∈ Ak−1이면 Rk−1 ∪ {ek} ⊆ Ak−1 ∈ ℐ이므로 모순. 따라서 ek ∉ Ak−1이고 Ak = Ak−1이 성립한다.

  • Rk−1 ∪ {ek} ∈ ℐ, ek ∈ Ak−1: Ak = Ak−1이 성립한다.

  • Rk−1 ∪ {ek} ∈ ℐ, ek ∉ Ak−1: Rk ∈ ℐ이고 |Rk| ≤ |Ak−1|이므로 (I3)을 반복 적용하여 Rk에 Ak−1의 원소들을 추가해 베이스 B를 만든다. Rk−1 ⊆ Ak−1이고 ek ∉ Ak−1이므로 B\Ak−1 = {ek}이다. 베이스 크기가 같으므로 Ak−1\B = {el}이고, Ak−1\Rk ⊆ {ek+1, ⋯, en}이므로 l ≥ k + 1이고 w(el) ≤ w(ek)이다. 따라서 W(B) = W(Ak−1) + w(ek) − w(el) ≥ W(Ak−1)이고, Ak−1이 최대이므로 W(B) = W(Ak−1)이다. Ak = B로 두면 성립한다.

Rn ⊆ An이고 An\Rn = ∅이므로 Rn = An이고, Rn은 최적이다. ■

5.2명제 1 (유전성의 필요성)

(I2)를 만족하지 않는 M = (E, ℐ)에는 위 알고리즘이 최적을 찾지 못하게 하는 w가 존재한다.

∃A ⊊ B, B ∈ ℐ, A ∉ ℐ인 A, B를 잡자. w(x) = 2 (x ∈ A), 1 (x ∈ B\A), 0 (otherwise)로 정의한다. A ∉ ℐ이므로 알고리즘은 A의 원소를 모두 선택할 수 없고, A에서 최대 |A| − 1개를 선택한다. 따라서 총 가중치는 2(|A| − 1) + (|B| − |A|) = |A| + |B| − 2 이하이다. 그러나 W(B) = |A| + |B|이므로 최적을 놓친다. ■

5.3명제 2 (확장 공리의 필요성)

(I3)을 만족하지 않는 M = (E, ℐ)에는 위 알고리즘이 최적을 찾지 못하게 하는 w가 존재한다.

∃A, B ∈ ℐ, |A| < |B|이고 ∀a ∈ B\A: A ∪ {a} ∉ ℐ인 A, B를 잡자. w(x) = 1 + 1/(2|A|+1) (x ∈ A), 1 (x ∈ B\A), 0 (otherwise)로 정의한다. A ∈ ℐ이므로 알고리즘은 A를 모두 선택하고, A ∪ {a} ∉ ℐ이므로 B\A의 원소는 하나도 추가하지 못한다. 총 가중치는 |A|(1 + 1/(2|A|+1)) < |A| + 1/2이다. 그러나 W(B) ≥ |B| ≥ |A| + 1이므로 최적을 놓친다. ■

6스팬

랭크 함수 r: 2E → ℤ를 r(A) = max{ |I| : I ⊆ A, I ∈ ℐ }로 정의한다.

6.1보조 정리 4 (단조성)

A ⊆ B ⇒ r(A) ≤ r(B).

A의 극대 독립 집합은 B에도 포함되므로 r(A) ≤ r(B)이다. ■

6.2준모듈성 정리

r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).

A ∩ B의 극대 독립 집합 I1을 잡는다. I1 ⊆ I인 A ∪ B의 극대 독립 집합 I를 만들고 I2 = I ∩ (A\B), I3 = I ∩ (B\A), I4 = I ∩ (A ∩ B)로 정의하면 r(A ∪ B) = |I| = |I2| + |I3| + |I4|이다. I1 ⊆ I4이고 I4 ⊆ A ∩ B이며 I4 ∈ ℐ이므로 I1의 극대성에 의해 I1 = I4이다.

I1 ∪ I2 ⊆ A이고 I1 ∪ I2 ∈ ℐ이므로 |I1| + |I2| ≤ r(A)이다. 마찬가지로 |I1| + |I3| ≤ r(B)이다. 두 부등식을 더하면

r(A) + r(B) ≥ 2|I1| + |I2| + |I3| = |I| + |I1| = r(A ∪ B) + r(A ∩ B)이다. ■

A ⊆ E에 대해 M에서 A의 스팬(span)을 span(A) = { a ∈ E : r(A ∪ {a}) = r(A) }로 정의한다.

6.3보조 정리 5

A ⊆ B ⇒ span(A) ⊆ span(B).

a ∈ span(A)이면 r(A ∪ {a}) = r(A)이다. a ∈ B이면 r(B ∪ {a}) = r(B)이므로 a ∈ span(B)이다. a ∉ B이면 준모듈성에 의해

r(A ∪ {a}) + r(B) ≥ r(B ∪ {a}) + r(A)

이므로 r(B) ≥ r(B ∪ {a})이다. 단조성에 의해 r(B) = r(B ∪ {a})이고 a ∈ span(B)이다. ■

6.4보조 정리 6

a ∈ span(A) ⇒ span(A ∪ {a}) = span(A).

단조성에 의해 span(A) ⊆ span(A ∪ {a})이다. b ∈ span(A ∪ {a})를 잡자. 준모듈성에 의해

r(A ∪ {a}) + r(A ∪ {b}) ≥ r(A ∪ {a, b}) + r(A)

이다. a ∈ span(A)이므로 r(A ∪ {a}) = r(A)이고, 부등식은 r(A ∪ {b}) ≥ r(A ∪ {a, b})가 된다. 단조성에 의해 r(A ∪ {b}) = r(A ∪ {a, b})이다. b ∈ span(A ∪ {a})이므로 r(A ∪ {a, b}) = r(A ∪ {a}) = r(A)이고, 따라서 r(A ∪ {b}) = r(A)이므로 b ∈ span(A)이다. ■

따름 정리: span(span(A)) = span(A).

span(A) = {a1, ⋯, am}으로 두면 보조 정리 6을 반복 적용하여 span(A) = span(A ∪ {a1}) = ⋯ = span(span(A))이다.

6.5강한 베이스 교환 정리

B1 ≠ B2가 베이스이고 x ∈ B1\B2이면 ∃y ∈ B2\B1 s.t. (B1\{x}) ∪ {y}와 (B2\{y}) ∪ {x}가 모두 베이스이다.

B2 ∪ {x}는 종속이므로 보조 정리 3에 의해 B2 ∪ {x}에 포함되는 유일한 회로 C가 존재하고 x ∈ C이다. x ∈ span(C\{x})이므로 보조 정리 5에 의해 x ∈ span((B1 ∪ C)\{x})이다. 보조 정리 6에 의해 span((B1 ∪ C)\{x}) = span(B1 ∪ C) ⊇ span(B1) = E이다. 따라서 (B1 ∪ C)\{x}는 어떤 베이스 B3을 포함한다.

|B1\{x}| + 1 = |B3|이므로 (I3)에 의해 ∃y ∈ B3\(B1\{x}) s.t. (B1\{x}) ∪ {y}가 베이스이다. B3\(B1\{x}) ⊆ ((B1 ∪ C)\{x})\(B1\{x}) = (C\{x})\B1 ⊆ B2\B1이므로 y ∈ B2\B1이다.

보조 정리 3에 의해 (B2 ∪ {x})\{y} = (B2\{y}) ∪ {x}도 베이스이다. ■

7참고 문헌

  • Whitney, H. (1935). On the abstract properties of linear dependence. American Journal of Mathematics, 57(3), 509–533.
  • Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1(1), 127–136.
  • Oxley, J. (2011). Matroid Theory (2nd ed.). Oxford University Press.