그래프 구조 정리

수학에서 **그래프 구조 정리**()는 그래프 이론 분야의 주요 결과이다. 이 결과는 그래프 마이너 이론과 위상적 임베딩 사이에 깊고 근본적인 연결을 설정한다. 이 정리는 닐 로버트슨과 폴 시모어가 저술한 23편의 논문 시리즈 중 17번째 논문에 기술되어 있다. 그 증명은 매우 길고 복잡하다. 와 는 비전문가도 접근 가능한 개요서로, 이 정리와 그 함의를 설명하고 있다.

## 정리의 설정 및 동기
그래프 의 마이너는 의 부분 그래프에서 일부 변을 수축하여 얻을 수 있는 그래프와 동형인 임의의 그래프 를 말한다. 만약 가 그래프 를 마이너로 갖지 않는다면, 를 **-제외**(H-free) 그래프라고 한다. 를 고정된 그래프라고 하자. 직관적으로, 가 거대한 -제외 그래프라면, 여기에는 그럴만한 "타당한 이유"가 있어야 한다. 그래프 구조 정리는 의 구조에 대한 대략적인 설명을 통해 이러한 "타당한 이유"를 제공한다. 본질적으로, 모든 -제외 그래프 는 두 가지 구조적 결함 중 하나를 갖는다. 즉, 가 를 마이너로 갖기에는 "너무 얇거나", 혹은 를 임베딩하기에는 너무 단순한 곡면에 (거의) 위상적으로 임베딩될 수 있다는 것이다. 첫 번째 이유는 가 평면 그래프인 경우에 해당하며, 가 평면 그래프가 아닌 경우에는 두 이유가 모두 적용된다. 먼저 이러한 개념들을 명확히 정의한다.

### 트리 너비
그래프 의 트리 너비는 의 "얇기"를 규정하는 양의 정수이다. 예를 들어, 연결 그래프 의 트리 너비가 1인 것은 가 트리인 것과 동치이며, 의 트리 너비가 2인 것은 가 직병렬 그래프인 것과 동치이다. 직관적으로 거대한 그래프 가 작은 트리 너비를 갖는다는 것은, 가 노드와 변이 작은 그래프들로 대체된 거대한 트리의 구조를 띠고 있음을 의미한다. 클릭 합(clique-sum)에 관한 소절에서 트리 너비의 정확한 정의를 다룬다. 만약 가 의 마이너라면, 의 트리 너비는 의 트리 너비보다 크지 않다는 정리가 있다. 따라서 가 -제외 그래프가 되는 한 가지 "타당한 이유"는 의 트리 너비가 그리 크지 않다는 것이다. 그래프 구조 정리는 가 평면 그래프인 경우 이 이유가 항상 적용됨을 시사한다.

따름정리 1. 모든 평면 그래프 에 대하여, 모든 -제외 그래프의 트리 너비가 보다 작게 만드는 양의 정수 가 존재한다.

따름정리 1에서 의 값은 일반적으로 의 트리 너비보다 훨씬 크다는 점은 아쉬운 부분이다(주요한 예외는 정점이 4개인 완전 그래프인 로, 이 경우 이다). 이것이 그래프 구조 정리가 -제외 그래프의 "대략적인 구조"를 기술한다고 말하는 이유 중 하나이다.

### 곡면 임베딩
대략적으로 곡면은 원판의 국소적 위상 구조를 가진 점들의 집합이다. 곡면은 두 개의 무한한 부류로 나뉜다. 가향 곡면에는 구, 원환면, 쌍원환면 등이 포함되며, 비가향 곡면에는 실 사영 평면, 클라인 병 등이 포함된다. 그래프가 곡면에 임베딩된다는 것은, 그래프의 변과 정점이 부합하거나 인접한 경우를 제외하고는 서로 교차하거나 닿지 않도록 곡면 위에 점(정점)과 호(변)의 집합으로 그릴 수 있음을 의미한다. 그래프가 구에 임베딩될 수 있으면 평면 그래프이다. 만약 그래프 가 특정 곡면에 임베딩된다면, 의 모든 마이너 또한 동일한 곡면에 임베딩된다. 따라서 가 -제외 그래프가 되는 또 다른 "타당한 이유"는 가 는 임베딩될 수 없는 곡면에 임베딩된다는 것이다.

