매트로이드 마이너

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

1. 개요
2. 정의
3. 성질
4. 알고리즘 및 복잡도
참조

1. 개요

매트로이드 마이너는 주어진 매트로이드에서 제한과 축약 연산을 반복하여 얻을 수 있는 매트로이드를 의미한다. 매트로이드의 부분 집합으로의 제한은 해당 부분 집합의 독립 집합을 포함하는 매트로이드를 생성하며, 축약은 쌍대 매트로이드의 제한의 쌍대 매트로이드를 구성하는 연산이다. 매트로이드 마이너 관계는 그래프 마이너의 일반화이며, 그래프 마이너는 순환 매트로이드의 마이너로 표현될 수 있다. 매트로이드 마이너는 정렬 원순서를 이루지 않지만, 그래프 순환 매트로이드에서는 정렬 원순서를 이룬다. 많은 매트로이드 집합은 마이너 연산에 대해 닫혀 있으며, 이를 통해 금지된 마이너를 사용하여 해당 집합을 특성화할 수 있다. 매트로이드의 분기 폭은 매트로이드 마이너 이론에서 중요한 개념이며, 매트로이드 분해는 매트로이드 구조를 이해하는 데 도움이 된다. 특정 매트로이드가 다른 매트로이드의 마이너인지 판별하는 문제는 일반적으로 어렵지만, 고정된 유한체에서 표현 가능한 매트로이드로 제한하면 효율적인 알고리즘이 존재할 가능성이 있다.

더 읽어볼만한 페이지

매트로이드 이론 - 탐욕 알고리즘
탐욕 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 알고리즘 설계 패러다임으로, 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 최적의 해를 보장하며, 다익스트라, 프림, 크루스칼 알고리즘 등에 사용된다.
매트로이드 이론 - 안둘레
안둘레는 그래프 이론에서 가장 짧은 사이클의 길이를 나타내며, 사이클이 없는 그래프는 무한대의 안둘레를 갖고, 그래프의 연결도, 접합 크기, 밖둘레와 관련되어 그래프 채색과 확장성 분석, 그리고 케이지 연구에 활용된다.

매트로이드 마이너
정의
설명	매트로이드 이론에서 매트로이드의 마이너는 다음 연산을 임의의 순서로 여러 번 수행하여 얻을 수 있는 매트로이드이다.
연산	축소: 매트로이드에서 요소를 제거한다. 삭제: 매트로이드에서 요소를 축약한다.
참고 자료
참고 문헌	Welsh, Dominic (1976), Matroid Theory, L.M.S. Monographs, No. 8, London: Academic Press, ISBN 0-12-744760-4, MR 0487279 Oxley, James (1992), Matroid Theory, Oxford Science Publications, Oxford: Clarendon Press, ISBN 0-19-853563-5, MR 1207587

2. 정의

매트로이드에서 일부 원소를 삭제하거나 축약하여 얻을 수 있는 새로운 매트로이드를 매트로이드 마이너라고 정의한다.^[10]

(유한 또는 무한) 매트로이드 $(X,\mathcal I)$ 가 주어졌을 때, 그 부분 집합 $S\subseteq X$ 에 대하여, $X$ 를 $S$ 로 축약하여 얻는 매트로이드는 다음과 같이 정의된다.

: $X.S = (X^*\restriction S)^*=\left(S,\bigcup_{B\in\max\mathcal I}\operatorname{Pow}(S\setminus B)\right)$

여기서 $\operatorname{Pow}(-)$ 는 멱집합을 뜻하며, 이 과정은 $X\setminus S$ 를 '''축약'''(contraction^영어)하는 것이다.

2. 1. 제한 (Restriction)

(유한 또는 무한) 매트로이드

(X,\mathcal I)

가 주어졌을 때, 그 부분 집합

S\subseteq X

에 대하여,

:

X\restriction S=(S,\{I\cap S\}_{I\in\mathcal I})

역시 매트로이드를 이룬다.^[10] 이를

X

의

S

로의 '''제한'''이라고 한다. (즉, 이 과정은

X\setminus S

의 '''삭제'''(deletion|딜리션^영어)이다.)

만약 ''M''이 집합 ''E'' 위의 매트로이드이고 ''S''가 ''E''의 부분 집합이면, ''M''을 ''S''로 제한한 것, 즉 ''M'' |''S''는 ''S''의 독립 집합이 ''S''에 포함된 ''M''의 독립 집합인 집합 ''S'' 위의 매트로이드이다. 회로는 ''S''에 포함된 ''M''의 회로이며, 랭크 함수는 ''S''의 부분 집합으로 제한된 ''M''의 랭크 함수이다.

