로버트슨 –시모어 정리

Robertson–

그래프 이론에서 로버트슨-Seymour 정리[1](그래프 부정리라고도 함)는 그래프 부관계에 의해 부분적으로 정렬된 무방향 그래프가 잘 준순서를 형성한다고 말합니다.[2] 마찬가지로, 바그너 정리가 평면 그래프를 완전한 그래프 K5 또는 완전한 이분 그래프 K를3,3 마이너로 갖지 않는 그래프로 특징짓는 것과 같은 방식으로, 마이너로 닫힌 모든 그래프 계열은 금지된 마이너의 유한 집합으로 정의될 수 있습니다.

로버트슨-시모어 정리는 수학자 닐 로버트슨과 폴 D의 이름을 따서 지어졌습니다. 시모어는 1983년부터 2004년까지 500페이지가 넘는 20편의 논문에서 이를 증명했습니다.[3] 증명되기 전에, 이 정리의 진술은 독일 수학자 클라우스 바그너의 이름을 따서 바그너의 추측으로 알려졌지만, 바그너는 결코 추측한 적이 없다고 말했습니다.[4]

나무에 대한 더 약한 결과는 1937년 Andrew Vázsoni에 의해 추측되었고 1960년 Joseph Kruskal과 S에 의해 독립적으로 증명된 Kruskal의 나무 정리에 의해 암시됩니다. 타르코프스키.[5]

진술

