마트로이드 단조

매트로이드의 수학적 이론에서 매트로이드 M의 단위는 제한과 수축 연산의 순서에 의해 M으로부터 얻어지는 또 다른 매트로이드 N이다.매트로이드 미성년자는 그래프 미성년자와 밀접한 관계가 있으며, 이들이 형성되는 제한 및 수축 연산은 그래프에서 가장자리 삭제 및 가장자리 수축 연산에 해당한다.매트로이드 미성년자 이론은 그래프의 해당 이론과 유사하게, 금지된 미성년자에 의한 매트로이드 가족의 구조적인 분해와 특성화로 이어진다.

정의들

만약 M이 세트 E의 매트로이드이고 S가 E의 서브셋이라면, M에서 S로 쓰여진 M의 제한은 세트 S의 매트로이드로서, 독립 세트는 S에 포함된 M의 독립 세트다.그것의 회로는 S에 포함된 M의 회로이고 그것의 순위 기능은 S의 서브셋으로 제한된 M의 회로다.

T가 E의 독립적인 부분집합인 경우, M/T로 작성된 M by T에 의한 M의 수축은 M에서 T와의 결합이 독립된 집합인 기본 집합 E - T의 매트리스다.이 정의는 T에 대한 근거를 선택하고 이 기준과의 결합이 M에서 독립적으로 유지되는 경우 수축에서 독립적일 집합을 정의함으로써 임의 T로 확장될 수 있다.${\displaystyle \mathrm{수축}}$의 순위 함수는 $r{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( A${\displaystyle }$)${\displaystyle }$= ${\displaystyle r}$( ${\displaystyle A}$ ${\displaystyle \cup }$ T${\displaystyle }$)${\displaystyle }$- ${\displaystyle r}$( T${\displaystyle }$)${\displaystyle }$. ${\디스플레이스타일 r'(A)=r(A\컵$ T$)-r(T$)이다$.$$}$

Matroid N은 제한 및 수축 연산에 의해 M에서 생성될 수 있는 경우 Matroid M의 부전이다.

매트로이드의 평면에 의해 형성된 기하학적 격자로 볼 때, 매트로이드의 마이너를 취하는 것은 주어진 하한 원소와 상한 원소 사이에 놓여 있는 격자의 부분인 격자의 간격을 취하는 것에 해당한다.^[1]

금지된 매트로이드 특성화

많은 중요한 모성애 가족은 미성년자 복용 수술로 문을 닫는다: 만약 모성애 M이 가족이라면, M의 모든 미성년자도 가족에 속한다.이 경우 가문은 가문에 속하지 않는 소소수 모종인 '포기된 모종'의 집합으로 특징지어질 수 있다.모항은 미성년자로서 금지된 모항모형을 가지고 있지 않은 경우에만 가족에 속한다.종종, 그러나 항상은 아니지만, 금지된 모성애들의 집합은 한정적이어서, 로버슨-과 유사하다.마이너 클로즈드 그래프 계열의 금지된 미성년자 집합은 항상 유한하다는 것을 명시하는 세이모어 정리.

이러한 현상의 예는 모든 분야에 걸쳐 대표할 수 있는 일반 매트로이드, 매트로이드에 의해 제시된다.등가적으로 행렬은 완전히 비모형 행렬(제곱 하위 행렬이 모두 0, 1 또는 -1과 같은 결정 인자를 갖는 행렬)로 나타낼 수 있는 경우 정규적이다.투테(1958)는 세 가지 금지된 미성년자 중 하나, 즉 균일한 매트로이드 $U{\displaystyle }$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{\mathrm{}}^{}}$ ${\$ U${}_{4}^{2$}}($$4점선), 파노 평면 또는 파노 평면의 이중 매트로이드 중 하나를 가지고 있지 않은 경우에만 매트로드가 규칙적이라는 것을 증명했다.이를 위해 그는 어려운 호모토피 정리를 사용했다.그 이후로 더 간단한 증거가 발견되었다.

그래픽 매트로이드, 독립된 세트가 그래프의 숲 하위그래프인 매트로이드에는 5개의 금지된 미성년자가 있다: 일반 매트로이드에 대한 3개, 바그너의 정리에 의해 금지된₅ 그래프 K와_3,3 K에 대한 그래픽 매트로이드의 2개 이중은 평면 그래프의 금지된 미성년이다.

2요소 유한장에 걸쳐 표현할 수 있는 2진성 매트로이드(matroids)는 그래픽과 일반 매트로이드는 그래픽과 일반 매트로이드를 모두 포함한다.Tutte는 이러한 모성애들이 금지된 사소한 특성을 가지고 있다는 것을 다시 보여주었다: 그들은 미성년자로서 4점선을 가지고 있지 않은 모성애들이다.로타는 어떤 한정된 분야에서든 그 분야에 걸쳐 대표할 수 있는 모성애들은 분명히 금지된 미성년자들을 많이 가지고 있다고 추측했다.^[2]Geelen, Gerards, Wittle에 의해 이 추측에 대한 완전한 증거가 발표되었다;^[3] 2015년^[update] 현재 그것은 나타나지 않았다.그러나 실수에 걸쳐 대표될 수 있는 매트로이드는 금지된 미성년자가 무한히 많다.^[4]

분기폭

매트로이드의 분기는 그래프에 대한 정의와 유사하게 정의될 수 있다.매트로이드의 가지 형태는 매트로이드 원소의 계층적 군집화로서, 잎에 매트로이드 원소를 가진 뿌리 없는 이진수로 표현된다.이 트리의 가장자리를 제거하면 매트로이드가 두 개의 분리 하위 집합으로 분할된다. 그러한 분할을 e-분리라고 한다.r이 매트로이드의 순위 함수를 나타내는 경우, e-분리 폭은 r(A) + r(B) - r(M) + 1로 정의된다. 분해 폭은 e-분할의 최대 폭이며, 매트로이드의 분기 폭은 분기 결합의 최소 폭이다.

그래프의 분기폭과 해당 그래픽 매트로이드의 분기폭은 다를 수 있다. 예를 들어, 3-엣지 경로 그래프와 3-엣지 별의 분기폭은 각각 2와 1이지만, 둘 다 분기폭 1과 동일한 그래픽 매트로드를 유도한다.^[5]그러나 트리가 아닌 그래프의 경우 그래프의 분기 너비는 연관된 그래픽 매트로이드의 분기 너비와 동일하다.^[6]매트로이드의 분기 폭은 항상 이중의 분기 폭과 동일하다.^[5]

가지폭은 그래프 미성년자 이론을 모체까지 확장하려는 시도의 중요한 구성 요소인데, 나무폭은 또한 모체로 일반화될 수 있고,^[7] 그래프 미성년자 이론에서 가지폭보다 더 큰 역할을 하지만, 가지폭은 모체 설정에서 더 편리한 특성을 가지고 있다.^[8]유한한 분야에 걸쳐 표현 가능한 마이너 폐쇄형 매트로이드 패밀리가 모든 평면 그래프의 그래픽 매트로이드를 포함하지 않는 경우, 패밀리의 매트로이드 분기폭에 일정한 한계가 있어 마이너 폐쇄형 그래프 패밀리에 대해서도 유사한 결과가 일반화된다.^[9]

웰 준주문

더 로버슨-시모어 정리는 금지된 미성년자 리스트로 특징지어지는 그래픽 매트로이드의 모든 매트로이드 성질은 유한한 리스트로 특징지어질 수 있음을 암시한다.같은 말을 하는 또 다른 방법은 경미한 조작으로 형성된 그래픽 매트로이드에 대한 부분적인 순서가 준주문이라는 것이다.그러나, 금지된 미성년자를 무한히 많이 가지고 있는 진짜 대표성 있는 모성애들의 예를 보면, 사소한 주문은 모든 모성애에 대해 잘 준주문이 아니라는 것을 알 수 있다.

로버슨과 시모어는 어떤 특정한 유한한 분야에 걸쳐 대표할 수 있는 매트로이드가 잘 정리되어 있다고 추측했다.지금까지 이것은 경계가 있는 가지폭의 매트로이드에 대해서만 증명되었다.^[10]

마트로이드 분해

그래프 구조 정리는 그래프 미성년자 이론에서 중요한 도구로, 이에 따라 마이너 폐쇄 계열의 그래프는 클릭-섬 연산에 의해 더 단순한 그래프에서 만들어질 수 있다.일부 유사한 결과는 모태론에서도 알려져 있다.특히 세이모어의 분해 정리는 모든 일반 매트로이드가 그래픽 매트로이드의 클릭섬, 그 이중, 그리고 하나의 특별한 10요소 매트로이드로서 간단한 방법으로 빌드될 수 있다고 기술하고 있다.^[11]그 결과, 이 분해의 그래픽 부분과 동그래픽 부분에 해당하는 최소 신장 트리 문제에 대한 해결책을 결합하여 완전히 단변형 매트릭스에 의해 정의된 선형 프로그램을 조합하여 해결할 수 있다.

알고리즘 및 복잡성

그래프 부설 이론의 중요한 요소 중 하나는 다른 그래프 G의 부설인지 여부를 시험하기 위한 알고리즘의 존재로서, H의 고정 선택에 대해 G에서 다항식인 시간을 (그리고 H의 크기가 다양하도록 허용될 경우 보다 강하게 고정된 매개변수를 추적할 수 있는) 것이다.이 결과를 로버트슨과 결합함으로써시모어 정리, 다항식 시간에 어떤 마이너 클로즈드 그래프 계열의 구성원을 인식하는 것이 가능하다.이에 상응하여, 매트로이드 이론에서, 주어진 고정 매트로드가 입력 매트로이드의 마이너인지 여부를 인식하기 위한 효율적인 알고리즘을 개발하는 것이 바람직할 것이다.불행히도 그렇게 강한 결과는 가능하지 않다. 다항식 Oracle 모델에서 다항식 시간에 인식할 수 있는 유일한 미성년자는 계급이나 코랭크가 1인 균일한 모항이다.^[12]그러나 문제가 일부 고정된 유한장(그리고 그장 위에 행렬로 표현)에 걸쳐 표현 가능한 매트로이드로 제한된다면, 그래프 사례에서처럼 다항식 시간에 고정된 마이너를 포함하는 매트로이드를 인식할 수 있을 것으로 추측된다.^[8]

메모들

참조