그래프 부차

그래프 이론에서, 가장자리와 정점을 삭제하고 가장자리를 수축시킴으로써 G에서 H를 형성할 수 있다면, 비방향 그래프 H를 그래프 G의 부차라고 부른다.

그래프 미성년자 이론은 그 미성년자가 완전한 그래프 K와₅ 완전한 양분 그래프 K를_3,3 포함하지 않는 경우에만 그래프가 평면이라는 바그너의 정리에서 시작되었다.^[1]더 로버슨-세이모어 정리는 삭제와 가장자리 수축에 의해 보존되는 그래프의 모든 특성에 대해 유사하게 금지된 사소한 특성화가 존재함을 암시한다.^[2]모든 고정 그래프 H에 대해, H가 다항식 시간에 입력 그래프 G의 부차인지 여부를 테스트할 수 있다.^[3] 금지된 부차적 문자와 함께, 이것은 삭제와 수축을 통해 보존된 모든 그래프 속성이 다항식 시간에 인식될 수 있음을 의미한다.^[4]

그래프 마이너와 관련된 다른 결과와 추측에는 그래프 구조 정리가 있는데, 이에 따라 마이너로서 H가 없는 그래프는 더 단순한 조각을 붙여서 형성될 수 있고, 하드와이거의 추측에는 그래프를 마이너로서 큰 전체 그래프의 존재에 색칠할 수 없는 것과 관련이 있다.그래프 미성년자의 중요한 변형은 위상학적 미성년자와 몰입적 미성년자를 포함한다.

정의들

가장자리 수축은 그래프에서 가장자리를 제거하는 동시에 그래프에서 가장자리가 연결될 때 사용한 두 꼭지점을 동시에 병합하는 연산이다.일부 가장자리를 수축하고 일부 가장자리를 삭제하며 일부 절연 정점을 삭제하여 G에서 그래프가 H에 대해 이형성을 얻을 수 있다면 비방향 그래프 H는 또 다른 비방향 그래프 G의 부차다.G에서 그러한 수축과 삭제의 순서가 수행되는 순서는 결과 그래프 H에 영향을 미치지 않는다.

그래프 미성년자는 종종 모태성 미성년자의 보다 일반적인 맥락에서 연구된다.이러한 맥락에서, 모든 그래프가 자체 루프와 다중 에지(즉, 단순한 그래프보다는 다중 그래프)가 허용되며, 루프의 수축과 컷 에지 삭제가 금지된 작업이라고 가정하는 것이 일반적이다.이러한 관점은 가장자리 삭제는 그래프 순위를 변경하지 않고, 가장자리 수축은 항상 순위를 하나씩 감소시킨다는 장점이 있다.

다른 맥락(예: 사이비 숲 연구)에서는, 컷 에지 삭제를 허용하고, 분리된 그래프는 허용하되, 다중 글자는 금지하도록 하는 것이 더 타당하다.그래프 부차 이론의 이러한 변화에서, 그래프는 항상 가장자리 수축 후에 단순화되어 자기 루프와 다중 가장자리를 제거한다.^[5]

함수 f는 H가 G의 마이너일 때마다 f(H) ≤ f(G)가 있으면 "minor-monotone"이라고 한다.

예

다음 예제에서 그래프 H는 그래프 G의 부차다.

H.

G.

다음 도표는 이를 예시한다.먼저 파선된 가장자리(그리고 그에 따른 절연된 꼭지점)를 삭제하여 G의 하위 그래프를 생성한 다음 회색 가장자리를 수축(연결되는 두 정점):

주요 결과와 추측

유한 비직접 그래프의 이형성 등급에 대해 그래프 마이너 관계가 전이성(G의 마이너는 G 자체의 마이너)이고, 비직렬 마이너 연산은 가장자리나 정점을 제거하기 때문에 이형성인 경우 G와 H는 서로의 미성년자만 될 수 있다는 것을 확인하는 것은 간단하다.닐 로버트슨과 폴 시모어에 의해 깊은 결과는 이 부분 순서는 실제로 well-quasi-ordering:유한 그래프의 무한 목록-G1G2,..., 그러면 언제나 나는 < 두 지수의 존재, Gj의 j가 기는 미성년자이라고 말한다.이 나타내는 또 다른 동등한 방법은 그래픈한 일련의 최소한의 e.의는 한정을 할 수 있다는 것하급 ^[6]계약이 결과는 클라우스 바그너 이후 바그너의 추측으로 알려진 추측을 증명했다; 바그너는 오래 전에 그것을 추측했었지만 1970년에야 그것을 발표했다.^[7]