무방향 그래프 G의 마이너는 G의 간선들의 0 이상의 수축들 및 G의 간선들 및 정점들의 삭제들의 시퀀스에 의해 G로부터 획득될 수 있는 임의의 그래프. 작은 관계는 모든 별개의 유한 무방향 그래프 집합에서 부분 순서를 형성하는데, 이는 부분 순서의 세 가지 공리를 준수하기 때문입니다: 반사적(모든 그래프는 그 자체로 작은 것), 과도적(G의 작은 것은 그 자체로 G의 작은 것), 그리고 반대칭(두 그래프 G와 H가 서로 작은 것이라면, 동형이어야 합니다. 그러나 동형인 그래프가 서로 다른 개체로 간주될 수 있는 경우, 그래프에 대한 작은 순서는 반사적이고 과도적이지만 반드시 반대 대칭은 아닌 관계인 전순서를 형성합니다.[6]

프리오더는 무한 하행 사슬도 무한 반 사슬도 포함하지 않으면 잘 준순서를 형성한다고 합니다.[7] 예를 들어, 음이 아닌 정수에 대한 일반적인 순서는 잘 준순서이지만, 모든 정수 집합에 대한 동일한 순서는 그렇지 않습니다. 왜냐하면 무한 하행 사슬 0, -1, -2, -3을 포함하기 때문입니다. 또 다른 예는 가분성에 의해 순서가 매겨진 양의 정수들의 집합인데, 이것은 무한한 내림차순 사슬이 없지만, 소수들이 무한한 반사슬을 구성하는 곳입니다.

로버트슨-시모어 정리는 유한한 무방향 그래프와 그래프 부차원이 잘 준순서를 이룬다는 것을 말합니다. 그래프 마이너 관계는 무한 내림차순을 포함하지 않습니다. 왜냐하면 각 수축 또는 삭제는 그래프의 모서리와 정점의 수를 감소시키기 때문입니다(음이 아닌 정수).[8] 이 정리의 사소한 부분은 작은 순서에 의해 서로 관련이 없는 무한 반연쇄, 무한 그래프 집합이 없다는 것입니다. 만약 S가 그래프의 집합이고, M이 최소 원소들의 각 동치 클래스에 대해 하나의 대표 그래프를 포함하는 S의 부분 집합이라면, M은 반연쇄를 형성하고, 따라서 이와 동등한 정리의 표현 방법은 임의의 무한한 그래프 집합 S에서, 동형이 아닌 최소 요소는 유한개만 있어야 합니다.

이 정리의 다른 동등한 형태는 임의의 무한한 그래프 집합 S에서, 그 중 하나는 다른 하나의 부차적인 그래프 쌍이 존재해야 한다는 것입니다.[8] 모든 무한 집합에 유한개의 최소 원소가 있다는 진술은 이 형식의 정리를 의미합니다. 왜냐하면 유한개의 최소 원소만 있다면 나머지 그래프는 각각 최소 원소 중 하나와 함께 이 유형의 쌍에 속해야 하기 때문입니다. 그리고 다른 방향에서 이 정리의 형태는 무한대의 항사슬이 존재할 수 없다는 진술을 의미합니다. 왜냐하면 무한대의 항사슬은 작은 관계에 의해 연관된 어떤 쌍도 포함하지 않는 집합이기 때문입니다.

금지된 사소한 특성

주 기사: 금지된 그래프 특성화

그래프의 패밀리 F는 F에 있는 모든 마이너가 F에 속한다면 마이너를 취하는 작전으로 폐쇄된다고 합니다. 만약 F가 소수-폐쇄 가군이라면, S를 F에 속하지 않는 그래프의 클래스(F의 여집합)라고 합니다. 로버트슨에 의하면-시모어 정리, S에는 최소 원소로 이루어진 유한 집합 H가 존재합니다. 이러한 최소 요소는 F의 금지된 그래프 특성을 형성합니다. F의 그래프는 H에 부차적으로 그래프가 없는 그래프입니다.[9] H의 구성원들은 가족 F를 위해 제외된 미성년자(또는 금지된 미성년자, 또는 경미한 장애)라고 불립니다.

예를 들어, 평면 그래프는 평면 그래프에서 모서리를 축소하거나, 그래프에서 모서리나 꼭짓점을 제거하는 것은 평면성을 파괴할 수 없습니다. 따라서 평면 그래프는 금지된 마이너 특성을 갖는데, 이 경우 와그너 정리에 의해 주어집니다: 마이너 최소 비평면 그래프의 집합 H는 완전한 그래프5 K와 완전한3,3 이분 그래프 K, 정확히 두 개의 그래프를 포함하며, 평면 그래프는 집합 {K5, K3,3}에서 마이너가 없는 그래프입니다.

모든 마이너 클로즈드 그래프 패밀리에 대한 금지된 마이너 특성의 존재는 로버트슨을 언급하는 동등한 방법입니다.시모어 정리. 모든 소수 폐족 F가 최소 금지된 소수자들로 이루어진 유한 집합 H를 갖는다고 가정하고, S를 임의의 무한한 그래프 집합이라고 가정합니다. S에서 F를 S에 부호가 없는 그래프의 계열로 정의합니다. 그러면 F는 미성년자 폐쇄형이고 최소 금지 미성년자의 유한 집합 H를 갖습니다. C를 F의 여집합이라 하자. S와 F가 서로소이기 때문에 S는 C의 부분 집합이고 H는 C의 최소 그래프입니다. G가 C에서 최소이므로 H의 그래프 G는 S에서 적절한 단사를 가질 수 없다고 생각합니다. 동시에 G는 S에 부음을 가져야 하는데, 그렇지 않으면 G는 F의 원소가 될 것이기 때문입니다. 따라서 G는 S의 원소, 즉 H는 S의 부분 집합이고, S의 다른 모든 그래프는 H의 그래프 중에서 부를 가지므로 H는 S의 최소 원소의 유한 집합입니다.

다른 의미로, 모든 그래프 집합에 최소 그래프의 유한 부분 집합이 있다고 가정하고, 작은 닫힌 집합 F가 주어지도록 합니다. 우리는 그래프가 H 안에 단소가 없는 경우에만 F 안에 있는 그래프의 집합 H를 구하고자 합니다. E를 F 안의 어떤 그래프의 단소가 아닌 그래프라고 하고, H를 E 안의 최소 그래프의 유한 집합이라고 합니다. 이제 임의의 그래프 G가 주어집니다. 먼저 G가 F에 있다고 가정합니다. G는 F에 있고 H는 E의 부분 집합이므로 G는 H에 단음을 가질 수 없습니다. 이제 G가 F에 없다고 가정합니다. 그러면 F는 마이너 클로징이므로 G는 F의 어떤 그래프의 마이너가 아닙니다. 따라서 G는 E에 있으므로 G는 H에 부음을 갖습니다.

소규모 폐쇄 가족의 예

다음과 같은 유한 그래프 집합은 마이너 클로징이며, 따라서 (로버트슨에 의해)Seymour theorem)은 다음과 같은 사소한 특성을 금지합니다.

