매트로이드

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

매트로이드는 다양한 방식으로 정의될 수 있는 수학적 구조로, 주로 유한 집합과 그 부분 집합족으로 구성된다. 매트로이드는 독립 집합, 기저, 회로, 랭크 함수 등을 통해 정의될 수 있으며, 이들은 서로 동치 관계에 있다. 매트로이드는 (A1), (A2), (A3) 공리를 만족하는 독립성 시스템의 특수한 경우로, 독립성 시스템은 매트로이드보다 일반적인 개념이다. 매트로이드에는 쌍대 매트로이드, 부분 매트로이드, 직합, 마이너 등의 연산이 존재하며, 유한 매트로이드, 유한형 매트로이드, 유순 매트로이드 등 다양한 종류가 있다. 균등 매트로이드, 선형 매트로이드, 그래프의 순환 매트로이드 등이 매트로이드의 예시이며, 조합 최적화 문제, 특히 최대 가중치 독립 집합을 찾는 문제에 탐욕 알고리즘을 적용할 수 있다는 점에서 응용 가치가 높다. 매트로이드 개념은 1935년 해슬러 휘트니에 의해 처음 도입되었으며, 윌리엄 토머스 텃, 리처드 라도 등에 의해 발전되었다.

더 읽어볼만한 페이지

폐포 연산자 - 완비 격자
완비 격자는 모든 부분 집합이 상한과 하한을 갖는 부분 순서 집합으로, 격자 이론에서 중요한 개념이며 다양한 수학 분야에서 활용된다.
폐포 연산자 - 내부 (위상수학)
내부는 위상 공간의 부분 집합 S에 대해 S에 포함된 가장 큰 열린 집합으로 정의되며, 멱등성을 가지고 폐포와 쌍대적인 개념이다.
매트로이드 이론 - 매트로이드 마이너
매트로이드 마이너는 매트로이드에서 부분집합 제거 또는 제한 연산을 반복하여 얻어지는 매트로이드로, 매트로이드의 성질 보존, 구조 분석, 그래프 이론과의 연결, 여러 종류의 매트로이드, 구조 파악 및 복잡성 분석, 효율적인 테스트 알고리즘 개발 등에 활용된다.
매트로이드 이론 - 탐욕 알고리즘
탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘 설계 패러다임으로, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 최적의 해를 보장하며, 다익스트라, 프림, 크루스칼 알고리즘 등에 사용된다.
집합족 - 가측 공간
가측 공간은 집합과 그의 멱집합의 부분 시그마 대수로 이루어진 순서쌍으로, 시그마 대수는 여집합과 가산 합집합에 대해 닫혀 있는 성질을 가지며, 가측 공간과 가측 함수는 구체적 범주를 이룬다.
집합족 - 집합의 분할
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것이며, 동치 관계와 밀접하게 관련되어 있고, 벨 수로 표현되며, 플레잉 카드를 나누는 것과 같은 예시가 있다.

매트로이드
정의
설명	유한 집합의 부분 집합족에 공리적으로 구조를 부여하여, 선형대수학에서의 선형 독립의 일반화, 그래프 이론에서의 연결성, 조합 최적화에서의 다양한 개념들을 추상화한 것임
역사
창시자	해슬러 휘트니 (1935년)
동기	행렬의 독립성에 대한 대수적 개념과 그래프의 독립성에 대한 그래프 이론적 개념 사이의 유사성을 파악
정의 방법
독립 집합족에 의한 정의	유한 집합 E와 E의 부분 집합족 I의 순서쌍 M=(E, I) I의 각 원소를 M의 독립 집합이라고 하며, 다음 공리들을 만족해야 함 공집합은 항상 독립 집합임: ∅ ∈ I 독립 집합의 부분 집합은 독립 집합임: X ⊆ Y ∈ I 이면 X ∈ I 독립 집합 X와 Y에 대해, \|X\| < \|Y\|이면, X ∪ {z} ∈ I인 z ∈ Y X가 존재함
기저족에 의한 정의	유한 집합 E와 E의 부분 집합족 B의 순서쌍 M=(E, B) B의 각 원소를 M의 기저라고 하며, 다음 공리들을 만족해야 함 B는 공집합이 아님: B ≠ ∅ 기저 교환 공리: B1, B2 ∈ B이고 x ∈ B1 B2이면, y ∈ B2 B1가 존재하여 (B1 {x}) ∪ {y} ∈ B
회로족에 의한 정의	유한 집합 E와 E의 부분 집합족 C의 순서쌍 M=(E, C) C의 각 원소를 M의 회로라고 하며, 다음 공리들을 만족해야 함 공집합은 회로가 아님: ∅ ∉ C 회로가 다른 회로를 포함하지 않음: C1, C2 ∈ C이고 C1 ⊆ C2이면 C1 = C2
랭크 함수에 의한 정의	유한 집합 E와 함수 r: P(E) → ℤ의 순서쌍 M=(E, r) r을 M의 랭크 함수라고 하며, 다음 공리들을 만족해야 함 부분 집합의 랭크는 그 크기를 초과할 수 없음: X ⊆ E이면 0 ≤ r(X) ≤ \|X\| 랭크 함수는 단조 증가함: X ⊆ Y ⊆ E이면 r(X) ≤ r(Y) 랭크 함수는 준모듈러 부등식을 만족함: X, Y ⊆ E이면 r(X ∪ Y) + r(X ∩ Y) ≤ r(X) + r(Y)
폐포 연산자에 의한 정의	유한 집합 E와 함수 cl: P(E) → P(E)의 순서쌍 M=(E, cl) cl을 M의 폐포 연산자라고 하며, 다음 공리들을 만족해야 함 X ⊆ E이면 X ⊆ cl(X) X ⊆ Y ⊆ E이면 cl(X) ⊆ cl(Y) X ⊆ E이면 cl(cl(X)) = cl(X) X ⊆ E이고 x, y ∈ E에 대해, y ∉ cl(X)이고 y ∈ cl(X ∪ {x})이면 x ∈ cl(X ∪ {y})
플랫족에 의한 정의	유한 집합 E와 E의 부분 집합족 F의 순서쌍 M=(E, F) F의 각 원소를 M의 플랫이라고 하며, 다음 공리들을 만족해야 함 E ∈ F F1, F2 ∈ F이면 F1 ∩ F2 ∈ F F ∈ F이고 x ∉ F이면, F ⊆ F'인 F' ∈ F가 존재하고, x ∈ F'이며, F'은 F ∪ {x}를 포함하는 F의 최소 플랫임
투표 게임에 의한 정의	유한 집합 E와 가중치 함수 w: P(E) → ℝ의 순서쌍 M=(E, w) w를 투표 게임이라고 하며, 다음 조건을 만족해야 함 S ⊆ T이면 w(S) ≤ w(T) w(S) + w(T) ≤ w(S ∪ T) + w(S ∩ T)
예시
행렬 마트로이드	행렬 A의 열들의 집합 E에서 선형 독립인 열들의 집합 I를 독립 집합족으로 정의 M = (E, I)는 마트로이드임
그래프 마트로이드	그래프 G = (V, E)의 변들의 집합 E에서 사이클을 포함하지 않는 변들의 집합 I를 독립 집합족으로 정의 M = (E, I)는 마트로이드임
균등 마트로이드	유한 집합 E의 크기가 k 이하인 부분 집합족 I를 독립 집합족으로 정의 M = (E, I)는 마트로이드임 표기: Uk,n (E의 크기가 n일 때)
파티션 마트로이드	유한 집합 E를 E1, E2, ..., Em으로 분할하고, 각 Ei에서 최대 ki개의 원소를 선택하는 부분 집합족 I를 독립 집합족으로 정의 M = (E, I)는 마트로이드임
가로 마트로이드	행렬 M의 각 행에서 최대 하나의 원소를 선택하여 얻을 수 있는 열들의 집합 I를 독립 집합족으로 정의 M = (E, I)는 마트로이드임
응용
선형대수학	선형 독립성
그래프 이론	연결성, 최소 신장 트리
조합 최적화	다양한 최적화 문제 해결
네트워크 코딩	정보 흐름 최적화
관련 개념
그리디 알고리즘	마트로이드에서 최적의 독립 집합을 찾는 데 사용될 수 있음
튜크의 보조정리	마트로이드의 기저 존재성을 증명하는 데 사용될 수 있음

