imeimi / Algorithm DB

Matroid Union

1정의

M1 = (E, ℐ1), ⋯, Mk = (E, ℐk)에 대해 합성 매트로이드(union matroid) M1 ∨ ⋯ ∨ Mk = (E, ℐ)의 독립 집합은 다음과 같다.

I ∈ ℐ ⟺ ∃ 쌍마다 서로소인 I1, ⋯, Ik s.t. I = I1 ∪ ⋯ ∪ Ik이고 ∀ j: Ij ∈ ℐj.

2알고리즘

I = I1 ∪ ⋯ ∪ Ik를 관리한다. 교환 그래프 D(I)를 다음과 같이 정의한다.

D(I) = (E, { y → x | ∃j, y ∈ E\Ij, x ∈ Ij, (Ij\{x}) ∪ {y} ∈ ℐj })

T = { y ∈ E : ∃ j, y ∉ Ij, Ij ∪ {y} ∈ ℐj }로 정의한다. I = ∅에서 시작하여 다음을 반복한다.

D(I)에서 E\I로부터 T에 이르는 경로 y0 → x1 → ⋯ → xm (m ≥ 0)을 찾는다. 존재하지 않으면 종료한다. 각 간선 a → b에 대응하는 j에 대해 Ij ← (Ij\{b}) ∪ {a}로 순서대로 갱신하고, Il ∪ {xm} ∈ ℐl인 l에 대해 Il ← Il ∪ {xm}으로 갱신한다.

2.1보조 정리 1

I ∪ {y0} ∈ ℐ이다.

D(I)의 정의에 의해 Ij의 독립성이 유지되고, 경로 위의 모든 정점이 각 Ij에 최대 한 번 등장하므로 쌍마다 서로소가 유지된다. 최종 분해의 합집합은 I ∪ {y0}이다. ■

따름 정리: 알고리즘은 I ∈ ℐ를 유지한다.

2.2보조 정리 2

알고리즘이 끝나면 |I| = r(E)이다.

|J| > |I|인 J = J1 ∪ ⋯ ∪ Jk ∈ ℐ가 존재한다고 가정한다. R = D(I)에서 E\I로부터 도달 가능한 정점 집합이라 하자. E\I ⊆ R이고 R ∩ T = ∅이다.

모든 j에 대해 |Jj ∩ R| ≤ |Ij ∩ R|임을 보인다. Jj ∩ R, Ij ∩ R ∈ ℐj이고 |Jj ∩ R| > |Ij ∩ R|라 가정하면 (I3)에 의해 ∃y ∈ (Jj ∩ R)\Ij s.t. (Ij ∩ R) ∪ {y} ∈ ℐj이다.

  • Ij ∪ {y} ∈ ℐj: y ∉ Ij이므로 y ∈ T이고, y ∈ R이므로 R ∩ T = ∅에 모순이다.
  • Ij ∪ {y} ∉ ℐj: Ij ∪ {y}에는 y를 포함하는 회로 C가 존재한다. C ∩ (Ij\R) ≠ ∅이면 어떤 x ∈ C ∩ (Ij\R)에 대해 간선 y → x가 D(I)에 존재하고, y ∈ R이므로 x ∈ R이다. 이는 x ∈ Ij\R에 모순이다. 따라서 C{y} ⊆ Ij ∩ R이다. C는 회로이므로 y ∈ span(C{y}) ⊆ span(Ij ∩ R)이다. 그런데 (Ij ∩ R) ∪ {y} ∈ ℐj이므로 y ∉ span(Ij ∩ R)이다. 모순이다.

따라서 모든 j에 대해 |Jj ∩ R| ≤ |Ij ∩ R|이므로 |J ∩ R| ≤ |I ∩ R|이다. E\R ⊆ I이므로 J\R ⊆ I\R이고 |J\R| ≤ |I\R|이다. 따라서 |J| = |J ∩ R| + |J\R| ≤ |I ∩ R| + |I\R| = |I|이다. 이는 |J| > |I|에 모순이므로 |I| = r(E)이다. ■

3합성 정리

M1 ∨ ⋯ ∨ Mk는 매트로이드이며 랭크 함수는 r(A) = minX ⊆ A(|A\X| + ∑j rj(X))이다.

(I1)과 (I2)는 정의에서 자명하다.

3.1보조 정리 3

∀A ⊆ E, ∀X ⊆ A: r(A) ≤ |A\X| + ∑j rj(X).