2. 2. 축약 (Contraction)

매트로이드 ''M''의 부분집합 ''T''에 대한 축약 ''M''/''T''는 ''T''와의 합집합이 ''M''에서 독립적인 집합들을 갖는 매트로이드이다. 이 정의는 임의의 ''T''에 대해 ''T''의 기저를 선택하고 이 기저와의 합집합이 ''M''에서 독립적인 경우 축약에서 집합을 독립적으로 정의하여 확장할 수 있다. 축약의 랭크 함수는 다음과 같다.

:

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

^[10]

2. 3. 마이너 (Minor)

(유한 또는 무한) 매트로이드

(X,\mathcal I)

가 주어졌을 때, 그 부분 집합

S\subseteq X

에 대한 제한

X\restriction S

와 축약

X.S = (X^*\restriction S)^*

을 정의할 수 있다. 제한은

X

에서

S

에 포함되지 않는 원소를 '''삭제'''하는 것이고, 축약은

X

에서

S

에 포함되지 않는 원소를 '''축약'''하는 것이다.

제한과 축약을 반복하여 얻는 매트로이드

(X',\mathcal I')

(

X'\subseteq X

)를

X

의 '''마이너'''라고 한다.^[10]

매트로이드 ''M''이 집합 ''E'' 위에 있고, ''S''가 ''E''의 부분 집합이면, ''M''을 ''S''로 제한한 ''M'' |''S''는 ''S'' 위의 매트로이드가 된다. 이때 ''S''의 독립 집합은 ''S''에 포함된 ''M''의 독립 집합이다. ''M''의 회로는 ''S''에 포함된 ''M''의 회로이며, 랭크 함수는 ''S''의 부분 집합으로 제한된 ''M''의 랭크 함수이다.

''T''가 ''E''의 독립 부분 집합이면, ''M''을 ''T''로 수축한 ''M''/''T''는 기본 집합 ''E − T'' 위의 매트로이드가 된다. 이때 독립 집합은 ''T''와의 합집합이 ''M''에서 독립적인 집합이다. 수축의 랭크 함수는

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

이다.

어떤 매트로이드 ''N''이 제한 및 수축 연산을 통해 ''M''으로부터 구성될 수 있다면, ''N''은 ''M''의 마이너가 된다.

3. 성질

매트로이드 마이너는 원래 매트로이드의 여러 성질을 보존하거나 특정한 방식으로 변화시킨다. 그래프 마이너는 매트로이드 마이너의 특수한 경우로, 그래프에서 변을 삭제하거나 축약하는 것은 순환 매트로이드에서 원소를 삭제하거나 축약하는 것과 같다. 홑 꼭짓점 삭제는 순환 매트로이드에 영향을 주지 않는다.

유한 그래프의 그래프 마이너 관계는 정렬 원순서를 이루지만, 모든 유한 매트로이드에서는 그렇지 않다. 로버트슨-세이무어 정리는 금지된 마이너 목록으로 특징지어지는 그래픽 매트로이드 속성이 유한한 목록으로 특징지어질 수 있음을 보여준다. 그러나 실수 표현 가능 매트로이드는 무한히 많은 금지된 마이너를 가지므로, 마이너 순서가 모든 매트로이드에 대해 잘 준 순서가 아니다.

정규 매트로이드는 완전 단일 모듈 행렬로 표현 가능하며, 터트는 세 개의 금지된 마이너를 가지지 않는 경우에만 정규임을 증명했다. 그래픽 매트로이드는 다섯 개의 금지된 마이너를, 이진 매트로이드는 4점 선을 마이너로 가지지 않는다. 로타 추측은 모든 유한체에 대해 해당 체에서 표현 가능한 매트로이드가 유한 개의 금지된 마이너를 갖는다고 추측했으며,^[1] 2014년에 증명되었지만 출판되지는 않았다.^[2]

분기 분해는 매트로이드 원소를 계층적 군집화하여 이진 트리로 표현한 것이다. 분해의 폭은 모든 e-분할의 최대 폭이며, 매트로이드 분기 폭은 모든 분기 분해의 최소 폭이다. 그래프 분기 폭과 해당 그래픽 매트로이드 분기 폭은 다를 수 있지만, 트리가 아닌 그래프의 경우에는 같다.^[3] 매트로이드 분기 폭은 항상 그 쌍대의 분기 폭과 같다.^[4]

세이모어의 분해 정리는 모든 정규 매트로이드가 그래픽 매트로이드, 그 쌍대 매트로이드 및 특수한 10개 원소 매트로이드의 클리크 합으로 구성될 수 있다고 설명한다.^[9]

3. 1. 그래프와의 관계