2. 정의

'''매트로이드'''는 여러 가지 방법으로 정의될 수 있으며, 이 정의들은 서로 동치이다.

정의	독립 집합 $I$	종속 집합 $D$	기저 $B$	회로 $C$	닫힌집합 $F$
독립 집합을 통한 정의	—	독립 집합이 아닌 집합	극대 독립 집합	극소 종속 집합	임의의 $F\supseteq I\in\mathcal I$ 및 $x\in E$ 에 대하여, $I\cup\{x\}\in\mathcal I\implies x\in F$
기저를 통한 정의	$\exists B\in\mathcal B\colon I\subseteq B$	$\forall B\in\mathcal B\colon D\not\subseteq B$	—	모든 진부분 집합이 기저이지만, 기저가 아닌 집합
회로를 통한 정의	$\forall C\in\mathcal C\colon C\not\subseteq I$	$\exists C\in\mathcal C\colon C\subseteq D$	회로를 포함하지 않는 극대 집합	—
계수를 통한 정의	\forall x\in I\colon\operatorname{rank}(I>I\setminus\{x\})>0	\exists x\in D\colon\operatorname{rank}(D>D\setminus\{x\})=0	극대 독립 집합	극소 종속 집합	x\in E에 대하여 $x\in F\iff \operatorname{rank}(E\cup\{x\}>E)=0$
폐포를 통한 정의	$\forall x\in I\colon x\not\in\operatorname{cl}(I\setminus\{x\})$	$\exists x\in D\colon x\in\operatorname{cl}(D\setminus\{x\})$	독립 집합이며, 고정점을 갖지 않는, $\forall x\in B\colon f(x)\in \operatorname{cl}(I\setminus\{x,f(x)\})$ 인 함수 $f\colon B\to B$ 가 존재	종속 집합이며, 임의의 $x,y\in C$ 에 대하여 $y\in\operatorname{cl}(C\setminus\{x,y\})\implies x=y$	$F=\operatorname{cl}F$

매트로이드 $(E,\mathcal I)$ 의 부분 집합 $S$ 의 폐포 $\operatorname{cl}(S)$ 는 독립 집합 또는 상대 계수 함수를 통해 정의할 수 있다.

독립 집합을 통한 정의:

:

\operatorname{cl}(S) = S \cup \{x\in E\colon \exists I\in\mathcal I\colon I\cup\{x\}\not\in\mathcal I\}

상대 계수 함수를 통한 정의:

:

\operatorname{cl}(S) = \max \{S'\subseteq E\colon \operatorname{rank}(S'|S)=0\}

매트로이드

(E,\mathcal I)

의 상대 계수 함수는 독립 집합을 통해 정의할 수 있다.

:

\operatorname{rank}(A|B) = \max\{|I\setminus J|\colon E\supseteq I\supseteq J,\;I\in\mathcal I\cap\operatorname{Pow}(A),\;J\in\max(\mathcal I\cap\operatorname{Pow}(B))\}

2. 1. 독립 집합을 통한 정의

집합 E와 E의 부분집합족

\mathcal I

의 쌍

(E,\mathcal I)

에서,

\mathcal I

의 원소를 '''독립 집합'''이라고 하며, 다음 공리들을 만족시켜야 한다.^[75]

(공집합의 독립성) 공집합은 독립 집합이다. 즉, $\varnothing\in\mathcal I$ 이다.
(유전성 hereditary property^영어) 독립 집합의 부분집합은 독립이다. 즉, 만약 $B\subseteq A\in\mathcal I$ 라면 $B\in\mathcal I$ 이다.
(추가성 augmentation property^영어) 만약 $A, B\in\mathcal I$ 이며, $A$ 는 $\mathcal I$ 의 극대 원소이지만 $B$ 는 $\mathcal I$ 의 극대 원소가 아니라면, $B\cup\{a\}\in\mathcal I$ 인 $a\in A\setminus B$ 가 존재한다.
(국소적 극대 독립 집합의 존재) 만약 $\mathcal I\ni A\subset B\subset E$ 라면, 닫힌 구간 $\mathcal I\cap [A,B]=\{S\in\mathcal I\colon A\subseteq S\subset B\}$ 는 극대 원소를 갖는다.

2. 2. 기저를 통한 정의

집합 E와 E의 부분 집합족

\mathcal{B}

의 쌍 (E, 𝓑)에서,

\mathcal{B}

의 원소를 '''기저'''라고 하며, 다음 조건들을 만족시켜야 한다.^[75]

('''B1''') $\mathcal{B}\neq\emptyset$
('''B2''') 임의의 $B',B''\in \mathcal{B}, x \in B' \setminus B''$ 에 대해 $(B'\setminus \{ x \}) \cup \{ y \} \in \mathcal{B}$ 가 되는 $y \in {B''} \setminus {B'}$ 가 존재한다.

기저가 하나뿐인 경우는 매트로이드가 된다. 예를 들어

E = \{ 1,2,3 \}, \mathcal{B} = \{\{1,2\},\{2,3\},\{1,3\}\}

로 하면

\mathcal{B}

는 (B1) 및 (B2)를 만족한다. 이러한 기저의 족을 가진 매트로이드는 균등 매트로이드

U_3^2

단 하나로 결정된다. 반면, 기저족이

\mathcal{B}=\{\{1,2\},\{3\}\}

일 때는 (B2)를 만족하지 않으므로, 이 기저족으로는 매트로이드가 되지 않는다.

2. 3. 회로를 통한 정의

매트로이드

(E,\mathcal C)

는 다음과 같은 데이터로 주어진다.^[75]

집합 $E$
집합족 $\mathcal C\subseteq\operatorname{Pow}(E)$ . 그 원소를 '''회로'''(回路, circuit^영어)라고 한다. 회로를 부분 집합으로 포함하지 않는 집합을 '''독립 집합'''이라고 한다.

이 데이터는 다음 공리들을 만족시켜야 한다.