방해물 집합

페테르센 가족, 링크리스 임베딩을 위한 장애물 세트.

유한 방해 집합의 일부 예는 로버트슨 이전에 이미 특정 등급의 그래프에 대해 알려져 있었습니다.시모어 정리가 증명되었습니다. 예를 들어, 모든 포리스트 집합에 대한 방해 요소는 루프 그래프(단순 그래프로 제한하는 경우 3개의 정점이 있는 사이클)입니다. 즉, 그래프가 포리스트(또는 세 개의 정점이 각각 있는 사이클)가 아닌 경우에만 포리스트(forest)임을 의미합니다. 경로 집합에 대한 유일한 장애물은 4개의 정점을 가진 트리이며, 그 중 하나는 차수가 3입니다. 이러한 경우 장애물 집합에는 단일 요소가 포함되어 있지만 일반적으로 그렇지 않습니다. 바그너의 정리는 그래프가5 K와3,3 K를 모두 부로 갖지 않는 경우에만 평면이라는 것을 말합니다. 즉, 집합 {K53,3, K}는 모든 평면 그래프의 집합에 대한 방해 집합이며, 실제로는 고유한 최소 방해 집합입니다. 유사한 정리는4 K와2,3 K가 외평면 그래프의 집합에서 금지된 부차적인 것임을 나타냅니다.

로버트슨 호가 비록-Seymour 정리는 임의의 마이너 폐쇄 그래프 패밀리로 이러한 결과를 확장하지만, 어떤 패밀리에 대한 방해 집합에 대한 명시적인 설명을 제공하지 않기 때문에 이러한 결과를 완전히 대체할 수는 없습니다. 예를 들어, 토로이드 그래프의 집합이 유한 방해 집합을 가지지만 그러한 집합을 제공하지는 않습니다. 토로이드 그래프에 대한 금지된 미성년자의 전체 집합은 알려지지 않았지만 적어도 17,535개의 그래프가 포함되어 있습니다.[11]

다항식 시간 인식

로버트슨-시모어 정리는 로버트슨과 시모어의 증명으로 계산 복잡도에서 중요한 결과를 가져오는데, 이는 각 고정 그래프 h에 대해 그래프가 마이너를 갖는지 여부를 테스트하기 위한 다항 시간 알고리즘이 있다는 것을 증명하기 때문입니다. 이 알고리즘의 실행 시간은 큐빅(확인할 그래프의 크기)이지만, 상수 요인은 마이너 h의 크기에 초다중적으로 의존합니다. 카와라바야시, 고바야시, 리드에 의해 주행 시간이 4차로 향상되었습니다.[12] 따라서, 모든 마이너-클로즈드 패밀리 F에 대해 그래프가 F에 속하는지 여부를 테스트하는 다항 시간 알고리즘이 존재합니다: 단지 주어진 그래프가 F의 방해 집합에서 금지된 각각의 마이너 h에 대해 h를 포함하는지 여부를 확인하기만 하면 됩니다.[13]

그러나 이 방법을 사용하려면 특정 유한 방해 집합이 필요하며 정리는 방해 집합을 제공하지 않습니다. 이 정리는 이러한 유한 방해 집합이 존재함을 증명하며, 따라서 문제는 위 알고리즘 때문에 다항식입니다. 그러나 알고리즘은 그러한 유한한 방해 집합이 제공되는 경우에만 실제로 사용될 수 있습니다. 결과적으로 이 정리는 문제가 다항 시간 내에 해결될 수 있음을 증명하지만, 이를 해결하기 위한 구체적인 다항 시간 알고리즘을 제시하지는 않습니다. 이러한 다항식의 증명은 비건설적입니다: 명시적인 다항식 시간 알고리즘을 제공하지 않고 문제의 다항식을 증명합니다.[14] 많은 구체적인 경우 그래프가 주어진 소밀폐 패밀리에 속하는지 여부를 확인하는 것이 더 효율적으로 수행될 수 있습니다. 예를 들어 그래프가 평면인지 여부를 확인하는 것은 선형 시간에 수행될 수 있습니다.

