그래프 구조 정리

Graph structure theorem

수학에서 그래프 구조 정리는 그래프 이론 영역의 주요한 결과물이다.그 결과는 그래프 미성년자 이론과 위상학적 임베딩 사이의 깊고 근본적인 연관성을 확립한다.그 정리는 닐 로버트슨과 폴 시모어의 23개 논문 시리즈 중 17번째에 명시되어 있다.그 증거는 매우 길고 관련이 있다.카와라바야시&모하르(2007)와 로바스츠(2006)는 비전문가가 접근할 수 있는 조사로, 정리 및 그 결과를 기술하고 있다.

정리를 위한 설정과 동기

그래프 G의 단위는 G의 하위 그래프에서 일부 가장자리를 수축하여 얻을 수 있는 그래프에 이형화된 그래프 H이다.만약 G가 그래프 H를 마이너로서 가지고 있지 않다면, 우리는 G가 H-프리라고 말한다.H를 고정 그래프로 하자.직관적으로, G가 거대한 H-프리 그래프라면, 이것에는 "좋은 이유"가 있어야 한다.그래프 구조 정리는 G의 구조에 대한 대략적인 설명의 형태로 그러한 "좋은 이유"를 제공한다.본질적으로, 모든 H-프리 그래프 G는 두 가지 구조적 결점 중 하나로 고통 받는다: G는 너무 얇아서 H를 마이너로서 가질 수 없거나, G는 너무 단순해서 H를 삽입할 수 없는 표면에 (대부분) 토폴로 삽입될 수 있다.첫 번째 이유는 H가 평면 그래프일 경우 적용되며, H가 평면 그래프가 아닐 경우 두 가지 이유가 모두 적용된다.우리는 먼저 이러한 개념들을 정확하게 만든다.

트리 폭

그래프 G의 트리 너비는 G의 "씬함"을 지정하는 양의 정수다.예를 들어, 연결된 그래프 G는 나무인 경우에만 나무 너비가 1이고, G는 직렬-병렬 그래프인 경우에만 나무 너비가 2이다.직관적으로 거대한 그래프 G는 노드와 가장자리가 작은 그래프로 대체된 거대한 나무의 구조를 G가 취할 경우에만 작은 트리 폭을 가진다.우리는 clique-sum에 관한 하위섹션에서 나무 너비의 정확한 정의를 제공한다.H가 G의 마이너라면 H의 트리 너비가 G의 트리 너비보다 크지 않다는 것이 정리다.따라서 G가 H가 없는 한 가지 "좋은 이유"는 G의 나무 너비가 그리 크지 않다는 것이다.그래프 구조 정리는 H가 평면인 경우에 항상 이 이유가 적용된다는 것을 암시한다.

코롤러리 1.모든 평면 그래프 H에 대해 모든 H-프리 그래프가 k보다 작은 트리 너비를 가질 수 있는 양의 정수 k가 존재한다.

일반적으로 Corollary 1의 k 값이 H의 트리 너비보다 훨씬 크다는 것은 유감스러운 일이다( 주목할 만한 예외는 H = K4, 4 정점의 전체 그래프인 k=3의 경우).이것은 그래프 구조 정리가 H-프리 그래프의 "거친 구조"를 기술한다고 하는 한 가지 이유다.

표면 임베딩

대략, 표면은 디스크의 국소 위상 구조를 가진 점들의 집합이다.표면은 두 개의 무한으로 구성된다: 방향성 표면은 구체, 토러스, 이중 토러스 등을 포함한다. 방향성이 없는 표면은 실제 투영면, 클라인 병 등을 포함한다.가장자리와 정점이 입사하거나 인접한 경우를 제외하고 서로 교차하거나 접촉하지 않는 점(수직)과 호(에지)의 집합으로 그래프를 표면에 그릴 수 있는 경우 그래프가 표면에 내장된다.그래프가 구체에 내장되면 평면형이다.그래프 G가 특정 표면에 삽입되면 G의 모든 부위도 동일한 표면에 삽입된다.따라서 G가 H-프리(H-free)가 되는 "좋은 이유"는 H가 내장되지 않은 표면에 G가 내장되어 있기 때문이다.

H가 평면적이 아닐 때, 그래프 구조 정리는 쿠라토프스키 정리의 광대한 일반화로 볼 수 있다.바그너(1937년)에 의해 증명된 이 정리의 버전은 그래프 G가 K-프리5(K-free)와 K-프리(K-free3,3)라면 G는 평면(planar)이라고 기술하고 있다.이 정리는 그래프 G가 K나5 K를3,3 미성년자로 갖지 않는 "좋은 이유"를 제공한다. 특히 G는 구에 내장되는 반면 K나5 K는3,3 구에 내장되지 않는다.불행히도, "좋은 이유"라는 개념은 그래프 구조 정리에 충분히 정교하지 않다.두 가지 개념이 더 필요하다: clique-sum과 vortices.

클라이크섬

그래프 G의 클라이크는 G에 인접한 쌍방향 정점 집합이다.음이 아닌 정수 k의 경우, 두 그래프 G와 K의 k-clique-sum은 음이 아닌 정수 m ≤ k를 선택하고, 각각의 G와 K에서 size m의 clique를 선택하여, 두 개의 clique를 하나의 size m의 clique로 식별한 다음, 새로운 clique에 정점을 이루는 가장자리를 0 이상 삭제함으로써 얻은 그래프다.

G1, G2, ..., G가n 그래프의 목록이라면, 우리는 k-clique-sum을 통해 그래프 리스트에 참여함으로써 새로운 그래프를 만들 수도 있다.즉, 우리는1 G와 G의2 k-clique-sum을 취하고, 그 결과 그래프로 G의3 k-clique-sum을 취하는 등의 과정을 거친다.그래프 목록에서 k-clike-sum을 통해 얻을 수 있다면 그래프는 최대 k의 트리 너비를 가지며, 목록의 각 그래프는 최대 k + 1 정점을 가진다.

Corolary 1은 우리에게 H가 평면일 때 작은 그래프의 k-clique-sum이 대략적인 구조 H-free 그래프를 설명한다는 것을 나타낸다.H가 비 평면적일 때, 우리는 또한 그래프 목록의 k-clik-sum을 고려할 필요가 있다. 각 그래프는 표면에 내장되어 있다.H = K를5 사용한 다음 예는 이 점을 예시한다.그래프 K는5 구를 제외한 모든 표면에 내장되어 있다.그러나 평면과는 거리가 먼 K-프리5 그래프가 존재한다.특히 평면 그래프의 리스트를 3-클릭하면 K-프리5 그래프가 된다.바그너(1937년)는 와그너의 정리라고 알려진 결과 군집의 일부로서 K-프리5 그래프의 정밀한 구조를 결정했다.

정리2.G가 K-프리인5 경우, 평면 그래프 리스트에서 3-클릭섬을 통해 G를 얻을 수 있고, 8-수직을 가진 특별한 비-평면 그래프 한 개의 복사본을 얻을 수 있다.

K-프리5 그래프의 정밀한 구조가 결정되기 때문에 정리2는 정확한 구조 정리라고 지적한다.그래프 이론에서는 그러한 결과가 드물다.대부분의 그래프 H의 경우 H-프리 그래프의 구조 설명에는 H-프리 그래프가 아닌 일부 그래프가 포함되기 때문에 그래프 구조 정리는 이러한 의미에서 정확하지 않다.

상자(설명하기 어려운 내용)

