로버트슨-시모어 정리

그래프 이론에서, **로버트슨-시모어 정리**(, 또는 **그래프 마이너 정리**())는 그래프 마이너(또는 부그래프의 축약) 관계에 의해 원순서가 부여된 무향 그래프들이 고른 준순서(well-quasi-ordering)를 형성한다는 정리이다. 이와 동등하게, 마이너 연산에 대해 닫혀 있는 모든 그래프의 족은 유한한 금지된 마이너 집합으로 정의될 수 있다. 이는 바그너의 정리가 평면 그래프를 완전 그래프 K_5나 완전 이분 그래프 K_{3,3}을 마이너로 가지지 않는 그래프로 특성 짓는 것과 같은 방식이다.

로버트슨-시모어 정리는 수학자 닐 로버트슨과 폴 시모어의 이름을 따서 명명되었으며, 그들은 1983년부터 2004년까지 500페이지가 넘는 20편의 논문 시리즈를 통해 이를 증명했다. 증명되기 전, 이 정리의 내용은 독일 수학자 클라우스 바그너의 이름을 딴 **바그너의 추측**()으로 알려져 있었으나, 바그너 본인은 그런 추측을 한 적이 없다고 밝혔다.

나무에 대한 더 약한 결과는 크러스컬 나무 정리에 의해 함의되는데, 이는 1937년 언드라시 바조니가 추측하였고 1960년 조지프 크러스컬과 S. 타르코프스키에 의해 독립적으로 증명되었다.

## 정의
무향 그래프 G의 마이너는 G의 변에 대한 0회 이상의 축약과 변 및 정점의 삭제를 통해 얻을 수 있는 모든 그래프를 말한다. 마이너 관계는 모든 서로 다른 유한 무향 그래프의 집합 위에서 부분 순서를 형성하는데, 이는 부분 순서의 세 가지 공리를 따르기 때문이다. 즉, 반사관계(모든 그래프는 자기 자신의 마이너이다), 추이적 관계(G의 마이너의 마이너는 그 자체로 G의 마이너이다), 반대칭관계(두 그래프 G와 H가 서로의 마이너라면, 두 그래프는 동형이어야 한다)를 만족한다. 그러나 동형인 그래프들을 별개의 객체로 간주할 경우, 그래프의 마이너 순서는 원순서(반사적이고 추이적이지만 반드시 반대칭일 필요는 없는 관계)를 형성한다.

원순서가 무한 내림 사슬과 무한 반사사슬을 모두 포함하지 않을 때 이를 고른 준순서라고 한다. 예를 들어, 음이 아닌 정수 위의 통상적인 순서는 고른 준순서이지만, 모든 정수 집합 위의 동일한 순서는 무한 내림 사슬 0,&nbsp;&minus;1,&nbsp;&minus;2,&nbsp;&minus;3...을 포함하므로 고른 준순서가 아니다. 또 다른 예로 가해성에 의해 순서가 매겨진 양의 정수 집합은 무한 내림 사슬은 없지만, 소수들이 무한 반사사슬을 구성한다.

로버트슨-시모어 정리는 유한 무향 그래프와 그래프 마이너가 고른 준순서를 형성한다는 것을 명시한다. 그래프 마이너 관계는 무한 내림 사슬을 포함하지 않는데, 각 축약이나 삭제는 그래프의 정점과 변의 수(음이 아닌 정수)를 줄이기 때문이다. 이 정리의 사소하지 않은 부분은 무한 반사사슬, 즉 마이너 순서로 서로 관련이 없는 무한한 그래프 집합이 존재하지 않는다는 점이다. 만약 \mathcal{S}가 그래프들의 집합이고, \mathcal{M}이 각 최소 원소(\mathcal{S}에 속하지만 그 어떤 진마이너도 \mathcal{S}에 속하지 않는 그래프)의 동치류에 대한 대표 그래프를 하나씩 포함하는 \mathcal{S}의 부분 집합이라면, \mathcal{M}은 반사사슬을 형성한다. 따라서 이 정리를 서술하는 동등한 방법은, 그래프의 임의의 무한 집합 \mathcal{S}에는 비동형인 최소 원소가 오직 유한 개만 존재해야 한다는 것이다.