시모어와 로버튼은 또한 증거 과정에서 어떤 고정 그래프 H에 대해서도 H를 부차적으로 가지고 있지 않은 그래프의 대략적인 구조를 결정하는 그래프 구조 정리를 증명한다.정리의 문장은 그 자체로 길고 관여하지만, 간단히 말해서 그러한 그래프는 경계 속 표면에 내장된 그래프로부터 작은 방법으로 수정된 작은 그래프의 집단-섬 구조를 가져야 한다는 것을 확립한다.따라서, 그들의 이론은 그래프 미성년자와 그래프의 위상학적 내장 사이에 근본적인 연관성을 확립한다.^[8]

모든 그래프 H의 경우, 단순 H-미너 프리 그래프는 희박해야 하며, 이는 에지 수가 정점 수의 일정한 배수보다 작다는 것을 의미한다.^[9]보다 구체적으로, H에 정점이 있다면, 간단한 n-vertex 단순 H-minor-free 그래프에는 최대 $O{\displaystyle (n}$ h ${\displaystyle \sqrt{\log }}$log $){\$ style $O(nh{\sqrt {\log$ h$})$ 에지가$$ 있을 수 있으며, 일부 K-minor-free_h 그래프에는 최소한 이 많은 에지가 있을 수 있다.^[10]Thus, if H has h vertices, then H-minor-free graphs have average degree ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ and furthermore degeneracy ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$. Additionally, the H-minor-free graphs have a separator theorem similar to the planar sepa평면 그래프의 라이터 정리: 모든 고정 H 및 n-vertex H-minor-free 그래프 G의 경우, 제거가 G를 서브그래프당 최대 2n/3 vertes로 두 개(잠길 수 있음) 하위그래프로 분할하는 $O{\displaystyle }$($){\$ 정점의$$ 부분 집합을 찾을 수 있다.^[11]더욱 강력한 것은 고정 H의 경우 H-minor-free 그래프에 트리 $너비{\displaystyle }$ O${\displaystyle (n\sqrt{}}$ $){\$ O$({\sqrt{n})}$가 있다는 점이다$.$^[12]

그래프 이론의 하드와이거 추측은 그래프 G가 k 정점의 완전한 그래프에 부등형 이형성을 포함하지 않으면 G가 k - 1 색상으로 적절한 색상을 갖는다는 것을 제안한다.^[13]사례 k = 5는 4색 정리의 재작성이다.하드와이거의 추측은 k≤ 6에 대해 증명되었지만,^[14] 일반적인 경우에는 알려져 있지 않다.볼로바스, 캐틀린 & 에르드스(1980년)는 이것을 "그래프 이론에서 가장 깊은 미해결 문제 중 하나"라고 부른다.미성년자를 그래프로 표시하는 4색 정리와 관련된 또 다른 결과는 로버슨, 샌더스, 시모어, 토머스가 발표한 스나크 정리인데, W. T. Tutte가 추측한 4색 정리의 강화와 가장자리 색상에서 4색을 필요로 하는 브릿지리스 3정형 그래프는 반드시 피터슨 그래프를 마이너로서 가져야 한다고 명시하고 있다.^[15]

부 닫힌 그래프 패밀리

많은 그래프 패밀리는 F에 있는 모든 그래프의 마이너도 F에 있는 속성을 가지고 있다. 그러한 클래스는 마이너 클로즈드라고 한다.예를 들어, 모든 평면 그래프 또는 고정 위상학적 표면에 그래프를 내장하는 경우, 가장자리 제거나 가장자리 수축은 내장 속(sinner-closed family)을 증가시킬 수 없다. 따라서 고정 표면에 내장할 수 있는 평면 그래프와 그래프는 마이너-폐쇄 패밀리를 형성한다.

F가 마이너 클로즈드 패밀리인 경우, F에 속하지 않는 그래프 중 (미성년자의 준주문 속성 때문에) 유한 집합 X가 있다.이러한 그래프는 F에 대해 금지된 미성년자: X의 그래프를 마이너 그래프로 포함하지 않는 경우에만 그래프가 F에 속한다.즉, 모든 마이너 클로즈드 패밀리 F는 금지된 미성년자의 일부 유한 집합 X에 대해 X-미너 프리 그래프의 패밀리로 특징지어질 수 있다.^[2]이러한 유형의 특성화의 가장 잘 알려진 예는 평면 그래프를 마이너로서 K도₅ K도_3,3 가지지 않은 그래프로 특징짓는 바그너의 정리다.^[1]

일부의 경우, 마이너 폐쇄 계열의 그래프의 속성은 제외된 미성년자의 속성과 밀접하게 연관될 수 있다.예를 들어 한minor-closed 그래프 가족 Fpathwidth을 경계했다 만일 그 금지된 미성년자 포함한 forest,[16]F이 경계 tree-depth 만일 그것의 금지된 미성년자 등이 차갑노조의 경로 그래프, F이 경계 treewidth 만일 그것의 금지된 미성년자 포함한 평면 graph,[17]와 F이 경계 지역 treewidth 'caput'도유직경과 나무 폭 사이의 관계) 금지된 미성년자가 정점 그래프(단일 정점을 제거하여 평면도를 만들 수 있는 그래프)를 포함하는 경우에만 해당된다.^[18]단 하나의 교차점(즉, 1번 교차점이 있음)만으로 평면에서 H를 그릴 수 있다면 H-미노르 프리 그래프는 평면 그래프와 경계 트리 폭의 그래프의 집단 합으로 형성되는 단순화된 구조 정리가 있다.^[19]예를 들어 K와₅ K 모두_3,3 넘버원을 가지고 있는데, 바그너가 보여준 것처럼 K-프리₅ 그래프는 평면 그래프의 3-클릭 합과 8-버텍스 바그너 그래프인 반면, K-프리_3,3 그래프는 평면 그래프와₅ K의 2-클릭 합이다.^[20]

변형

위상학적 미성년자

G의 서브그래프에 대해 H의 하위구분이 이형인 경우 그래프 G의 위상학적 부차라고 한다.^[21]모든 위상학적 소인도 소인임을 쉽게 알 수 있다.그러나 역은 일반적으로 사실이 아니며(예를 들어 피터슨 그래프의 전체 그래프 K는₅ 부차적이지만 위상학적 그래프는 아님) 최대도가 3 이하인 그래프를 유지한다.^[22]

위상학적 소관계는 유한 그래프^[23] 집합에서 잘 준주문되지 않으며 따라서 로버슨과 시모어의 결과는 위상학적 미성년자에게 적용되지 않는다.그러나 최소 2도 이상 내려간 k 잎의 모든 나무로 모든 분기를 k 발신 가장자리로 교체함으로써 유한 금지된 사소한 특성화로부터 유한 금지된 위상학적 사소한 특성을 구성하는 것은 간단하다.

유도미성년자

가장자리를 수축시켜 G의 유도 하위 그래프에서 얻을 수 있다면 그래프 H를 그래프 G의 유도 부차라고 한다.그렇지 않으면 G는 H로 인한 경미한 무(無)^[24]라고 한다.

몰입 단조

리프팅이라고 불리는 그래프 연산은 임모션이라는 개념에서 중심이다.리프팅은 인접한 가장자리에서의 작업이다.v, u, w의 3개의 꼭지점이 주어진 경우, (v,u)와 (u,w)가 그래프에서 가장자리인 경우, 뷔의 리프팅 또는 (v,u)와 동등한 (u,w)는 두 가장자리(v,u)와 (u,w)를 삭제하고 가장자리(v,w)를 추가하는 작업이다.이미 (v,w)가 존재했던 경우, 이제 v와 w는 둘 이상의 에지로 연결될 것이며, 따라서 이 작업은 본질적으로 다중그래프 작업이다.

(G에 대한) 리프팅 작업 순서(G에 대한)에 의해 그래프 G에서 그래프 H를 얻을 수 있는 경우, 우리는 H가 G의 몰입 마이너라고 말한다.리프팅 작업과 동등한 몰입 미성년자를 정의하는 또 다른 방법이 있다.우리는 H의 정점부터 G의 정점까지의 주입 매핑이 존재한다면 H는 G의 몰입 마이너로서 H의 인접 요소들의 영상이 G에서 가장자리 분리 경로로 말한다.

몰입 마이너 관계는 유한 그래프 집합에 잘 준주문된 것이므로, 로버슨과 시모어의 결과는 몰입 미성년자에게 적용된다.이것은 또한 모든 몰입 마이너 클로즈드 가족이 금지된 몰입 미성년자들의 유한한 가족으로 특징지어진다는 것을 의미한다.

그래프 도면에서, 몰입 미성년자는 비 평면 그래프의 평면화에 따라 발생한다: 평면 내 그래프의 도면에서 교차점을 사용하여 각 교차점을 새로운 정점으로 대체함으로써 몰입 마이너를 형성할 수 있으며, 그 과정에서 각 교차점을 경로로 세분화하기도 한다.이를 통해 평면 그래프의 그리기 방법을 비 평면 그래프로 확장할 수 있다.^[25]

얕은 미성년자

그래프 G의 얕은 부차는 부문을 형성하기 위해 수축된 G의 가장자리가 지름이 낮은 분리형 서브그래프 모음을 형성하는 부차다.얕은 미성년자는 그래프 미성년자와 하위그래프의 이론 사이를 보간하는데, 반면에 깊이가 높은 얕은 미성년자는 일반적인 유형의 그래프 미성년자와 일치한다는 점에서, 반면 깊이가 0인 얕은 미성년자는 정확히 하위그래프다.^[26]그들은 또한 그래프 미성년자 이론이 미성년자 취급을 받지 않고 닫히지 않는 1평형 그래프와 같은 그래프 종류로 확장될 수 있도록 허용한다.^[27]

패리티 조건

그래프 마이너의 대안적이고 동등한 정의는 H의 정점들이 G의 정점-분점 하위 트리의 집합으로 표현될 수 있을 때마다 H가 G의 마이너라는 것이다. 즉, 두 정점이 H에 인접할 경우 G의 해당 두 트리에 그 끝점과의 에지가 존재하게 된다.홀수 부차는 이러한 하위 트리에 패리티 조건을 추가하여 이 정의를 제한한다.만약 H가 위와 같이 G의 하위 트리의 집합으로 표현된다면, 하위 트리 내의 G의 각 가장자리가 적절히 색칠되도록(끝점의 색이 다름) G의 각 가장자리에 두 가지 색상을 할당할 수 있을 때마다 H는 홀수 G의 마이너로서, 두 하위 트리 사이의 인접성을 나타내는 G의 각 가장자리는 단색이다.ic(두 끝점이 동일한 색상임).일반적인 유형의 그래프 미성년자와 달리, 금지된 홀수 미성년자가 있는 그래프는 반드시 희박한 것은 아니다.^[28]크롬 그래프에 반드시 k-Vertex 완전 그래프가 들어 있다는 하드와이거 추측도 홀수 미성년자의 관점에서 연구됐다.^[29]

그래프 마이너스의 개념에 대한 다른 패리티 기반 확장은 양분 마이너의 개념으로 시작 그래프가 양분될 때마다 양분 그래프를 생성한다.그래프 H는 그래프의 주변 주기에 따라 서로 거리 2에 있는 정점을 삭제하고, 가장자리를 삭제하고, 정점의 쌍을 접어서 G로부터 H를 얻을 수 있을 때마다 다른 그래프 G의 양분형 부차다.바그너의 정리의 형태는 초당적 미성년자에게 적용된다:^[30] 초당적 그래프 G는 초당적 마이너로서 효용 그래프 K가 없는_3,3 경우에만 평면 그래프다.

알고리즘

그래프 G가 H를 마이너로서 포함하는지 여부를 결정하는 문제는 일반적으로 NP-완전하다. 예를 들어, H가 G와 정점 수가 같은 사이클 그래프라면, G가 해밀턴 사이클을 포함하는 경우에만 H가 G의 마이너다.단, G가 입력의 일부인데 H가 고정되어 있을 때는 다항 시간 내에 해결할 수 있다.구체적으로는 이 경우 H가 G의 마이너인지 여부를 테스트하기 위한 실행 시간은 O(n³)이며, 여기서 n은 G의 정점수이며, 큰 O 표기법은 H에 기본적으로 의존하는 상수를 숨긴다.^[3] 원래의 Graph Minors 결과 이후 이 알고리즘은 O(n²) 시간으로 개선되었다.^[31]따라서, 주어진 그래프에 금지된 미성년자가 포함되어 있는지 여부를 시험하기 위해 다항 시간 알고리즘을 적용함으로써, 이론적으로 다항 시간 내에 마이너 폐쇄 가족의 구성원을 인식하는 것이 가능하다.이 결과는 숨겨진 상수가 어떤 응용을 배제시킬 정도로 거대하기 때문에(표현하기 위해 크누스의 위쪽 화살표 표기법의 3개 층이 필요하기 때문에 은하 알고리즘으로 사용되지는 않는다.^[32]나아가 이 결과를 건설적으로 적용하기 위해서는 그래프 계열의 금지된 미성년자가 무엇인지 알 필요가 있다.^[4]금지된 미성년자가 알려져 있거나 계산이 가능한 경우도 있다.^[33]

H가 고정 평면 그래프인 경우, 입력 그래프 G에서 H가 G의 마이너인지 여부를 선형 시간으로 테스트할 수 있다.^[34]H가 고정되지 않은 경우 G가 평면인 경우 보다 빠른 알고리즘을 알 수 있다.^[35]

메모들

참조

외부 링크

• Weisstein, Eric W. "Graph Minor". MathWorld.