I ∈ ℐ, I ⊆ A, I = I1 ∪ ⋯ ∪ Ik이면

|I| = |I\X| + |I ∩ X| ≤ |A\X| + ∑j |Ij ∩ X| ≤ |A\X| + ∑j rj(X). ■

3.2보조 정리 4

∀A ⊆ E, ∃X ⊆ A: |A\X| + ∑j rj(X) = r(A).

그라운드 집합을 A로 제한하여 알고리즘을 실행한다. 즉 Ij ⊆ A이고 D(I), T도 A의 원소만 사용한다. 보조 정리 2와 같은 논리로 알고리즘이 종료하면 |I| = r(A)이고, R = D(I)에서 A\I로부터 도달 가능한 정점 집합에 대해 R ∩ T = ∅이다.

임의의 y ∈ R\Ij를 잡자.

  • Ij ∪ {y} ∈ ℐj: y ∉ Ij이므로 y ∈ T이고, y ∈ R이므로 R ∩ T = ∅에 모순이다.
  • Ij ∪ {y} ∉ ℐj: y를 포함하는 회로 C ⊆ Ij ∪ {y}가 존재한다. C ∩ (Ij\R) ≠ ∅이면 어떤 x ∈ C ∩ (Ij\R)에 대해 간선 y → x가 D(I)에 존재하므로 y ∈ R에 의해 x ∈ R이다. 이는 x ∈ Ij\R에 모순이므로 C{y} ⊆ Ij ∩ R이다. C는 회로이므로 y ∈ span(C{y}) ⊆ span(Ij ∩ R)이다.

따라서 R의 모든 원소가 span(Ij ∩ R)에 속하므로 rj(R) ≤ rj(Ij ∩ R) = |Ij ∩ R|이다. Ij는 독립이므로 rj(R) ≥ |Ij ∩ R|이고, rj(R) = |Ij ∩ R|.

A\I ⊆ R이므로 A\R = I\R이다. X = R로 두면 |A\R| + ∑j rj(R) = |I\R| + ∑j |Ij ∩ R| = |I\R| + |I ∩ R| = |I| = r(A). ■

보조 정리 3, 4에 의해 r(A) = minX ⊆ A(|A\X| + ∑j rj(X)).

3.3교환 공리 (I3)

I, J ∈ ℐ이고 |I| < |J|이면 J ⊆ I ∪ J이므로 r(I ∪ J) ≥ |J| > |I|이다. 그라운드 집합을 I ∪ J로 제한하고 I를 시작점으로 알고리즘을 실행하면 |I| < r(I ∪ J)이므로 (I ∪ J)\I = J\I로부터 T에 이르는 경로가 존재한다. 보조 정리 1에 의해 경로의 시작점 y0 ∈ J\I에 대해 I ∪ {y0} ∈ ℐ이다. ■

따라서 M1 ∨ ⋯ ∨ Mk는 매트로이드이다.

4Nash-Williams 정리

G = (V, E)의 간선을 k개의 서로소 포레스트로 분해할 수 있다 ⟺ ∀∅ ≠ A ⊆ V: |E(A)| ≤ k(|A| − 1).

A ⊆ V에 대해 G[A]를 A로 유도된 부분 그래프, E(A)를 G[A]의 간선 집합, c(A)를 G[A]의 연결 컴포넌트 수라 하자. 그래픽 매트로이드의 랭크 함수에 의해 rM(G)(E(A)) = |A| − c(A)이다.

합성 정리에 의해 r(E) = minX ⊆ E(|E\X| + k · rM(G)(X))이므로, r(E) = |E|는 ∀ X ⊆ E: k · rM(G)(X) ≥ |X|와 동치이다.

(⇒) X = E(A) (∅ ≠ A ⊆ V)로 두면 k(|A| − c(A)) ≥ |E(A)|이다. c(A) ≥ 1이므로 |E(A)| ≤ k(|A| − 1).

(⇐) 임의의 X ⊆ E를 잡고 (V(X), X)의 연결 컴포넌트를 C1, ⋯, Cm이라 하면 rM(G)(X) = |V(X)| − m이다. 조건을 각 Ct에 적용하면 |X ∩ E(Ct)| ≤ |E(Ct)| ≤ k(|Ct| − 1)이므로

|X| = ∑t |X ∩ E(Ct)| ≤ k ∑t (|Ct| − 1) = k(|V(X)| − m) = k · rM(G)(X). ■