정리2의 아날로그가 K가5 아닌 그래프 H를 가지고 있다고 추측하고 싶은 마음이 들 수도 있다.아마도 사실일 것이다: 모든 비 평면 그래프 H의 경우 모든 H-프리 그래프는 그래프 목록에서 k-clique-sum을 통해 얻을 수 있는 양의 정수 k가 존재하며, 각 그래프는 H가 포함하지 않는 일부 표면에 최대 k 정점 또는 내장되어 있다.불행히도, 이 진술은 사실일 정도로 아직 정교하지 않다.우리는 각각의 내장된 그래프 G가i 두 가지 제한된 방법으로 "치트"하도록 허용해야 한다.첫째, 우리는 제한된 복잡성의 방법으로 서로 교차할 수 있는 새로운 정점과 가장자리를 추가할 수 있는 표면의 경계된 위치 수를 허용해야 한다.그러한 장소를 vortices라고 부른다.소용돌이의 "복잡성"은 그 깊이라고 불리는 매개변수에 의해 제한되며, 경로 폭과 밀접한 관련이 있다.독자는 깊이 k의 소용돌이에 대한 다음과 같은 정확한 설명을 읽는 것을 지연시킬 수 있다.둘째, vortices가 포함된 각 그래프에 제한된 수의 새로운 정점을 추가하도록 허용해야 한다.

Vortice(정밀 정의)

내장된 그래프의 면은 그래프에서 분리되지만, 그 경계는 포함된 그래프의 일부 가장자리의 결합인 표면의 열린 2셀이다.F를 내장된 그래프 G의 면으로 하고 v0, v1, v, ..., vn−1,vn = v를0 F의 경계(그 원형 순서로)에 놓여 있는 정점이 되게 한다.F에 대한 순환 간격은 a와 s가 정수이고 첨자가 감소된 modulo n인 {va, va+1, ..., va+s} 형식의 정점 집합이다.Ⅱ를 F에 대한 순환구간의 유한한 목록으로 한다.우리는 아래와 같이 새로운 그래프를 구성한다.λ의 각 원형 구간 L에 대해 우리는 L의 정점 0 이상에 결합되는 새로운 정점 v를L 추가한다.마지막으로, λ에서 간격의 각 쌍 {L, M}에 대해 L과 M이 비어 있지 않은 교차점을 갖는 경우 v에M 엣지 결합 v를L 추가할 수 있다.결과 그래프는 λ의 간격 중 k보다 큰 간격으로 F의 경계에 정점이 나타나지 않는 경우, 최대 k(면 F)에서 깊이의 소용돌이를 추가하여 G로부터 얻었다고 한다.

그래프 구조 정리 명세서

그래프 구조 정리 모든 그래프 H의 경우, 모든 H-프리 그래프를 다음과 같이 얻을 수 있는 양의 정수 k가 존재한다.

  1. 먼저 그래프 목록부터 시작하는데, 목록의 각 그래프는 H가 포함하지 않는 표면에 포함되어 있다.
  2. 목록에 포함된 각 그래프에 각 소용돌이의 깊이가 최대 kk인 vortices를 추가한다.
  3. 각 결과 그래프에 우리는 최대 k개의 새로운 정점(정점이라고 함)을 추가하고, 각 정점 사이에 최소한 하나의 끝점을 갖는 임의의 수의 가장자리를 추가한다.
  4. 마지막으로, 우리는 결과적인 그래프 목록을 k-clike-clike를 통해 참여한다.

1단계와 2단계는 H가 평면인 경우 빈 그래프가 되지만 3단계에서 추가된 정점의 경계 수는 이 문구를 Corolary 1과 일치하도록 만든다는 점에 유의하십시오.

정제

금지된 미성년자의 설정 H에 따라 그래프 구조 정리의 강화된 버전이 가능하다.예를 들어, H의 그래프 중 하나가 평면인 경우 모든 H-미노르 프리 그래프는 경계 폭의 트리 분해를 가지고 있다. 동등하게, 일정한 크기의 그래프의 집단 합으로 나타낼 수 있다.[1]H에 있는 그래프 중 하나를 단 하나의 교차만으로 평면에서 그릴 수 있는 경우, H-미노르 프리 그래프는 일정한 크기의 그래프와 한정된 속도의 그래프의 집단 합으로 분해를 인정하며, 변위가 없다.[2]H의 그래프 중 하나가 꼭지점 그래프인 경우에도 다른 강화가 알려져 있다.[3]

참고 항목

메모들

  1. ^ 그래프 Minor V.
  2. ^ 로버트슨 & 시모어(1993); 데메인, 하지아카이 & 틸리코스(2002).
  3. ^ 데메인, 하지아헤이 & 카와라바야시(2009년).

참조