고정 파라미터 트랙터빌리티

각 k에 대해 최대 k가 불변인 그래프가 마이너 폐쇄인 특성을 갖는 그래프 불변량의 경우 동일한 방법이 적용됩니다. 예를 들어, 이 결과에 의해 트리 너비, 가지 너비 및 경로 너비, 정점 덮개 및 임베딩의 최소 속이 모두 이 접근 방식에 적합하며, 임의의 고정 k에 대해 이러한 불변량이 최대 k인지 여부를 테스트하는 다항 시간 알고리즘이 존재하며, 이 알고리즘의 실행 시간 내의 지수는 k에 의존하지 않습니다. k에 의존하지 않는 지수를 갖는 임의의 고정된 k에 대해 다항 시간 내에 해결될 수 있는 이 성질의 문제를 고정 매개 변수 트랙터블이라고 합니다.

그러나 이 방법은 금지된 미성년자 집합을 결정하기 어렵기 때문에 k가 알려지지 않은 주어진 그래프의 매개 변수 값을 계산하기 위한 단일 고정 매개 변수 추출 알고리즘을 직접 제공하지 않습니다. 또한 이러한 결과에 관련된 큰 상수 요인은 매우 비현실적입니다. 따라서 k에 대한 의존성이 개선된 이러한 문제에 대한 명시적 고정 매개변수 알고리즘의 개발은 중요한 연구 라인으로 계속되어 왔습니다.

그래프 부정리의 유한한 형태

Friedman, Robertson & Seymour(1987)는 다음 정리가 Peano 산술보다 훨씬 강력한 다양한 형식적 시스템에서는 증명할 수 없지만 ZFC보다 훨씬 약한 시스템에서는 증명할 수 있음으로써 독립 현상을 나타냄을 보여주었습니다.

정리: 모든 양의 정수 n에 대하여, G1, ..., G가m 유한 무방향 그래프의 수열이라면,
여기서 각i G는 최대 n+i의 크기를 가지며, 어떤 j < k에 대해서는j G ≤ G입니다k.

(여기서 그래프의 크기는 정점과 에지의 총 수이고 ≤는 작은 순서를 나타냅니다.)

참고 항목

메모들

  1. ^ 비엔스톡 & 랭스턴 (1995).
  2. ^ 로버트슨 & 시모어 (2004).
  3. ^ Robertson and Seymour (1983, 2004); 디스텔 (2005, 페이지 333).
  4. ^ 디스텔 (2005, 페이지 355).
  5. ^ Diestel (2005, pp. 335–336); Lovász (2005), Section 3.3, pp. 78–79.
  6. ^ 예를 들어, Bienstock & Langston(1995), 섹션 2, "웰 준주문"을 참조하십시오.
  7. ^ 디스텔 (2005, 페이지 334).
  8. ^ a b Lovász (2005, p. 78).
  9. ^ Bienstock & Langston (1995), Corollary 2.1.1; Lovász (2005), 정리 4, 페이지 78.
  10. ^ a b Lovász (2005, pp. 76–77).
  11. ^ Myrvold & Woodcock (2018).
  12. ^ Kawarabayashi, Kobayashi & Reed (2012)
  13. ^ Robertson & Seymour (1995); Bienstock & Langston (1995), Theorem 2.1.4 and Corollary 2.1.5; Lovász (2005), 정리 11, 83쪽.
  14. ^ 펠로우 & 랭스턴(1988); 비엔스톡 & 랭스턴(1995), 섹션 6.

참고문헌

외부 링크