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} ∈ ℐ이다.

m = 0이면 y0 ∈ T이므로 자명하다. m ≥ 1이라 하자. 경로가 최단이므로 다음이 성립한다.

  • 중간 정점은 T에 없다: y0, x1, ⋯, xm−1 중 T에 속하는 정점이 있으면 경로를 거기서 끊어 더 짧은 경로를 얻는다.
  • 지름길 간선이 없다: 경로에서 두 칸 이상 앞으로 건너뛰는 간선이 D(I)에 존재하면 더 짧은 경로를 얻는다.

매트로이드 j를 고정하고, j에 대응하는 경로 간선을 경로 순서대로 (a1, b1), ⋯, (at, bt)라 하자. 갱신 후의 Ij는 Aj = (Ij\{b1, ⋯, bt}) ∪ {a1, ⋯, at}이다.

주장: Aj ∈ ℐj.

p < q인 간선 (ap, bq)는 지름길이므로 DMj(Ij)에 존재하지 않는다. 따라서 {a1, ⋯, at}와 {b1, ⋯, bt} 사이의 완전 매칭은 각 p를 q ≤ p로 보내는 순열로 제한되고, 그런 순열은 항등뿐이다. 즉 (ap, bp)는 DMj(Ij)에서 Ij △ Aj에 대한 유일한 완전 매칭이고, 매트로이드 교차의 보조 정리 2에 의해 Aj ∈ ℐj이다. □

마지막 갱신 Al ∪ {xm}도 독립이다. l에 대응하는 간선의 시작점 ai는 ai ∉ Il이고, xm이 아닌 경로 정점이라 T에 없으므로 Il ∪ {ai} ∉ ℐl, 즉 ai ∈ spanl(Il)이다. 따라서 Al ⊆ spanl(Il)이고 rl(Il ∪ Al) = rl(Il) = |Il| = |Al|이다. xm ∈ T에 의해 Il ∪ {xm} ∈ ℐl이고 |Il ∪ {xm}| > |Al|이므로, (I3)에 의해 Al ∪ {a} ∈ ℐl인 a ∈ (Il ∪ {xm})\Al이 존재한다. a ∈ Il이면 rl(Il ∪ Al) ≥ |Al| + 1이 되어 모순이므로 a = xm이고 Al ∪ {xm} ∈ ℐl이다.

경로가 단순하므로 각 bi는 자신이 속했던 유일한 Ij에서 빠지고 각 ai는 정확히 하나의 Ij에 더해진다 (연속한 두 간선의 매트로이드는 다르다: xi ∈ Iji인데 다음 간선은 xi ∉ Iji+1을 요구한다). 따라서 쌍마다 서로소가 유지되고, 최종 분해의 합집합은 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). ■

5참고 문헌

  • Nash-Williams, C. St. J. A. (1964). Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39(1), 12.
  • Edmonds, J. (1965). Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards Section B, 69B(1–2), 67–72.
  • Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer.