순환 매트로이드

3. 성질

완전 그래프 $K\_n$의 그래픽 매트로이드는 특별한 성질을 지닌다. 이 매트로이드의 플랫은 $K\_n$의 부분 그래프가 정의하는 정점들의 연결 요소 분할과 대응하며, 모든 가능한 정점 분할이 이러한 방식으로 표현될 수 있다. 결과적으로, $K\_n$의 그래픽 매트로이드의 플랫 격자는 $n$개의 원소를 가지는 집합의 분할 격자와 자연스럽게 동형 관계를 이룬다. 모든 매트로이드의 플랫 격자는 기하 격자이므로, 이는 집합의 분할 격자 역시 기하 격자임을 보여준다.^[2]

3. 1. 그래프 성질과의 관계

특히, 그래프에서 그래프 마이너 연산(제한 또는 축약)은 순환 매트로이드와 접합 매트로이드에서 매트로이드 마이너 연산에 대응된다. 구체적으로, 그래프의 제한 마이너는 순환 매트로이드의 제한 마이너 및 접합 매트로이드의 축약 마이너에 해당하고, 그래프의 축약 마이너는 순환 매트로이드의 축약 마이너 및 접합 매트로이드의 제한 마이너에 해당한다.

순환 매트로이드는 그래픽 매트로이드의 한 예이다. 일반적으로 그래프 $G$가 주어졌을 때, $G$의 변 집합 $E$와 $E$의 부분 집합 중 숲(순환이 없는 부분 그래프)을 이루는 것들의 모임 $\backslash mathcal\{F\}$를 생각할 수 있다. 이때 $(E,\; \backslash mathcal\{F\})$는 매트로이드를 형성하며, 이를 그래프 $G$의 그래픽 매트로이드 $M(G)$라고 한다.^[3] 그래픽 매트로이드의 독립 집합은 그래프의 숲이고, 회로는 그래프의 단순 순환(사이클)이다.

그래픽 매트로이드 $M(G)$의 랭크 함수 $r(X)$는 변의 부분 집합 $X$에 대해 $r(X)\; =\; n\; -\; c$로 정의된다. 여기서 $n$은 $X$에 속한 변들로 만들어지는 부분 그래프의 정점 수이고, $c$는 해당 부분 그래프의 연결 요소 개수이다.^[3] 그래픽 매트로이드의 코랭크는 그래프의 회로 랭크(순환수)와 같다.

3. 2. 유한성

4. 표현

그래프 매트로이드는 여러 방식으로 표현될 수 있다. 대표적인 방법 중 하나는 그래프 $G$의 방향 인접 행렬을 이용한 열 매트로이드 표현이다. 이 방식은 행렬의 열 벡터들의 선형 독립 집합을 매트로이드의 독립 집합으로 정의하며, 어떤 체를 사용하든 동일하게 적용된다는 특징이 있다. 따라서 그래프 매트로이드는 모든 가능한 체 위에서 표현 가능한 정규 매트로이드의 한 종류이다.^[3]

또한, 그래프 매트로이드의 플랫 격자는 초평면 배열의 격자로도 나타낼 수 있다. 구체적으로, 그래프 $G$의 정점을 $v\_1,\; \backslash ldots,\; v\_n$이라고 할 때, $e\; =\; v\_i\; v\_j$가 $G$의 모서리일 때마다 초평면 $H\_\{ij\}\; =\; \backslash \{(x\_1,\; \backslash ldots,\; x\_n)\; \backslash in\; \backslash mathbb\{R\}^n\; \backslash mid\; x\_i\; =\; x\_j\backslash \}$를 포함하는 배열로 표현할 수 있다. 이 배열은 대각선 초평면들로 구성된 브레이드 배열의 부분 집합에 해당한다.

4. 1. 인접 행렬 표현

5. 예

무변 그래프의 경우, 그 순환 매트로이드와 접합 매트로이드 둘 다 크기가 0인 유일한 매트로이드이다.

숲 그래프 $T$의 경우, 그 순환 매트로이드는 모든 집합이 독립 집합인 균등 매트로이드 $\backslash operatorname\{Unif\}(\backslash operatorname\; E(T),0)^*$이다. 반면, 그 접합 매트로이드는 공집합만이 독립 집합인 균등 매트로이드 $\backslash operatorname\{Unif\}(\backslash operatorname\; E(T),0)$이다.

순환 그래프 $C\_n$의 경우, 그 순환 매트로이드는 균등 매트로이드 $\backslash operatorname\{Unif\}(\backslash operatorname\; E(C\_n),n-1)$이다. 이는 전체 간선 집합을 제외한 모든 부분 집합이 독립 집합임을 의미한다. 반대로, 그 접합 매트로이드는 균등 매트로이드 $\backslash operatorname\{Unif\}(\backslash operatorname\; E(C\_n),1)$이다.

6. 연결성

매트로이드는 두 개의 더 작은 매트로이드의 직접 합으로 표현될 수 없을 때 연결되었다고 한다. 다시 말해, 매트로이드의 원소 집합을 공집합이 아닌 두 개의 서로소 부분 집합으로 나누었을 때, 원래 매트로이드의 랭크 함수 값이 각 부분 집합의 랭크 합과 같아지는 경우가 존재하지 않으면 그 매트로이드는 연결된 것이다.