가 평면 그래프가 아닐 때, 그래프 구조 정리는 쿠라토프스키 정리의 방대한 일반화로 볼 수 있다. 가 증명한 이 정리의 한 버전에 따르면, 그래프 가 -제외이면서 동시에 -제외이면 는 평면 그래프이다. 이 정리는 그래프 가 나 을 마이너로 갖지 않는 "타당한 이유"를 제공한다. 구체적으로 는 구에 임베딩되지만, 나 은 구에 임베딩되지 않기 때문이다. 안타깝게도 이러한 "타당한 이유"의 개념은 그래프 구조 정리에는 충분히 정교하지 않다. 클릭 합과 소용돌이(vortex)라는 두 가지 개념이 더 필요하다.

### 클릭 합
그래프 에서 클릭은 에서 서로 쌍으로 인접한 정점들의 집합이다. 음이 아닌 정수 에 대하여, 두 그래프 와 의 **-클릭 합**이란, 음이 아닌 정수 를 선택하고, 와  각각에서 크기 의 클릭을 선택하여 두 클릭을 하나의 크기  클릭으로 식별한 후, 새 클릭의 정점들을 잇는 변들 중 0개 이상을 삭제하여 얻은 임의의 그래프를 말한다.

만약 이 그래프들의 목록이라면, 이들을 -클릭 합으로 연결하여 새로운 그래프를 만들 수 있다. 즉, 과 의 -클릭 합을 구하고, 그 결과물과 의 -클릭 합을 구하는 식이다. 그래프의 **트리 너비가 최대 **라는 것은, 각 그래프가 최대 개의 정점을 가진 그래프 목록으로부터 -클릭 합을 통해 얻어질 수 있음을 의미한다.

따름정리 1은 가 평면 그래프일 때 작은 그래프들의 -클릭 합이 -제외 그래프의 대략적인 구조를 설명함을 보여준다. 가 비평면 그래프인 경우에는 곡면에 임베딩된 그래프들의 목록에 대한 -클릭 합도 고려해야 한다. 를 사용한 다음 예시는 이 점을 잘 보여준다. 그래프 는 구를 제외한 모든 곡면에 임베딩된다. 그러나 평면 그래프와는 거리가 먼 -제외 그래프들이 존재한다. 특히, 임의의 평면 그래프 목록에 대한 3-클릭 합은 -제외 그래프가 된다. 는 바그너의 정리로 알려진 일련의 결과 중 일부로서 -제외 그래프의 정확한 구조를 결정했다.

정리 2. 만약 가 -제외라면, 는 평면 그래프들과 8개의 정점을 가진 하나의 특수한 비평면 그래프의 복사본들로부터 3-클릭 합을 통해 얻어질 수 있다.

정리 2는 -제외 그래프의 정확한 구조가 결정되었으므로 정밀한 구조 정리(exact structure theorem)라고 할 수 있다. 이러한 결과는 그래프 이론에서 드문 편이다. 그래프 구조 정리는 대부분의 그래프 에 대해 -제외 그래프의 구조적 기술이 -제외가 아닌 일부 그래프도 포함하기 때문에 이런 의미에서 정밀하지는 않다.