이 정리의 또 다른 동등한 형태는, 그래프의 임의의 무한 집합 \mathcal{S}에서 한 그래프가 다른 그래프의 마이너가 되는 한 쌍의 그래프가 반드시 존재해야 한다는 것이다. 모든 무한 집합이 유한 개의 최소 원소를 갖는다는 진술은 이 형태를 함의한다. 왜냐하면 최소 원소가 유한 개뿐이라면, 나머지 각 그래프는 최소 원소 중 하나와 이러한 유형의 쌍을 이루어야 하기 때문이다. 반대 방향으로도, 이 형태의 정리는 무한 반사사슬이 존재할 수 없음을 의미한다. 무한 반사사슬은 마이너 관계에 의해 연관된 어떤 쌍도 포함하지 않는 집합이기 때문이다.

## 금지된 마이너 특성분석

그래프들의 족 \mathcal{F}가 \mathcal{F}에 속한 그래프의 모든 마이너가 다시 \mathcal{F}에 속할 때, 마이너 연산에 대해 닫혀 있다고 한다. 만약 \mathcal{F}가 마이너-폐쇄적 족이라면, \mathcal{S}를 \mathcal{F}에 속하지 않는 그래프들의 클래스(\mathcal{F}의 여집합)라고 하자. 로버트슨-시모어 정리에 따르면, \mathcal{S}에는 유한한 최소 원소 집합 \mathcal{H}가 존재한다. 이러한 최소 원소들은 \mathcal{F}의 금지된 그래프 특성분석을 형성한다. 즉, \mathcal{F}에 속하는 그래프들은 정확히 \mathcal{H}에 속하는 어떤 그래프도 마이너로 가지지 않는 그래프들이다. \mathcal{H}의 원소들을 족 \mathcal{F}에 대한 **제외된 마이너**(또는 **금지된 마이너**, 또는 **마이너-최소 장애물**)라고 부른다.

예를 들어, 평면 그래프는 마이너 연산에 대해 닫혀 있다. 평면 그래프의 변을 축약하거나 변 또는 정점을 제거해도 평면성을 파괴할 수 없기 때문이다. 따라서 평면 그래프는 금지된 마이너 특성분석을 가지며, 이 경우 바그너의 정리에 의해 주어진다. 마이너-최소 비평면 그래프의 집합 \mathcal{H}는 정확히 두 개의 그래프, 완전 그래프 K_5와 완전 이분 그래프 K_{3,3}를 포함하며, 평면 그래프는 정확히 집합 \mathcal{H}=\{K_5,K_{3,3}\}의 마이너를 가지지 않는 그래프들이다.

모든 마이너-폐쇄 그래프 족에 대해 금지된 마이너 특성분석이 존재한다는 것은 로버트슨-시모어 정리를 서술하는 동등한 방법이다. 왜냐하면, 모든 마이너-폐쇄 족 \mathcal{F}가 유한한 최소 금지 마이너 집합 \mathcal{H}를 갖는다고 가정하고, \mathcal{S}를 임의의 무한 그래프 집합이라 하자. \mathcal{S}의 마이너를 가지지 않는 그래프들의 족으로 \mathcal{F}를 결정하면, \mathcal{F}는 마이너-폐쇄적이며 유한한 최소 금지 마이너 집합 \mathcal{H}를 갖는다. \mathcal{C}를 \mathcal{F}의 여집합이라 하자. \mathcal{S}와 \mathcal{F}는 서로소이므로 \mathcal{S}는 \mathcal{C}의 부분 집합이고, \mathcal{H}는 \mathcal{C}에서의 최소 그래프들이다. \mathcal{H}에 속한 그래프 G를 고려하자. G는 \mathcal{C}에서 최소이므로 \mathcal{S}에 진마이너를 가질 수 없다. 동시에 G는 \mathcal{S}의 마이너를 가져야만 하는데, 그렇지 않으면 G가 \mathcal{F}의 원소가 되기 때문이다. 따라서 G는 \mathcal{S}의 원소이며, 즉 \mathcal{H}는 \mathcal{S}의 부분 집합이고, \mathcal{S}의 다른 모든 그래프는 \mathcal{H}의 그래프 중 하나를 마이너로 가지므로, \mathcal{H}는 \mathcal{S}의 유한한 최소 원소 집합이 된다.