그래픽 매트로이드 $M(G)$가 연결되어 있다는 것은, 그 기반이 되는 그래프 $G$가 연결 그래프이면서 동시에 2-정점 연결 그래프라는 것과 같은 의미이다.^[3]

7. 마이너와 쌍대성

매트로이드는 부분 집합을 취하거나 원소를 축약하는 마이너 연산을 통해 더 작은 매트로이드를 만들 수 있다. 또한, 모든 매트로이드 $M$에는 고유한 쌍대 매트로이드 $M^*$가 존재한다.

그래픽 매트로이드와 그 쌍대인 공동 그래픽 매트로이드는 특정 마이너 구조를 통해 특징지어질 수 있다. 어떤 매트로이드가 그래픽 매트로이드인지, 또는 공동 그래픽 매트로이드인지를 판별하는 데에는 금지된 마이너(forbidden minor) 개념이 사용된다. 즉, 특정 종류의 매트로이드를 마이너로 포함하지 않아야 해당 유형의 매트로이드가 될 수 있다.^[3][4][5] 이러한 마이너 조건은 매트로이드가 정규 매트로이드인지 여부와도 관련이 있다.^[6]

7. 1. 평면 그래프와의 관계

8. 알고리즘

그래픽 매트로이드의 최소 가중치 기저는 최소 신장 트리(또는 기본 그래프가 분리된 경우 최소 신장 숲)이다. 최소 신장 트리를 계산하는 알고리즘은 집중적으로 연구되었다. 비교 모델의 계산에서 선형 랜덤 기대 시간으로 문제를 해결하는 방법이 알려져 있으며,^[7] 또는 에지 가중치가 작은 정수이고 비트 단위 연산이 해당 이진 표현에서 허용되는 계산 모델에서 선형 시간으로 해결하는 방법이 알려져 있다.^[8] 결정적 알고리즘에 대해 증명된 가장 빠른 시간 제한은 약간 초선형이다.^[9]

여러 저자가 주어진 매트로이드가 그래픽인지 테스트하는 알고리즘을 연구했다.^[10][11][12] 예를 들어, 터트(Tutte)의 1960년 알고리즘은 입력이 이진 매트로이드인 것으로 알려진 경우 이 문제를 해결한다. 시모어(Seymour)는 1981년에 주어진 집합이 독립적인지 여부를 결정하는 서브루틴인 독립성 오라클을 통해서만 매트로이드에 접근할 수 있는 임의의 매트로이드에 대해 이 문제를 해결했다.

9. 관련 매트로이드

그래프의 잘 알려진 종류로부터 특정 성질을 공유하는 매트로이드의 부류들이 정의되었다. 이러한 정의는 해당 그래프들의 특징을 매트로이드에 대해 더 일반적으로 의미 있는 용어로 표현한 것이다.

• 이분 매트로이드: 모든 회로(cycle)가 짝수 길이를 갖는 매트로이드이다. 그래프 매트로이드의 경우, 해당 그래프가 이분 그래프일 때만 이분 매트로이드가 된다.
• 오일러 매트로이드: 서로소인 회로들로 분할될 수 있는 매트로이드이다. 그래프 매트로이드의 경우, 해당 그래프가 오일러 그래프일 때만 오일러 매트로이드가 된다.

• 강성 매트로이드: 그래프 매트로이드는 1차원 강성 매트로이드의 한 예이다. 강성 매트로이드는 만나는 정점에서 자유롭게 회전할 수 있는 강성 빔 구조의 자유도를 설명하는 매트로이드이다. 1차원에서 이러한 구조의 자유도는 연결된 요소의 수(정점 수 - 매트로이드 랭크)와 같다. 더 높은 차원에서는 ''n''개의 정점을 가진 ''d''차원 구조의 자유도는 ''dn'' - (매트로이드 랭크)로 계산된다. 2차원 강성 매트로이드에서는 라만 그래프가 그래프 매트로이드에서의 신장 숲과 유사한 역할을 한다. 2차원보다 높은 차원의 강성 매트로이드 구조는 아직 잘 알려져 있지 않다.^[14]

참조

_[1] 논문 uses a reversed terminology, in which he called bond matroids "graphic" and cycle matroids "co-graphic", but this has not been followed by later authors.
_[2] 서적 Lattice Theory https://books.google[...] American Mathematical Society
_[3] 간행물 Lectures on matroids https://nvlpubs.nist[...]
_[4] 간행물 On Tutte's characterization of graphic matroids
_[5] 간행물 On Tutte's characterization of graphic matroids—a graphic proof
_[6] 간행물 A homotopy theorem for matroids. I, II
_[7] 간행물 A randomized linear-time algorithm to find minimum spanning trees
_[8] 간행물 Trans-dichotomous algorithms for minimum spanning trees and shortest paths
_[9] 간행물 A minimum spanning tree algorithm with inverse-Ackermann type complexity
_[10] 간행물 An algorithm for determining whether a given binary matroid is graphic.
_[11] 간행물 Converting linear programs to network problems
_[12] 간행물 Recognizing graphic matroids
_[13] 간행물 Euler and bipartite matroids
_[14] 서적 Matroid theory (Seattle, WA, 1995) American Mathematical Society
_[15] 저널인용 Axioms for infinite matroids 2013-06-01