### 소용돌이 (대략적 설명)
 이외의 그래프 에 대해서도 정리 2와 유사한 정리가 성립할 것이라고 추측하고 싶을 수도 있다. 아마도 다음과 같은 진술이 참일 것이라 생각할 수 있다: 임의의 비평면 그래프 에 대하여, 모든 -제외 그래프가 -클릭 합을 통해 얻어질 수 있게 하는 양의 정수 가 존재하며, 이때 각 그래프는 최대 개의 정점을 갖거나 가 임베딩될 수 없는 곡면에 임베딩된다. 안타깝게도 이 진술은 참이 되기에는 아직 충분히 정교하지 않다. 임베딩된 각 그래프 가 두 가지 제한된 방식으로 "반칙"을 하도록 허용해야 한다. 첫째, 곡면 위의 한정된 수의 위치에서 새로운 정점과 변을 추가하되, 제한된 복잡도 내에서 서로 교차하는 것을 허용해야 한다. 이러한 위치를 **소용돌이**(vortex)라고 부른다. 소용돌이의 "복잡도"는 경로 너비와 밀접한 관련이 있는 **깊이**(depth)라는 매개변수에 의해 제한된다. 독자는 깊이 인 소용돌이에 대한 다음의 정밀한 설명을 나중에 읽어도 좋다. 둘째, 소용돌이가 있는 각 임베딩된 그래프에 제한된 수의 새로운 정점을 추가하는 것을 허용해야 한다.

### 소용돌이 (정밀한 정의)
임베딩된 그래프의 **면**(face)은 그래프와 분리되어 있지만 그 경계가 임베딩된 그래프의 일부 변들의 합집합으로 이루어진 곡면 상의 열린 2-세포이다. 를 임베딩된 그래프 의 한 면이라 하고, , 을 의 경계 위에 (원형 순서대로) 놓인 정점들이라고 하자. 에 대한 **원형 구간**(circular interval)은  형태의 정점 집합을 말하며, 여기서 와 는 정수이고 하첨자는 법 으로 계산된다. 를 에 대한 원형 구간들의 유한한 목록이라고 하자. 다음과 같이 새로운 그래프를 구성한다. 의 각 원형 구간 에 대해 새로운 정점 을 추가하고 이를 에 속한 0개 이상의 정점들과 연결한다. 마지막으로, 의 각 구간 쌍 에 대하여, 과 의 교집합이 공집합이 아니라면 과 을 잇는 변을 추가할 수 있다. 의 경계 상의 어떤 정점도 에 있는 구간들 중 개 보다 많은 구간에 나타나지 않는다면, 결과 그래프는 로부터 (면 에) **최대 깊이 인 소용돌이를 추가**하여 얻은 것이라고 한다.

## 그래프 구조 정리의 내용
**그래프 구조 정리.** 임의의 그래프 에 대하여, 모든 -제외 그래프가 다음과 같이 얻어질 수 있게 하는 양의 정수 가 존재한다.
# 가 임베딩되지 않는 곡면에 임베딩된 그래프들의 목록에서 시작한다.
# 목록의 각 임베딩된 그래프에 최대 개의 소용돌이를 추가하며, 각 소용돌이의 깊이는 최대 이다.
# 각 결과 그래프에 최대 개의 새로운 정점(**[[정점 덮개 그래프|첨단 정점]]**(apices)이라 불림)을 추가하고, 적어도 하나의 끝점이 첨단 정점에 있는 변들을 임의의 개수만큼 추가한다.
# 마지막으로, 결과 그래프 목록을 -클릭 합을 통해 연결한다.

가 평면 그래프인 경우 1단계와 2단계의 결과는 공 그래프가 되지만, 3단계에서 추가되는 한정된 수의 정점들 덕분에 이 진술은 따름정리 1과 일치하게 된다.

## 개선된 결과들
금지된 마이너 집합 에 따라 그래프 구조 정리의 강화된 버전들이 가능하다. 예를 들어, 의 그래프 중 하나가 평면 그래프인 경우, 모든 -마이너-제외 그래프는 유계된 너비의 트리 분해를 갖는다. 즉, 이는 상수 크기 그래프들의 클릭 합으로 표현될 수 있다. 의 그래프 중 하나가 단 하나의 교차만으로 평면에 그려질 수 있는 경우, -마이너-제외 그래프는 소용돌이 없이 상수 크기의 그래프들과 유계된 속(genus)을 가진 그래프들의 클릭 합으로 분해될 수 있다.
의 그래프 중 하나가 첨단 그래프(apex graph)인 경우에 대해서도 다른 강화된 결과가 알려져 있다.

## 같이 보기
* 로버트슨-시모어 정리

## 내용주

## 각주
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.

분류:그래프 이론 정리