반대 방향의 동등성을 입증하기 위해, 모든 그래프 집합이 유한한 최소 그래프 부분 집합을 갖는다고 가정하고 마이너-폐쇄 집합 \mathcal{F}가 주어졌다고 하자. 우리는 그래프가 \mathcal{F}에 속할 필요충분조건이 \mathcal{H}의 마이너를 가지지 않는 것인 집합 \mathcal{H}를 찾고자 한다. \mathcal{E}를 \mathcal{F}의 어떤 그래프의 마이너도 아닌 그래프들이라 하고, \mathcal{H}를 \mathcal{E}의 유한한 최소 그래프 집합이라 하자. 이제 임의의 그래프 G가 주어졌다고 가정하자. 먼저 G가 \mathcal{F}에 있다면, G는 \mathcal{F}에 있고 \mathcal{H}는 \mathcal{E}의 부분 집합이므로 G는 \mathcal{H}의 마이너를 가질 수 없다. 이제 G가 \mathcal{F}에 있지 않다고 가정하자. \mathcal{F}는 마이너-폐쇄적이므로 G는 \mathcal{F}의 어떤 그래프의 마이너도 아니다. 따라서 G는 \mathcal{E}에 속하며, 고로 G는 \mathcal{H}의 마이너를 갖는다.

## 마이너-폐쇄 족의 예
다음 유한 그래프 집합들은 마이너-폐쇄적이며, 따라서 (로버트슨-시모어 정리에 의해) 금지된 마이너 특성분석을 갖는다.
* 나무 그래프(숲), 선형 숲(경로 그래프들의 분리합집합), 의사숲(pseudoforest), 선인장 그래프;
* 평면 그래프, 외평면 그래프, 꼭짓점 평면 그래프(apex graph, 평면 그래프에 정점 하나를 추가하여 형성됨), 토러스 그래프, 그리고 임의의 고정된 2차원 다양체에 매립될 수 있는 그래프;
* 유클리드 3차원 공간에 고리 없는 매립이 가능한 그래프, 그리고 유클리드 3차원 공간에 매듭 없이 매립 가능한 그래프;
* 고정된 상수 이내의 크기를 가진 피드백 정점 집합을 갖는 그래프; 콜랭 드 베르디에르 그래프 불변량이 고정된 상수 이내인 그래프; 나무 너비(treewidth), 경로 너비(pathwidth), 또는 가지 너비(branchwidth)가 고정된 상수 이내인 그래프.

## 장애물 집합
[섬네일|고리 없는 매립에 대한 장애물 집합인 [피터슨 가족]]
로버트슨-시모어 정리가 증명되기 전에도 특정 그래프 클래스에 대한 유한 장애물 집합의 몇 가지 예가 이미 알려져 있었다. 예를 들어, 모든 숲의 집합에 대한 장애물은 루프 그래프(또는 단순 그래프로 한정할 경우 정점이 3개인 순환)이다. 이는 그래프가 숲일 필요충분조건이 루프(또는 각각 정점이 3개인 순환)를 마이너로 갖지 않는 것임을 의미한다. 경로 집합에 대한 유일한 장애물은 정점이 4개이고 그 중 하나의 차수가 3인 나무이다. 이러한 경우 장애물 집합은 단일 원소를 포함하지만, 일반적으로는 그렇지 않다. 바그너의 정리에 따르면 그래프가 평면일 필요충분조건은 K_5와 K_{3,3} 중 어느 것도 마이너로 갖지 않는 것이다. 즉, 집합 \{K_5,K_{3,3}\}은 모든 평면 그래프 집합에 대한 장애물 집합이며, 사실상 유일한 최소 장애물 집합이다. 비슷한 정리에 따르면 K_4와 K_{2,3}은 외평면 그래프 집합에 대한 금지된 마이너이다.

로버트슨-시모어 정리가 이러한 결과들을 임의의 마이너-폐쇄 그래프 족으로 확장하지만, 이 결과들을 완전히 대체하는 것은 아니다. 왜냐하면 이 정리는 어떤 족에 대한 장애물 집합의 명시적인 설명을 제공하지 않기 때문이다. 예를 들어, 이 정리는 토러스 그래프 집합이 유한 장애물 집합을 갖는다는 것을 알려주지만, 그러한 집합을 제공하지는 않는다. 토러스 그래프에 대한 금지된 마이너의 전체 집합은 여전히 알려져 있지 않으나, 적어도 17,535개의 그래프를 포함하고 있다.

