Matroid Theory 2 - Basis, Circuit

 

 

저번 글에서 매트로이드의 정의에 대해 알아보았습니다.

이번 글에선 본격적으로 매트로이드에서 정의될 수 있는 여러 가지 개념들을 알아보겠습니다.

저번 글에서 언급했듯이 모든 개념은 Linear Matroid 또는 Graphic Matroid 관점에서 예시를 들어 설명할 것이므로, 기초적인 선형대수학과 그래프이론 지식이 있으면 좋습니다.

Reminder

매트로이드 $M = (S, \mathcal{I}), \ \mathcal{I} \subseteq 2^S$ 는 다음 3가지 공리를 만족해야 합니다.

• [I1] $\phi \in \mathcal{I}$.
• [I2] Independent Set의 부분집합은 Independent Set이다.
  $\forall A \subseteq B \subseteq S$ then $B \in \mathcal{I} \Rightarrow A \in \mathcal{I}$
• [I3] 두 Independent Set $A,B \in \mathcal{I}$ 에 대해, $A$가 $B$보다 크다면, $A$에만 있는 어떤 원소 $x$를 뽑아, $B$에 추가하고도, $B$의 Independence를 유지할 수 있다.
  $\forall A,B \subseteq S, |A| > |B|$, then $\exists x \in A \setminus B, B\cup\{x\} \in \mathcal{I}$

기저 Basis

매트로이드의 Independent Set $A \subseteq S$중 Maximal한 경우를 "기저(Basis)"라고 합니다.

Independent Set이 Basis일 조건은

• $A$에 없는 모든 원소에 대해, 그 원소를 추가하면 Independence가 깨진다. 즉, 아무 원소 하나를 추가해도 Dependent Set이 된다.
  $A \in \mathcal{I}$ is basis if and only if $\forall x \in S \setminus A, A \cup \{x\} \notin \mathcal{I}$

Linear Matroid에서 Basis는 선형 대수학에서의 Basis 개념과 완전히 일치하며 (이름도 여기서 가져왔듯이), Graphic Matroid에서 Basis는 Spanning Tree와 일치합니다.

눈치가 좋은 사람은 벌써 유추했을 것 같은데, Basis의 가장 중요한 성질 중 하나로 모든 Basis의 크기는 같습니다.

• pf) 만약 두 Basis $B_1,B_2$가 $|B_1| > |B_2|$ 이면, 매트로이드 공리 [I3]에 의하여 $B_1 \setminus B_2$의 원소 중 하나를 $B_2$에 추가해 $B_2$의 Independence를 유지할 수 있다. 이는 $B_2$가 기저임에 모순이다.

선형대수학에서의 기저 정리와 유사하다는 것을 알 수 있습니다. 선형대수학에서 Vector Space의 차원(Dimension)이 정의되는 근본적인 이유중 하나이죠.

더 나아가, 어떤 Basis와 같은 크기를 가진 Independent Set은 항상 Basis이고, Basis가 아닌 Independent Set은 항상 원소 몇개를 추가해 Basis로 확장할 수 있습니다.

회로 Circuit

매트로이드의 Dependent Set $A \subseteq S$중 Minimal한 경우를 "회로(Circuit)"이라고 합니다.

Dependent Set이 Circuit일 조건은

• $A$의 모든 원소에 대해, 그 원소를 제거하면 Dependence가 깨진다. 즉, 아무 원소 하나를 제거해도 Independent Set이 된다.
  $A \notin \mathcal{I}$ is circuit if and only if $\forall x \in A, A \setminus \{x\} \in \mathcal{I}$

정의가 Basis의 정의와 매우 유사하다는 것을 알 수 있습니다.

Basis는 Linear Matroid의 경우에서 따온 이름이였습니다. 반면 Circuit은 이름에서부터 알 수 있듯이, Graphic Matroid의 경우에서 따온 이름입니다. 즉, Graphic Matroid에서 Circuit은 그래프 이론에서의 회로(Circuit, 또는 Cycle)와 완전히 일치합니다.

여기서 알 수 있는 점은, Basis와 달리 Circuit은 크기가 동일하지 않을 수 있다는 것입니다. (당장 그래프에서 다양한 길이의 Cycle이 있으므로)

당연하게도 모든 Dependent Set은 하나 또는 여러 개의 Circuit을 포함하고 있고, Circuit은 포함 관계일 수 없습니다.

어떤 Independent Set에 원소 하나를 추가하면, 최대 하나의 Circuit만 포함할 수 있습니다. Graphic Matroid 관점에서 생각하면 직관적입니다. 증명은 이 글 1페이지에 잘 되어있습니다 https://math.mit.edu/~goemans/18438F09/lec9.pdf