(공집합의 독립성) 공집합은 회로가 아니다. 즉, $\varnothing\not\in\mathcal C$ 이다.
임의의 $C,C'\in\mathcal C$ 에 대하여, $C\subseteq C'$ 라면 $C=C'$ 이다.
(회로의 제거) 임의의 회로 $C\in\mathcal C$ 및 회로의 족 $\mathcal U\subseteq\mathcal C$ 이 주어졌으며, 집합 $X\subseteq E$ 가 $\forall U\in\mathcal U\colon|X\cap U|=1$ 를 만족시킨다고 하자. 이제, $\textstyle Y= C\setminus\bigcup\mathcal U$ 로 놓자. 그렇다면, $\forall x\colon x\in f(x)$ 인 함수 $\textstyle f\colon Y\to\mathcal C\cap\operatorname{Pow}(Y\setminus X)$ 가 존재한다.
(국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$ 에 대하여, $I$ 를 포함하며 $E'$ 에 포함되는 독립 집합들의 부분 순서 집합은 적어도 하나 이상의 극대 원소를 갖는다.

유한 집합 E와 C ⊆ 2^E라고 하자. C가 매트로이드 (E, F)의 서킷족이 되기 위한 필요충분 조건은 다음이 성립하는 것이다.

(C1) $\emptyset\not\in{C}$
(C2) 임의의 C₁, C₂ ∈ C에 대해 C₁ ⊆ C₂이면 C₁ = C₂이다.
(C3) 임의의 C₁, C₂ ∈ C는 C₁ ≠ C₂이고 c ∈ C₁ ∩ C₂일 때, $C_3 \subseteq (C_1 \cup C_2) \setminus \{c \}$ 가 되는 C₃ ∈ C가 존재한다.

2. 4. 폐포를 통한 정의

집합 E와 함수

\operatorname{cl}\colon\operatorname{Pow}(E)\to\operatorname{Pow}(E)

의 쌍

(E,\operatorname{cl})

에서,

\operatorname{cl}

을 폐포 연산이라고 하며, 다음 조건들을 만족시켜야 한다.^[75]

$\operatorname{cl}$ 은 폐포 연산이다. 즉,
* 임의의 $X\subseteq E$ 에 대하여, $X\subseteq\operatorname{cl}(X)=\operatorname{cl}(\operatorname{cl}(X))$
* 임의의 $X\subseteq Y\subseteq E$ 에 대하여, $\operatorname{cl}(X)\subseteq\operatorname{cl}(Y)$
임의의 부분 집합 $X\subseteq E$ 에 대하여, $E$ 위의 다음 이항 관계는 대칭 관계이다.
: $x\sim_X y \iff x\in\operatorname{cl}(X\cup\{y\})\setminus\operatorname{cl}(X)$
(국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$ 에 대하여, 다음 조건을 만족시키는 독립 집합 $I\subseteq I'\subseteq E'$ 이 존재한다.
: $I'$ 은 극대적이다. 즉, 임의의 $x\in E'\setminus I'$ 에 대하여, $E'\cup\{x\}$ 는 종속 집합이다.

2. 5. 랭크 함수를 통한 정의

'''매트로이드'''

(E,\operatorname{rank})

는 다음의 데이터로 구성된다.

집합 $E$
함수 $\operatorname{rank}(-|-)\colon\operatorname{Pair}(E)\to\mathbb N\sqcup\{\infty\}$ . 이 함수는 '''상대 계수 함수'''(相對係數函數, relative rank function^영어)라고 불린다.

여기서

\operatorname{Pair}(E)=\{(S,T)\subseteq E\colon T\subseteq S\}\subseteq\operatorname{Pow}(E)^2

는

E

의 원소들 중, 길이가 2인 사슬들의 집합이다.

상대 계수 함수는 다음 조건들을 만족해야 한다.^[75]

임의의 $(A,B)\in\operatorname{Pair}(E)$ 에 대하여, $\operatorname{rank}(A|B)\le|A\setminus B|$ 이다.
임의의 $A,B\subseteq E$ 에 대하여, $\operatorname{rank}(A|A\cap B)\ge\operatorname{rank}(A\cup B|B)$ 이다.
(유한 사슬에 대한 분해) 임의의 $C\subseteq B\subseteq A\subseteq E$ 에 대하여, $\operatorname{rank}(A|C)=\operatorname{rank}(A|B)+\operatorname{rank}(B|C)$ 이다.
임의의 집합족 $\mathcal U\subseteq E$ 에 대하여, 만약 $\textstyle\forall U\in\mathcal U\colon\operatorname{rank}(U|\bigcap\mathcal U)=0$ 이라면, $\textstyle\operatorname{rank}(\bigcup\mathcal U|\bigcap\mathcal U)=0$ 이다.
(국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$ 에 대하여, $I$ 를 포함하며 $E'$ 에 포함되는 독립 집합들의 부분 순서 집합은 적어도 하나 이상의 극대 원소를 갖는다.

3. 성질

매트로이드의 랭크 함수 $r: 2^E \to \mathbb{R}$ 는 $X \subseteq E$ 에 대해 다음과 같이 정의된다.

: $r(X) := \max \{ |Y| : Y \subseteq X,Y \in F \}$

매트로이드에서 $E$ 의 부분 집합 $X$ 의 모든 기저의 원소 수는 같으므로, 랭크 함수는 $X$ 의 기저의 크기로 정의할 수 있다. 예를 들어 E = {1, 2, 3}, F = { {}, {1}, {2}, {1, 2} }인 매트로이드에서 r({1}) = 1, r({1, 2}) = 2, r({1, 2, 3}) = 2, r({1, 3}) = 1이다.

독립성 시스템 $(E,F)$ 의 랭크 함수 $r: 2^E \to \mathbb{R}$ 는 임의의 $X,Y \subseteq E$ 와 $x,y \in E$ 에 대해 다음 성질을 만족한다.

('''R1''') $r(X) \leq |X|$
('''R2''') $X \subseteq Y \Rightarrow r(X) \le r(Y)$
('''R3''') $r(\emptyset)=0$

(E,F)

가 매트로이드라면 다음 성질도 추가로 만족한다.

('''R4''') $r(X \cup Y)+r(X \cap Y) \leq r(X) + r(Y)$ (열모듈성)
('''R5''') $r(X) \leq r(X \cup \{x\}) \leq r(X)+1$
('''R6''') $r(X \cup \{x\}) = r(X \cup \{y\}) = r(X) \Rightarrow r(X \cup \{x,y\})=r(X)$

랭크 함수가 열 모듈러라는 성질(R4)은 매트로이드의 매우 중요한 성질이다.

랭크

r

인 매트로이드에서 랭크

r - 1

인 플랫을 ''초평면'' (''코아톰'' 또는 ''코포인트'')이라고 한다. 초평면은 최대 고유 플랫이며, 초평면을 포함하는 플랫은 전체 집합

E

뿐이다. 코아톰은 ''M''을 생성하지 않지만, 다른 원소를 추가하면 생성 집합이 되는 ''E''의 부분 집합으로 정의할 수도 있다.^[5]

매트로이드의 초평면 집합

\mathcal{H}

는 다음 성질을 가지며, 이는 매트로이드의 또 다른 공리화로 간주될 수 있다:^[5]

(H1) $\mathcal{H}$ 에 $X \subseteq Y$ 인 서로 다른 집합 $X$ , $Y$ 는 존재하지 않는다. (초평면은 스페르너족을 이룬다.)
(H2) 모든 $x \in E$ 에 대해, $x\notin Y \cup Z$ 인 서로 다른 $Y, Z \in \mathcal{H}$ 가 존재하면, $(Y \cap Z) \cup \{x\} \subseteq X$ 인 $X \in \mathcal{H}$ 가 존재한다.

3. 1. 계수

유한 매트로이드의 서로 다른 기저들의 크기는 서로 같다.^[77]

만약 일반화 연속체 가설이 참이라면, 모든 (유한 또는 무한) 매트로이드의 서로 다른 기저들의 크기는 서로 같은 기수이다.^[77] 이 경우, 기저의 크기를 매트로이드의 '''계수'''(rank^영어)라고 한다. 보다 일반적으로, 만약

\kappa\in\operatorname{Card}

이하에서 일반화 연속체 가설이 성립한다면 (즉,

\forall\aleph_0\le\lambda\le\kappa\colon \lambda^+=2^\lambda

), 크기가

\kappa

이하인 매트로이드의 모든 기저의 크기는 같다.

만약 선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)이 무모순적이라면, “임의의 매트로이드에서, 기저들의 크기는 같다”라는 명제는 ZFC와 독립적이다.^[78]

3. 2. 작은 매트로이드의 수

작은 크기의 매트로이드의 동형류의 수, 고리 없는 매트로이드의 동형류의 수, 단순 매트로이드의 동형류의 수는 다음과 같다.^[79]

크기	매트로이드 동형류의 수	고리 없는 매트로이드 동형류의 수	단순 매트로이드 동형류의 수
0	1	1	1
1	2	1	1
2	4	2	1
3	8	4	2
4	17	9	4
5	38	21	9
6	98	60	26
7	306	208	101
8	1724	1418	950
9	383172	381448	376467

3. 3. 범주론적 성질

유한 매트로이드와 강사상의 작은 범주를

\operatorname{finMatr}

라고 한다. 또한, 유한 집합과 함수의 작은 범주를

\operatorname{finSet}

라고 한다.

\operatorname{finMatr}

는 구체적 범주이며, 망각 함자

:

|-|\colon \operatorname{finMatr}\to\operatorname{finSet}

가 존재한다.

이 밖에도, 균등 매트로이드 함자

:

\operatorname{Unif}(-,0) \colon\operatorname{finSet} \to \operatorname{finMatr}

:

\operatorname{Unif}(-,0)^* \colon\operatorname{finSet} \to \operatorname{finMatr}

:

\operatorname{Unif}(-,0) \colon S\mapsto \operatorname{Unif}(S,0)

:

\operatorname{Unif}(-,0)^* \colon S\mapsto \operatorname{Unif}(S,0)^* = \operatorname{Unif}(S,|S|)

및

:

(-)_0 \colon\operatorname{finMatr} \to \operatorname{finSet}

:

(-)_0 \colon E \mapsto \operatorname{cl}_E(\varnothing)

:

(-)_0 \colon (E \xrightarrow f E') \mapsto \left(f\restriction (\operatorname{cl}_E(\varnothing))\right)

를 정의할 수 있다.

이들은 다음과 같은 수반 함자 관계를 이룬다.^[81]

:

\operatorname{Unif}(-,0)^* \dashv |-| \dashv \operatorname{Unif}(-,0) \dashv (-)_0

즉, 균등 매트로이드

\operatorname{Unif}(S,0)^*

은 “자유 매트로이드”이며,

\operatorname{Unif}(S,0)

은 “쌍대 자유 매트로이드”이다.

\operatorname{finMatr}

는 모든 유한 쌍대곱을 갖지만, 모든 유한 곱을 갖지 못하며, 또한 유한 쌍대 극한 가운데 일부는 존재하지 못한다.^[81]

4. 연산

그래프 이론은 매트로이드 이론의 주요 원천 중 하나이다.

모든 유한 그래프(또는 멀티그래프) $G$ 는 매트로이드 $M(G)$ 를 생성한다. $E$ 를 $G$ 의 모든 간선들의 집합으로 하고, 간선 집합이 숲인 경우, 즉 단순 사이클을 포함하지 않는 경우에만 독립으로 간주한다. $M(G)$ 는 "사이클 매트로이드"라고 불리며, 이렇게 파생된 매트로이드는 ''그래픽 매트로이드''이다. 모든 매트로이드가 그래픽 매트로이드인 것은 아니지만, 세 개의 원소를 가진 모든 매트로이드는 그래픽 매트로이드이다.^[22] 모든 그래픽 매트로이드는 정규 매트로이드이다.

그래프에 대한 다른 매트로이드들은 다음과 같다.

그래프의 이중사이클 매트로이드는 모든 연결된 부분 집합이 최대 하나의 사이클을 포함하는 경우 독립적인 간선 집합을 호출하여 정의된다.

임의의 방향 그래프 또는 무방향 그래프 $G$ 에서, $E$ 와 $F$ 를 두 개의 구별되는 정점 집합으로 둔다. 집합 $E$ 에서, 하위 집합 $U$ 가 $|U|$ 개의 정점-분리된 경로가 $F$ 에서 $U$ 로 이어지는 경우 독립적이라고 정의한다. 이것은 ''감마이드''라고 불리는 $E$ 에 대한 매트로이드를 정의한다.^[10] ''엄격한 감마이드''는 집합 $E$ 가 $G$ 의 전체 정점 집합인 경우이다.^[7]

이분 그래프 $G = (U,V,E)$ 에서, 요소가 이분 그래프의 한쪽 $U$ 에 있는 정점이고 독립적인 하위 집합이 그래프의 매칭의 끝점 집합인 매트로이드를 형성할 수 있다. 이것은 ''횡단 매트로이드''라고 불리며,^[8]^[9] 감마이드의 특별한 경우이다.^[10] 횡단 매트로이드는 엄격한 감마이드에 대한 쌍대 매트로이드이다.^[7]

그래픽 매트로이드는 부호 그래프, 게인 그래프, 편향 그래프에서 매트로이드로 일반화되었다. 사이클의 구별되는 선형 클래스 $B$ 를 가진 그래프 $G$ 는 "편향 그래프" $(G, B)$ 로 알려져 있으며, 편향 그래프의 ''프레임 매트로이드''와 ''리프트 매트로이드''로 알려진 두 개의 매트로이드를 갖는다.

라만 그래프는 2차원 강성 매트로이드의 기저를 형성하며, 이는 구조적 강성 이론에서 정의된 매트로이드이다.

$G$ 를 연결된 그래프로 하고 $E$ 를 간선 집합으로 하자. $I$ 를 $G - F$ 가 여전히 연결되어 있는 $E$ 의 하위 집합 $F$ 의 모음으로 하자. 그러면 $M^*(G)$ 요소 집합이 $E$ 이고 독립 집합의 클래스가 $I$ 인 매트로이드는 $G$ 의 ''결합 매트로이드''라고 불린다.

기존 매트로이드로부터 새로운 매트로이드를 구성하는 몇 가지 방법이 있다.

4. 1. 쌍대 매트로이드

매트로이드

(E,\mathcal I)

의 쌍대 매트로이드

(E^*,\mathcal I^*)

는 다음과 같이 정의된다. 집합은

E=E^*

로 동일하지만,

:

\mathcal I^*=\{S\in\mathcal P(E)\colon\operatorname{cl}_{\mathcal I}(E\setminus S)=E\}

이다. 즉,

E

의 기저는

E^*

의 기저의 여집합이다.

이 연산은 쌍대성을 가지는데,

E^{**}=E

이다.

M

이 유한 매트로이드일 때, 동일한 기본 집합을 사용하고, 원래 집합의 여집합이

M

에서 "기저"일 때만 해당 집합을

M^*

에서 "기저"라고 부르는 방식으로 ''직교'' 또는 ''쌍대 매트로이드''

M^*

를 정의할 수 있다.

M^*

는 매트로이드이며,

M^*

의 쌍대는

M

이다.^[13]

쌍대는 매트로이드를 정의하는 다른 방법을 사용하여 다음과 같이 표현할 수 있다.

집합은 여집합이 $M$ 을 생성할 때만 $M^*$ 에서 독립이다.

집합은 여집합이 $M$ 에서 코원자일 때만 $M^*$ 의 회로이다.

쌍대의 랭크 함수는 $r^*(S) = |S| - r(M) + r\left(E\smallsetminus S\right)$ 이다.

쿠라토프스키 정리의 매트로이드 버전에 따르면, 그래프 매트로이드

M

의 쌍대는

M

이 평면 그래프의 매트로이드일 경우에만 그래프 매트로이드이다. 이 경우,

M

의 쌍대는

G

의 쌍대 그래프의 매트로이드이다.^[14] 특정 체

F

위에서 표현 가능한 벡터 매트로이드의 쌍대 또한

F

위에서 표현 가능하다. 횡단 매트로이드의 쌍대는 엄격한 감마이드이며 그 반대도 성립한다.

;예시: 그래프의 사이클 매트로이드는 그 결합 매트로이드의 쌍대 매트로이드이다.

독립성 시스템 (E, F)에 대해, F^*를

X \cap B = \emptyset

이 되는 (E, F)의 기저 B가 존재하는

X \subseteq E

의 집합으로 한다. 이 때, (E, F^*)를 (E, F)의 '''쌍대'''(dual)라고 정의한다.

쌍대에는 다음과 같은 성질이 있다.

(E, F^**) = (E, F)
(E, F)가 독립성 시스템이면, (E, F^*)는 독립성 시스템이다.
(E, F)는 매트로이드 $\iff$ (E, F^*)는 매트로이드^[45]
매트로이드 (E, F)와 그 쌍대 (E, F^*)로, 각각의 랭크 함수를 r, r^*라고 하면, r^*는 임의의 X ⊆ E에 대해 $r^*(X)=|X|+r(E{\setminus}X)-r(E)$ 이다.

예를 들어, E = {1, 2, 3}, F = 라는 매트로이드에 대해 기저족 B = { {1, 2} }이므로 F^* = { {3} }이 된다. 쌍대의 랭크 함수도, 예를 들어 r^*({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1이 되는 것처럼 성립함을 알 수 있다.

또한, 평면 그래프에 대한 쌍대와 그래프적 매트로이드의 쌍대 개념은 일치한다. 즉, 임의의 평면 그래프 G의 사이클 매트로이드 M(G)의 쌍대는 G의 쌍대 평면 그래프 G^*의 매트로이드와 (평면 매립 방법에 관계없이) 동일하다.

4. 2. 부분 매트로이드

매트로이드

(E,\mathcal I)

의 부분 집합

S\subseteq E

위에서,

(S,\mathcal I\cap\operatorname{Pow}(S))

는 매트로이드를 이룬다. 이를

E

의 '''부분 매트로이드'''(submatroid^영어)라고 한다. 매트로이드의 부분 집합

S

의 계수는 부분 매트로이드로서의 계수이다.

4. 3. 직합

두 매트로이드

(E_1,\mathcal I_1)

,

(E_2,\mathcal I_2)

가 주어졌을 때, 분리합집합

E=E_1\sqcup E_2

위에 다음과 같은 매트로이드 구조를 줄 수 있다.

:

\mathcal I=\{I_1\sqcup I_2\colon I_1\in\mathcal I_1,\;I_2\in\mathcal I_2\}

이를 두 매트로이드의 '''직합'''이라고 하며,

E_1\oplus E_2

로 쓴다. 이 용어는 벡터 공간의 부분 집합으로 나타내어지는 매트로이드의 직합이 해당 벡터 공간들의 직합에 해당하기 때문에 붙여졌다.

기본 원소 집합 ''E''를 가진 매트로이드 ''M''과 기본 원소 집합 ''F''를 가진 또 다른 매트로이드 ''N''이 있을 때, 매트로이드 ''M''과 ''N''의 ''직합''은 기본 집합이 ''E''와 ''F''의 상호 배타적 합집합이고, 독립 집합이 ''M''의 독립 집합과 ''N''의 독립 집합의 상호 배타적 합집합인 매트로이드이다.

4. 4. 마이너

부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 '''매트로이드 마이너'''라고 한다. 이는 그래프 마이너의 일반화이다.

원소 집합이 ''E''인 매트로이드 ''M''이 있고, ''S''가 ''E''의 부분 집합인 경우, ''M''을 ''S''로 ''제한''한 것(즉, ''M'' |''S'')은 ''S''에 포함된 ''M''의 독립 집합이 독립 집합인 집합 ''S''에 대한 매트로이드이다. 이 매트로이드의 회로는 ''S''에 포함된 ''M''의 회로이며, 랭크 함수는 ''S''의 부분 집합으로 제한된 ''M''의 랭크 함수이다.

선형대수학에서 이는 ''S''의 벡터에 의해 생성된 부분 공간으로 제한하는 것에 해당한다. 동등하게, ''T'' = ''M''−''S''이면 이를 ''T''의 ''삭제''라고 할 수 있으며, ''M''\''T'' 또는 ''M''−''T''로 표기한다. ''M''의 부분 매트로이드는 삭제 시퀀스의 결과와 정확히 일치한다. 순서는 관련이 없다.^[15]^[16]

제한의 이중 연산은 수축이다.^[17] ''T''가 ''E''의 부분 집합인 경우, ''T''에 의한 ''M''의 ''수축''(즉, ''M''/''T'')은 기저 집합 ''E − T''에 대한 매트로이드이며, 랭크 함수는

r'(A) = r(A \cup T) - r(T).

이다.^[18] 선형대수학에서 이는 ''T''의 벡터에 의해 생성된 선형 공간에 의한 몫 공간과 ''E - T''의 벡터의 이미지와 함께 살펴보는 것에 해당한다.

제한 및 수축 연산의 시퀀스를 통해 ''M''에서 얻은 매트로이드 ''N''을 ''M''의 마이너라고 한다.^[16]^[19] ''M''이 ''N''을 ''마이너로 포함한다''라고 말한다. 많은 중요한 매트로이드 패밀리는 해당 패밀리에 속하지 않는 마이너-최소 매트로이드로 특징지을 수 있으며, 이를 ''금지된'' 또는 ''제외된 마이너''라고 한다.^[20]

4. 5. 안둘레와 밖둘레

매트로이드의 '''안둘레'''는 가장 작은 회로의 크기이다. 마찬가지로, 매트로이드의 '''밖둘레'''는 회로들의 크기의 상한이다.^[22]

5. 종류

매트로이드에는 여러 종류가 있다.

용어	정의
유한 매트로이드	E가 유한 집합인 매트로이드
유한형 매트로이드	모든 회로가 유한 집합인 매트로이드
유순 매트로이드	모든 회로와 쌍대 회로의 교집합이 유한 집합인 매트로이드
고리 없는 매트로이드	모든 회로의 크기가 1 이상인 매트로이드
단순 매트로이드	모든 회로의 크기가 2 이상인 매트로이드

크기가 1인 회로는 '''고리'''(loop|루프^영어)라고 하며, 크기가 2인 회로는 '''평행변'''(平行邊, parallel lines|패럴렐 라인^영어)이라고 한다. 이러한 용어는 다중 그래프에 대응되는 순환 그래프에서 유래하였다.

5. 1. 유한성

E가 유한 집합인 매트로이드를 유한 매트로이드라고 한다. 모든 회로가 유한 집합인 매트로이드를 유한형 매트로이드라고 한다. 모든 회로와 쌍대 회로의 교집합이 유한 집합인 매트로이드를 유순 매트로이드라고 한다.

5. 2. 작은 회로의 부재

크기 1의 회로는 '''고리'''(loop^영어)라고 하며, 크기 2의 회로는 '''평행변'''(平行邊, parallel lines^영어)이라고 한다. 이러한 용어는 다중 그래프에 대응되는 순환 그래프에서 유래하였다.

모든 회로의 크기가 2 이상인 매트로이드를 '''단순 매트로이드'''(simple matroid^영어)라고 한다. 모든 회로의 크기가 1 이상인 매트로이드를 '''고리 없는 매트로이드'''(loopless matroid^영어)라고 한다.

6. 예

(내용 없음)

6. 1. 균등 매트로이드

임의의 집합 E와 자연수 k에 대해, 크기가 k 이하인 부분집합을 독립 집합으로 갖는 매트로이드를 균등 매트로이드라고 한다. 균등 매트로이드는 항상 유한형 매트로이드이다.^[41]

균등 매트로이드

\operatorname{Unif}(E,k)

는 다음과 같이 정의된다.

독립 집합: $\mathcal I=\{S\subseteq E\colon |S|\le k\}$
기저: $\mathcal B=\{S\subseteq E\colon |S| =k\}$
종속 집합: $\mathcal C=\{S\subseteq E\colon |S| =k+1\}$

E

가 유한 집합일 때,

\operatorname{Unif}(E,k)

의 쌍대 매트로이드는

\operatorname{Unif}(E,|E|-k)

이다. 만약

E

가 무한 집합이라면,

\operatorname{Unif}(E,k)

의 쌍대 매트로이드는 더 이상 유한형 매트로이드가 아니다.

n

개의 원소를 갖는 균등 매트로이드의 랭크가

k

이면

U_{k,n}

으로 표시한다. 랭크가 2 이상인 모든 균등 매트로이드는 단순 매트로이드이다.

n

개의 점에 대한 랭크 2의 균등 매트로이드를

n

''점 직선''이라고 한다.

매트로이드는 매트로이드의 랭크에 1을 더한 것보다 작은 크기의 회로가 없는 경우에만 균등 매트로이드이다. 균등 매트로이드의 직접 합은 분할 매트로이드라고 한다.^[41]

E를 유한 집합으로 하고, 어떤 정수 r 이하의 원소수를 갖는 2^E의 부분집합을 F라고 할 때, (E, F)는 매트로이드가 된다. 이것을 '''균일 매트로이드'''라고 부르며, n=|E|로 했을 때

U_n^r

등으로 쓴다.

U_n^r

에서의 기저는 원소수가 r인 E의 부분집합이며, 회로는 원소수가 r+1인 E의 부분집합이다.^[41]

6. 2. 선형 매트로이드

체

K

에 대한 유한 차원 벡터 공간

V

의 유한 부분 중복집합

E\subset V

가 있을 때,

E

의 일차독립 부분 중복집합들을 독립 집합으로 갖는 매트로이드를 선형 매트로이드(linear matroid^영어)라고 한다.^[6]

파노 평면에서 파생된 파노 매트로이드. GF(2)-선형이지만 실수 선형은 아님

만약

E

가 벡터 공간

V

의 유한한 부분 집합이라면,

M

의 독립 집합을

E

의 선형 독립 부분 집합으로 정의하여

E

에 대한 매트로이드

M

을 정의할 수 있다. 이 매트로이드에 대한 독립 집합 공리의 타당성은 슈타이니츠 교환 보조정리로부터 나온다.

만약

M

이 이런 방식으로 정의될 수 있는 매트로이드라면, 집합

E

가

M

을 ''표현''한다고 말한다. 이러한 종류의 매트로이드를 ''벡터 매트로이드''라고 한다.

벡터 매트로이드와 동등한 매트로이드는, 다르게 표현될 수 있지만, ''표현 가능'' 또는 ''선형''이라고 한다. 만약

M

이 체

F

에 대한 벡터 매트로이드와 동등하다면,

M

이

F

에 대해 ''표현 가능''하다고 말하며, 특히, 실수를 통해 표현 가능한 경우

M

은 ''실수 표현 가능''하다.

행렬

A

는 체의 원소를 가지며, 열 집합에 대한 매트로이드

M

을 발생시킨다. 매트로이드에서 열의 종속 집합은 벡터로 선형 종속적인 열이다. 이 매트로이드를

A

의 ''열 매트로이드''라고 하며,

A

는

M

을 ''표현''한다고 말한다.^[6]

정규 매트로이드는 가능한 모든 체에 대해 표현 가능한 매트로이드이다. Vámos 매트로이드는 어떤 체에 대해서도 표현 불가능한 매트로이드의 가장 간단한 예이다.^[6]

E를 체 위의 행렬의 열 집합, 그 체 위에서 선형 독립인 열의 집합을 F라고 할 때, (E, F)는 마트로이드가 되며, '''벡터 마트로이드'''라고 부른다. 마트로이드가 동일한 체 K 위의 벡터 마트로이드로 기술될 수 있을 때, '''표현 가능'''하다고 불린다. 임의의 체 위에서 표현 가능한 마트로이드를 '''정칙 마트로이드'''라고 부르며, 위수 2의 유한체 위에서 표현 가능한 마트로이드를 '''이진 매트로이드'''라고 부른다.

6. 3. 그래프의 매트로이드

그래프에는 '''순환 매트로이드'''라는 유한형 매트로이드와 그 쌍대 매트로이드인 '''접합 매트로이드'''가 대응된다.^[6]

이 외에도 그래프에는 다음과 같은 매트로이드들이 알려져 있다.

E를 무향 그래프 G의 변 집합, F를 pseudoforest^[43]가 되는 X의 집합이라고 할 때 (E, F)는 매트로이드가 된다. 이것을 '''이중 사이클 매트로이드(Bicircular matroid)'''라고 부른다.
점 집합 U, V, 변 집합 X인 이분 그래프에서, 매칭의 단말점이 되는 점 집합 $S \subseteq U$ 를 요소로 하는 집합을 F라고 할 때, (U, F)는 매트로이드가 된다. 이것을 '''횡단 매트로이드''' (transversal matroid)라고 부른다. 완전 이분 그래프 $K_{n,r}$ 의 횡단 매트로이드는 균일 매트로이드 $U_n^r$ 이다.
점 집합을 V로 하는 그래프에서 점의 부분 집합을 $V',U \subseteq V$ 라고 한다. U로의 점소(點素)인 |U|개의 경로가 존재하는 V'의 부분 집합을 F의 요소로 하면, (V', F)는 매트로이드가 된다. 이것을 '''감마이드(Gammoid)'''라고 부른다. 특히, (V, F)를 '''협의 감마이드''' (strict gammoid)라고 부른다.

6. 4. 작은 크기의 매트로이드

공집합 위에는 유일한 매트로이드 구조가 존재하며, 이는 균등 매트로이드

\operatorname{Unif}(0,0)

이다. 이는 무변 그래프의 순환 매트로이드이자, 임의의 벡터 공간 속의 공집합으로부터 정의되는 선형 매트로이드이다.

크기 1의 매트로이드 동형류는 다음 두 가지이다.

$\operatorname{Unif}(1,1)$ (계수 1). 이는 한 변을 갖는 경로 그래프 $P_2$ 의 순환 매트로이드이다.
$\operatorname{Unif}(1,0)$ (계수 0). 이는 하나의 꼭짓점과 하나의 변을 갖는 다중 그래프의 순환 매트로이드이다.

크기 2의 매트로이드 동형류는 다음 네 가지이다.

$\operatorname{Unif}(2,2)$ (계수 2)
$\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(1,0)$ (계수 1)
$\operatorname{Unif}(2,1)$ (계수 1)
$\operatorname{Unif}(2,0)$ (계수 0)

이 가운데 단순 매트로이드인 것은 첫째 밖에 없다.

크기 3의 매트로이드 동형류는 다음 여덟 가지이다.

$\operatorname{Unif}(3,3)$ (계수 3)
$\operatorname{Unif}(3,2)$ (계수 2)
$\operatorname{Unif}(2,2)\oplus\operatorname{Unif}(1,0)$ (계수 2)
$\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,1)$ (계수 2)
$\operatorname{Unif}(3,1)$ (계수 1)
$\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,0)$ (계수 1)
$\operatorname{Unif}(2,0)\oplus\operatorname{Unif}(1,1)$ (계수 1)
$\operatorname{Unif}(3,0)$ (계수 0)

이 가운데 단순 매트로이드인 것은 처음 두 개이다.

크기 4의 매트로이드는 총 17개가 있으며, 하나를 제외하고는 나머지는 균등 매트로이드들의 직합으로 표현될 수 있다.

계수	매트로이드
0	$\operatorname{Unif}(4,0)$
1	$\operatorname{Unif}(4,1)$
	$\operatorname{Unif}(3,1)\oplus\operatorname{Unif}(1,0)$
	$\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(2,0)$
	$\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(3,0)$
2	$\operatorname{Unif}(4,2)$
	$\operatorname{Unif}(3,1)\oplus\operatorname{Unif}(1,1)$
	$\operatorname{Unif}(3,2)\oplus\operatorname{Unif}(1,0)$
	$\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(2,1)$
	$\operatorname{Unif}(2,2)\oplus\operatorname{Unif}(2,0)$
	$\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(1,0)$
	균등 매트로이드의 직합이 아닌 매트로이드 $X$

계수 3 및 계수 4의, 크기 4의 매트로이드들은 각각 계수 1 및 계수 0의 것들의 쌍대 매트로이드로 얻어진다.

여기서, 매트로이드 $X$ 는 다음과 같다.

: $E=\{\mathsf a,\mathsf b,\mathsf c,\mathsf d\}$

: $\mathcal B=\{S\subseteq E\colon |S|=2,\;S\ne\{\mathsf a,\mathsf b\}\}$

: $\mathcal C=\left\{\{\mathsf a,\mathsf b\},\{\mathsf b,\mathsf c,\mathsf d\},\{\mathsf a,\mathsf c,\mathsf d\}\right\}$

이는 다음과 같은 다중 그래프에 대응하는 순환 매트로이드이다.

마찬가지로, 이는 (예를 들어) 다음과 같은 실수 벡터 공간

\mathbb R^2

의 부분 집합

\{\mathsf a,\mathsf b,\mathsf c,\mathsf d\}

에 대응되는 매트로이드와 동형이다.

:

\mathsf a=(1,0)

:

\mathsf b=(2,0)

:

\mathsf c=(0,1)

:

\mathsf d=(1,1)

7. 역사

해슬러 휘트니가 1935년에 매트로이드의 개념을 도입하였다.^[82] 1938년에 일본의 나카자와 다케오(中澤武雄|나카자와 다케오^일본어, 1913~1946)가 동일한 개념을 독립적으로 발견하였으나,^[83]^[84]^[85]^[86] 크게 알려지지 못했다.

이후 윌리엄 토머스 텃이 매트로이드 이론을 발달시켰고, 텃 다항식과 같은 중요한 개념들을 발견하였다.^[87]

1970년에 잔카를로 로타와 헨리 하울런드 크레이포(Henry Howland Crapo|헨리 하울런드 크레이포^영어)는 매트로이드 이론에 대한 최초의 책을 출판하였다.^[88] (이 책에서는 “매트로이드” 대신 “조합 기하”(combinatorial geometry|조합 기하^영어)라는 용어가 사용되었다.) 이듬해에 윌리엄 토머스 텃은 매트로이드 이론에 대한 둘째 책을 출판하였다.^[89]

무한 매트로이드의 올바른 정의는 오랫동안 미해결 문제였다. 1966년에 리하르트 라도는 무한 매트로이드의 올바른 정의에 대한 문제를 제기하였다.^[90] 데니스 힉스(Denis A. Higgs|데니스 힉스^영어, 1932~2011)는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 “B-매트로이드”(B-matroid|B-매트로이드^영어)라는 개념이었다.^[91]

이후 1978년에 제임스 옥슬리(James G. Oxley|제임스 옥슬리^영어)는 “B-매트로이드”의 모임이 쌍대성을 가지며 매트로이드 마이너에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다.^[92] 이후 2010년에 이 “B-매트로이드”에 대한 여러 자연스러운 공리화들이 발견되었으며,^[75] 이후 이 개념이 무한 매트로이드의 통상적인 정의로 굳어지게 되었다.

8. 응용

가중 매트로이드에서 탐욕 알고리즘을 사용하여 최대 가중치 독립 집합을 찾을 수 있다. 이는 매트로이드의 특징을 나타내는 데 사용될 수 있다.^[29]

매트로이드 분할 문제는 매트로이드 원소를 가능한 적은 수의 독립 집합으로 분할하는 것이고, 매트로이드 포장 문제는 가능한 많은 서로소 생성 집합을 찾는 것이다. 이 두 문제 모두 다항 시간 안에 해결할 수 있다.

동일한 기본 집합에 대한 둘 이상의 매트로이드의 매트로이드 교차는 각 매트로이드에서 동시에 독립적인 집합의 집합족이다. 두 매트로이드 교차에서 가장 큰 집합 또는 최대 가중치 집합을 찾는 문제는 다항 시간 안에 찾을 수 있다. 그러나 셋 이상의 매트로이드 교차에서 가장 큰 집합을 찾는 문제는 NP-완전이다.

매트로이드 계산을 위한 오픈 소스 패키지로는 Kingan의 [http://userhome.brooklyn.cuny.edu/skingan/software.html Oid]와 Hlineny의 [http://www.fi.muni.cz/~hlineny/MACEK/ Macek]가 있다.^[30]

조합 최적화 문제 대부분은 독립성 시스템과 코스트 함수에 대해 최적의 해를 구하는 문제로 정식화할 수 있다. 예를 들어, 최소 신장 트리 문제는 매트로이드가 되지만, 외판원 문제나 배낭 문제는 매트로이드가 되지 않는다.

매트로이드에서는 탐욕법으로 최적해를 얻을 수 있다. 크루스칼 알고리즘은 매트로이드 상의 탐욕법으로 설명할 수 있지만, 프림 알고리즘이나 다익스트라 알고리즘은 그렇지 않다.

'''최량 선택 탐욕법'''은 비용이 큰 순서대로 요소를 잠정 해에 추가하는 알고리즘이다. 최량 선택 탐욕법으로 얻을 수 있는 해의 비용과 최적 해의 비용 사이에는 랭크 비를 사용한 관계식이 성립한다.^[47]^[48] 독립성 시스템이 매트로이드가 되기 위한 필요충분 조건은 최량 선택 탐욕법으로 최대화 문제의 최적 해를 구할 수 있는 것이며, 이를 '''Edmonds-Rado 정리'''라고 한다.^[49]^[50]

'''최악 기각 탐욕법'''은 불리한 요소를 우선적으로 해에서 제외하는 알고리즘이다. 매트로이드라면 최악 기각 탐욕법으로도 항상 최적해를 얻을 수 있다.^[55]

'''매트로이드 교차 문제'''는 두 개의 매트로이드가 주어졌을 때, 최대 크기의 공통 독립 집합을 찾는 문제이다. 이 문제는 다항 시간 내에 풀 수 있지만, 셋 이상의 매트로이드 교차 문제는 NP-난해 문제이다. 가중치 버전에 대한 알고리즘도 알려져 있다.^[66]

'''매트로이드 분할 문제'''는 k개의 매트로이드가 주어졌을 때, 최대 크기의 분할 가능한 집합을 구하는 문제이다. 매트로이드 교차 문제와 매트로이드 분할 문제는 서로 동일하다.

참조

_[1] 논문
_[2] 논문
_[3] 서적
_[4] 서적
_[5] 서적
_[6] 간행물 Solving Rota's conjecture http://www.ams.org/n[...] 2014-08-17
_[7] 서적
_[8] 서적
_[9] 서적
_[10] 서적
_[11] 서적
_[12] 서적
_[13] 서적
_[14] 서적
_[15] 서적
_[16] 서적
_[17] 서적
_[18] 서적
_[19] 서적
_[20] 서적
_[21] 서적
_[22] 서적
_[23] 서적
_[24] 서적
_[25] 서적
_[26] 서적
_[27] 논문
_[28] 서적
_[29] 서적
_[30] 웹사이트 The Matroids and Hypergraphs Packages in Maple 2024 https://www.maplesof[...] MapleSoft 2024-08-19
_[31] 서적
_[32] 서적
_[33] 서적
_[34] 서적
_[35] 서적
_[36] 간행물
_[37] 간행물
_[38] 간행물
_[39] 문서 記号の意味については「冪集合」「空集合」「集合間の関係を表す記号」「濃度 (数学)」「合併 (集合論)|和集合」「差集合」を参照のこと
_[40] 논문 Worst case analysis of greedy type algorithms for independence systems
_[41] 문서 マトロイドの直和もマトロイドになる。
_[42] 문서 閉路のない辺集合
_[43] 문서 各連結成分において、高々1つの閉路を持つグラフ
_[44] 문서 (R3),(R5),(R6)を満たす関数と(R1),(R2),(R4)を満たす関数は同値
_[45] 논문 On the abstract properties of linear dependence http://www.math.osu.[...] 1935-07
_[46] 서적 Theory of Graphs; proceedings of an international symposium in Rome 1966 Gordon and Breach
_[47] 논문 The Efficacy of the greedy Algorithm
_[48] 서적 Aogorithmic Aspects of Combinatorics; Annals of Discrete Mathematics North-Holland
_[49] 논문 Note on Independence Functions
_[50] 논문 Matroids and the greedy algorithm
_[51] 문서 $(|X_j| - |X_{j-1}|)$ は、 $e_j \in X$ のとき、かつそのときのみ1となるから、 $c(X) = \sum_{j=1}^n (|X_j| - |X_{j-1}|) c(e_j)$ が得られる。これを $|X_j|$ でまとめて右辺を得る。
_[52] 문서 "{{mvar|G{{sub|j}}}} は {{mvar|E{{sub|j}}}} の基であり、{{math|ρ}} の定義より得られる。"
_[53] 문서 ランク商の定義より明らか。
_[54] 문서 $OPT_j\in F$ であることと、階数関数の定義および性質('''R1''')より得られる。
_[55] 서적 Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen Birkhäuser
_[56] 문서 '''X''' の基でないことに注意
_[57] 문서 概念は「[[多項式時間変換]]」に詳しい
_[58] 서적 Complexity of Computer Computations New York: Plenum
_[59] 문서 最良選択貪欲法を使うことによって（本質的には独立性オラクルを複数回使うことによって）基決定オラクルを作れるが、逆に基決定オラクルを多項式回使っても独立性オラクルを作れない
_[60] 논문 Algorithmic versus axiomatic definitions of matroids
_[61] 서적 Nonlinear Programming Academic Press
_[62] 논문 Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems 1975-10
_[63] 논문 Algorithms for Scheduling Independent Tasks 1976-01
_[64] 서적 Mathematical Foundations of Computer Science Springer
_[65] 논문 Fast Approximation Algorithms for Knapsack Problems
_[66] 논문 A weighted matroid intersection algorithm
_[67] 논문 The ellipsoid method and its consequences in combinatorial optimization http://oai.cwi.nl/oa[...] 2011-03-26
_[68] 논문 A combinatorial algorithm minimizing submodular functions in strongly polynomial time https://homepages.cw[...] 2023-05-14
_[69] 서적 Matroids: a geometric introduction Cambridge University Press 2012-09
_[70] 서적 Matroid theory https://archive.org/[...] Oxford University Press 1992
_[71] 서적 Matroid theory and its applications in electric network theory and in statics https://archive.org/[...] Springer-Verlag, Akademiai Kiado 1989
_[72] 서적 Independence theory in combinatorics https://archive.org/[...] Chapman and Hall 1980
_[73] 서적 Matroid theory Academic Press 1976
_[74] 저널 An introduction to matroid theory 1973-05
_[75] 저널 Axioms for infinite matroids 2013-06-01
_[76] 저널 Matroids with an infinite circuit-cocircuit intersection 2014-07
_[77] 저널 Equicardinality of bases in B-matroids 1969-03
_[78] 저널 Self-dual uniform matroids on infinite sets http://www.math.uni-[...] 2016
_[79] 저널 Matroids with nine elements 2007
_[80] 저널 On the number of matroids 2015-04
_[81] 저널 The category of matroids 2017
_[82] 저널 On the abstract properties of linear dependence 1935
_[83] 저널 Zur Axiomatik der linearen Abhängigkeit Ⅰ http://jairo.nii.ac.[...] 1935
_[84] 저널 Zur Axiomatik der linearen Abhängigkeit Ⅱ http://jairo.nii.ac.[...] 1936
_[85] 저널 Zur Axiomatik der linearen Abhängigkeit Ⅲ http://jairo.nii.ac.[...] 1936
_[86] 서적 A lost mathematician, Takeo Nakasawa: the forgotten father of matroid theory 2009
_[87] 저널 Lectures on matroids 1965
_[88] 서적 On the Foundations of Combinatorial Theory Ⅱ. Combinatorial geometries 1970
_[89] 서적 Introduction to the theory of matroids Elsevier 1971
_[90] 저널 Abstract linear dependence http://pldml.icm.edu[...] 1966
_[91] 저널 Matroids and duality http://pldml.icm.edu[...] 1969
_[92] 저널 Infinite matroids 1978-09

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com