## 다항 시간 인식
로버트슨-시모어 정리는 계산 복잡도 이론에서 중요한 결과를 갖는다. 로버트슨과 시모어는 각 고정된 그래프 H에 대해, 어떤 그래프가 H를 마이너로 갖는지 테스트하는 다항 시간 알고리즘이 존재함을 증명했다. 이 알고리즘의 실행 시간은 (검사할 그래프의 크기에 대해) 3차 시간이지만, 마이너 H의 크기에 초다항식적으로 의존하는 상수 인자가 붙는다. 실행 시간은 가와라바야시, 고바야시, 리드에 의해 2차 시간으로 개선되었다. 그 결과, 모든 마이너-폐쇄 족 \mathcal{F}에 대해 어떤 그래프가 \mathcal{F}에 속하는지 테스트하는 다항 시간 알고리즘이 존재한다. 즉, 주어진 그래프가 \mathcal{F}의 장애물 집합에 있는 각 금지된 마이너 H를 포함하는지 확인하면 된다.

그러나 이 방법은 작동하기 위해 구체적인 유한 장애물 집합을 필요로 하며, 정리는 이를 제공하지 않는다. 정리는 그러한 유한 장애물 집합이 존재한다는 것을 증명하므로 위의 알고리즘 덕분에 문제가 다항 시간임을 입증한다. 하지만 알고리즘은 그러한 유한 장애물 집합이 제공될 때만 실제로 사용될 수 있다. 결과적으로, 이 정리는 문제가 다항 시간에 해결될 수 있음을 증명하지만, 이를 해결하기 위한 구체적인 다항 시간 알고리즘을 제공하지는 않는다. 이러한 다항성 증명은 **비구성적**(non-constructive)이다. 즉, 명시적인 다항 시간 알고리즘을 제공하지 않고 문제의 다항성을 증명한다. 많은 구체적인 사례에서, 그래프가 주어진 마이너-폐쇄 족에 속하는지 확인하는 작업은 더 효율적으로 수행될 수 있다. 예를 들어, 그래프가 평면인지 확인하는 작업은 선형 시간에 가능하다.

## 고정 매개변수 가능성
각 k에 대해 불변량이 최대 k인 그래프들이 마이너-폐쇄적인 성질을 갖는 그래프 불변량의 경우에도 동일한 방법이 적용된다. 예를 들어, 이 결과에 의해 나무 너비, 가지 너비, 경로 너비, 정점 덮개, 그리고 매립의 최소 종수는 모두 이 접근 방식에 적합하며, 임의의 고정된 k에 대해 이러한 불변량이 최대 k인지 테스트하는 다항 시간 알고리즘이 존재한다. 이때 알고리즘 실행 시간의 지수는 k에 의존하지 않는다. 지수가 k에 의존하지 않고 임의의 고정된 k에 대해 다항 시간에 해결될 수 있는 이러한 성질의 문제를 고정 매개변수 가능(fixed-parameter tractable) 문제라고 한다.

그러나 금지된 마이너의 집합을 결정하는 어려움 때문에, 이 방법은 k를 모르는 주어진 그래프에 대해 매개변수 값을 계산하는 단일 고정 매개변수 가능 알고리즘을 직접적으로 제공하지는 않는다. 또한, 이러한 결과에 수반되는 거대한 상수 인자들은 이를 매우 비실용적으로 만든다. 따라서 k에 대한 의존성을 개선한 이러한 문제들에 대한 명시적인 고정 매개변수 알고리즘 개발은 계속해서 중요한 연구 분야가 되고 있다.

## 그래프 마이너 정리의 유한 형태
프리드먼, 로버트슨, 시모어 (1987)는 다음 정리가 페아노 산술보다 훨씬 강력한 다양한 형식 체계에서 증명 불가능하면서도, ZFC보다는 훨씬 약한 체계에서 증명 가능하다는 점을 통해 독립성 현상을 보여준다는 것을 입증했다.

(여기서 그래프의 크기는 정점과 변의 총 개수이며, ≤는 마이너 순서를 나타낸다.)

프리드먼은 단순 서브큐빅(subcubic) 그래프에 대한 이 결과를 사용하여 빠르게 성장하는 함수인 SSCG를 구성한다.

## 같이 보기
* 그래프 구조 정리

## 내용주

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

## 외부 링크
* 

분류:기초관계
분류:그래프 이론 정리