바그너 정리

Wagner's theorem
K5(왼쪽)와 K3,3(오른쪽)는 비평면형 페테르센 그래프(작은 색 원과 검은색 단변)의 부차적인 역할을 합니다. 각 노란색 원 내에서 빨간색 꼭짓점과 수축 모서리를 삭제하여 마이너를 형성할 수 있습니다.
두 개의 평면 그래프와 K-free5 그래프를 형성하는 와그너 그래프의 클릭-합입니다.

그래프 이론에서 바그너 정리는 평면 그래프의 수학적 금지 그래프 특성화로, 클라우스 바그너의 이름을 따서 명명되었으며, 유한 그래프는 K(다섯 개의 정점에 있는 완전한 그래프)와5 K3,3(유틸리티 그래프, 여섯 개의 정점에 있는 완전한 이분 그래프)를 포함하지 않는 경우에만 평면이라고 말합니다. 이것은 그래프 미성년자 이론의 초기 결과 중 하나였으며 로버트슨의 전신으로 볼 수 있습니다.시모어 정리.

정의 및 진술

주어진 그래프의 평면 임베딩은 유클리드 평면에 그래프의 점과 모서리에 대한 곡선이 있는 그림으로, 모서리 쌍 사이의 유일한 교차점이 두 모서리의 공통 끝점에 있도록 합니다. 주어진 그래프의 작은 부분은 정점을 삭제하고, 간선을 삭제하고, 간선을 축소함으로써 형성되는 또 다른 그래프입니다. 모서리가 수축되면 두 끝점이 병합되어 하나의 정점을 형성합니다. 그래프 마이너 이론의 일부 버전에서는 수축으로 인한 그래프가 자기 루프 및 다중 인접을 제거하여 단순화되는 반면, 다른 버전에서는 다중 그래피가 허용되지만 이 변형은 바그너 정리에 차이가 없습니다. 바그너 정리는 모든 그래프가 평면 임베딩을 갖거나, 완전한 그래프5 K 또는 완전한 이분3,3 그래프 K 중 하나의 부형을 갖는다는 것을 말합니다. (단일 그래프가 두 가지 부형을 갖는 것도 가능합니다.)

주어진 그래프가 평면인 경우, 모든 부차적인 그래프도 평면성을 유지합니다. 정점과 에지 삭제는 평면성을 분명히 유지하며, 에지 축소는 평면성 보존 방법으로 수행할 수도 있습니다. 축소된 에지의 두 끝점 중 하나를 제자리에 두고 다른 끝점에 입사된 모든 에지를 축소된 에지의 경로를 따라 라우팅합니다. 마이너 최소 비평면 그래프는 평면이 아니라 모든 적절한 마이너(최소 하나의 삭제 또는 축소로 형성된 마이너)가 평면인 그래프입니다. 와그너 정리를 기술하는 또 다른 방법은 부-최소53,3 비평면 그래프 K와 K 두 개뿐이라는 것입니다.

바그너 정리로도 알려진 또 다른 결과는 4개의 연결된5 그래프가 K단조가 없는 경우에만 평면이라는 것입니다. 즉, 더 높은 수준의 연결성을 가정함으로써 그래프 K를3,3 특성화에서 불필요하게 만들 수 있으며, 단 하나의 금지된 부 K만5 남게 됩니다. 이에 대응하여 켈만족은–Seymour 추측은 5-연결된 그래프가 위상 부차로서5 K를 갖지 않는 경우에만 평면적이라는 것을 말합니다.

쿠라토프스키 정리의 역사와 관계

쿠라토프스키나 바그너의3,3 정리를 사용하여 하이퍼큐브 그래프가5 비평면적이라는 말없이 증명하고 K(위) 또는 K(아래) 부분 그래프를 찾습니다.

바그너는 1937년에 두 개의 정리를 모두 발표했는데,[1][2] 1930년에 쿠라토프스키 정리가 출판된 후 그래프는 동일한 두 금지 그래프 K와5 K3,3 중 하나의 세분을 부분 그래프로 포함하지 않는 경우에만 평면입니다. 어떤 의미에서 쿠라토프스키의 정리는 바그너의 정리보다 더 강한데, 세분화 과정에 의해 형성되는 각 경로에서 하나의 간선을 제외한 모든 간선을 수축시킴으로써 세분화는 동일한 유형의 마이너로 변환될 수 있지만, 마이너를 동일한 유형의 서브분할로 변환하는 것이 항상 가능한 것은 아닙니다. 그러나 두 그래프 K와5 K의3,3 경우, 이 두 그래프 중 적어도 하나를 부차적으로 갖는 그래프도 적어도 하나를 부분집합으로 갖는다는 것을 증명하는 것은 간단하므로 두 정리는 동치입니다.[3]

시사점

4개의 연결된 그래프에 대한 바그너 정리의 더 강력한 버전의 결과 중 하나는5 K단조를 갖지 않는 그래프를 특성화하는 것입니다. 이 정리는 모든 그래프가 평면이거나 더 간단한 조각으로 분해될 수 있다는 것으로 다시 표현될 수 있습니다. 이 아이디어를 사용하여 K-마이너-프리5 그래프는 평면 그래프와 8개의 정점 바그너 그래프의 조합으로 형성될 수 있는 그래프로 특징지어질 수 있으며, 이는 클리크-섬 연산에 의해 접착됩니다. 예를 들어, K는3,3 세 개의 평면 그래프의 클리크-합으로 형성될 수 있으며, 각 그래프는 사면체 그래프 K의4 복사본입니다.

와그너 정리는 그래프 부등식 이론의 중요한 선구자로서, 그래프 구조 정리(와그너의 K-5 부등식 그래프 분해의 일반화)[4]와 로버트슨-의 두 가지 깊고 광범위한 결과의 증명으로 절정에 이르렀습니다.세이모어 정리(평면 그래프의 금지된 마이너 특성화의 일반화, 미성년자를 취하는 작업으로 폐쇄된 모든 그래프 패밀리는 제한된 수의 금지된 미성년자에 의한 특성화를 가짐).[5] 와그너 정리의 유사체는 또한 마트로이드 이론으로 확장될 수 있습니다: 특히 금지된 마트로이드 미성년자의 그래픽 마트로이드 특성에 동일한 두 그래프 K와5 K3,3(세 개의 다른 금지된 구성과 함께)가 나타납니다.[6]

참고문헌

  1. ^ Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann., 114: 570–590, doi:10.1007/BF01594196, S2CID 123534907.
  2. ^ Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fund. Math. (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283.
  3. ^ Bondy, J. A.; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 269, ISBN 9781846289699.
  4. ^ Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8, MR 2188176.
  5. ^ Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5th ed.), CRC Press, p. 307, ISBN 9781439826270.
  6. ^ Seymour, P. D. (1980), "On Tutte's characterization of graphic matroids", Annals of Discrete Mathematics, 8: 83–90, doi:10.1016/S0167-5060(08)70855-0, ISBN 9780444861108, MR 0597159.