그래프 마이너는 매트로이드 마이너의 특수한 경우이다. 그래프

\Gamma

의 순환 매트로이드를

\operatorname M(\Gamma)

라고 할 때, 임의의 변의 집합

S\subseteq\operatorname M(\Gamma)

에 대해 다음이 성립한다.

:

\operatorname M(\Gamma\restriction S)=\operatorname M(\Gamma)\restriction S

:

\operatorname M(\Gamma.S)=\operatorname M(\Gamma).S

:

\operatorname M(\Gamma\sqcup K_0) = \operatorname M(\Gamma)

이는 다음을 의미한다.

그래프에서 $S$ 에 속하지 않는 변을 삭제하는 것은 순환 매트로이드에서 $S$ 에 속하지 않는 원소를 삭제하는 것과 같다.
그래프에서 $S$ 에 속하지 않는 변을 축약하는 것은 순환 매트로이드에서 $S$ 에 속하지 않는 원소를 축약하는 것과 같다.
그래프에서 홑 꼭짓점(아무 변과 결합하지 않는 꼭짓점)을 삭제하는 것은 순환 매트로이드에 영향을 주지 않는다.

따라서 그래프의 순환 매트로이드의 매트로이드 마이너는 그래프 마이너의 순환 매트로이드이다.

3. 2. 정렬 원순서 (Well-quasi-ordering)

유한 그래프의 그래프 마이너 관계는 정렬 원순서를 이룬다(로버트슨-시모어 정리). 즉, 유한 그래프의 순환 매트로이드로 국한했을 때, 매트로이드 마이너 관계는 정렬 원순서를 이룬다.

그러나 모든 유한 매트로이드의 집합 위에서 매트로이드 마이너 관계는 정렬 원순서를 이루지 못한다. 로버트슨-세이무어 정리는 금지된 마이너 목록으로 특징지어지는 모든 그래픽 매트로이드의 매트로이드 속성이 유한한 목록으로 특징지어질 수 있음을 암시한다. 다르게 표현하면, 마이너 연산으로 형성된 그래픽 매트로이드에 대한 반순서는 잘 준 순서라는 것이다. 그러나 무한히 많은 금지된 마이너를 갖는 실수 표현 가능 매트로이드의 예는 마이너 순서가 모든 매트로이드에 대해 잘 준 순서가 아님을 보여준다.

로버트슨과 세이무어는 특정 유한체 위에서 표현 가능한 매트로이드가 잘 준 순서가 될 것이라고 추측했다. 지금까지는 분지폭이 제한된 매트로이드에 대해서만 이것이 증명되었다.^[8]

3. 3. 금지된 매트로이드 특성화 (Forbidden matroid characterizations)

많은 중요한 매트로이드 집합은 마이너를 취하는 연산에 대해 닫혀 있다. 즉, 매트로이드 ''M''이 집합에 속하면 ''M''의 모든 마이너도 집합에 속한다. 이 경우, 집합은 해당 집합에 속하지 않는 마이너 최소 매트로이드인 "금지된 매트로이드"의 집합으로 특징지을 수 있다. 매트로이드는 금지된 매트로이드를 마이너로 가지지 않는 경우에만 집합에 속한다.

이러한 현상의 예는 모든 체에서 표현 가능한 매트로이드인 정규 매트로이드에 의해 제공된다. 동등하게, 매트로이드는 완전 단일 모듈 행렬(모든 정방 부분 행렬이 0, 1 또는 -1과 같은 행렬식 값을 갖는 행렬)로 표현할 수 있는 경우 정규이다. 터트(1958)는 매트로이드가 세 개의 금지된 마이너 중 하나, 즉 균등 매트로이드

U{}^2_4

(4점 선), 파노 평면, 또는 파노 평면의 쌍대 매트로이드를 가지지 않는 경우에만 정규임을 증명했다. 이를 위해 그는 어려운 호모토피 정리를 사용했다. 이후 더 간단한 증명이 발견되었다.

그래픽 매트로이드는 독립 집합이 그래프의 숲 부분 그래프인 매트로이드이며, 다섯 개의 금지된 마이너를 갖는다. 이는 정규 매트로이드에 대한 세 개와, 바그너 정리에 따라 평면 그래프에 대한 금지된 마이너인 그래프 ''K''₅ 및 ''K''_3,3에 대한 그래픽 매트로이드의 두 개의 쌍대 매트로이드이다.

이진 매트로이드는 두 개의 원소를 갖는 유한체에서 표현 가능한 매트로이드이며, 그래픽 매트로이드와 정규 매트로이드를 모두 포함한다. 터트는 다시 이 매트로이드가 금지된 마이너 특성을 갖는다는 것을 보여주었다. 즉, 4점 선을 마이너로 가지지 않는 매트로이드이다. 로타 추측은 모든 유한체에 대해, 해당 체에서 표현 가능한 매트로이드가 유한 개의 금지된 마이너를 갖는다고 추측했다.^[1] 이 추측의 증명은 2014년에 Geelen, Gerards 및 Whittle에 의해 발표되었지만 출판되지는 않았다. 실수로 표현할 수 있는 매트로이드는 무한히 많은 금지된 마이너를 갖는다.^[2]

3. 4. 분지 분해 (Branch decomposition)

분기 분해는 그래프에 대한 정의와 유사하게 매트로이드에 대해 정의될 수 있다.

매트로이드의 분기 분해는 매트로이드의 원소를 계층적 군집화하여 나타낸 것으로, 매트로이드의 원소를 잎으로 갖는 무방향 이진 트리로 표현된다. 이 트리의 임의의 모서리를 제거하면 매트로이드는 두 개의 서로소인 부분 집합으로 분할되는데, 이러한 분할을 e-분할이라고 한다. ''r''이 매트로이드의 랭크 함수를 나타내는 경우, e-분할의 폭은 ''r''(''A'') + ''r''(''B'') - ''r''(''M'') + 1로 정의된다. 분해의 폭은 모든 e-분할의 최대 폭이며, 매트로이드의 분기 폭은 모든 분기 분해의 최소 폭이다.

그래프의 분기 폭과 해당 그래픽 매트로이드의 분기 폭은 다를 수 있다. 예를 들어, 세 개의 모서리를 가진 경로 그래프와 세 개의 모서리를 가진 별은 분기 폭이 각각 2와 1로 다르지만, 분기 폭이 1인 동일한 그래픽 매트로이드를 유도한다.^[4] 그러나 트리가 아닌 그래프의 경우, 그래프의 분기 폭은 해당 그래픽 매트로이드의 분기 폭과 같다.^[3] 매트로이드의 분기 폭은 항상 그 쌍대(dual)의 분기 폭과 같다.^[4]

3. 5. 매트로이드 분해 (Matroid decompositions)

그래프 구조 정리와 유사하게, 매트로이드 이론에서도 비슷한 결과가 알려져 있다. 특히 세이모어의 분해 정리는 모든 정규 매트로이드가 그래픽 매트로이드, 그 쌍대 매트로이드 및 하나의 특수한 10개 원소 매트로이드의 클리크 합으로 간단하게 구성될 수 있다고 설명한다.^[9] 결과적으로, 완전 단일 모듈 행렬로 정의된 선형 계획법은 이 분해의 그래픽 부분과 공그래픽 부분에 해당하는 일련의 최소 스패닝 트리 문제에 대한 해를 결합함으로써 조합적으로 해결될 수 있다.

4. 알고리즘 및 복잡도

그래프 마이너 이론에서 중요한 부분 중 하나는 어떤 그래프 ''H''가 다른 그래프 ''G''의 마이너인지 검사하는 알고리즘의 존재이다. 이 알고리즘은 고정된 ''H''에 대해 ''G''에 대한 다항 시간 내에 수행될 수 있다. (''H''의 크기가 변동할 수 있는 경우에는 더 강력하게 고정 매개변수 처리 가능하다). 이 결과와 로버트슨-세이모어 정리를 결합하면, 모든 마이너-닫힌 그래프족의 구성원을 다항 시간 내에 인식할 수 있다.

마찬가지로, 매트로이드 이론에서도 주어진 고정 매트로이드가 입력 매트로이드의 마이너인지 효율적으로 판별하는 알고리즘을 개발하는 것이 바람직하다. 그러나 불행하게도, 이렇게 강력한 결과는 불가능하다. 매트로이드 오라클 모델에서 다항 시간 내에 인식할 수 있는 유일한 마이너는 랭크 또는 코랭크가 1인 균일 매트로이드이다.^[6]

하지만, 문제가 어떤 고정된 유한체 위에서 표현 가능한 매트로이드로 제한되고, 그 체 위에서 행렬로 표현되는 경우, 그래프의 경우와 마찬가지로 어떤 고정된 마이너를 포함하는 매트로이드를 다항 시간 내에 인식하는 것이 가능할 것으로 추측된다.^[6]

참조

_[1] 논문
_[2] 논문
_[3] 논문
_[4] 논문
_[5] 논문
_[6] 논문
_[7] 논문
_[8] 논문
_[9] 논문
_[10] 저널 Axioms for infinite matroids 2013-06-01

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

문의하기 : help@durumis.com