다면체 그래프

Polyhedral graph
정십이면체의 슐레겔 다이어그램으로 형성된 다면체 그래프.
잘린 이십이면체 그래프의 슐레겔도

수학의 한 분야인 기하학 그래프 이론에서, 다면체 그래프는 볼록 다면체의 정점과 가장자리에서 형성된 무방향 그래프이다.또는 순수하게 그래프 이론적 관점에서 다면체 그래프는 3-vertex 연결 평면 그래프이다.

특성화

볼록 다면체의 슐레겔 다이어그램은 정점과 모서리를 유클리드 평면에서 점과 선분으로 나타내며, 외부 볼록 다각형의 하위 분할을 더 작은 볼록 다각형(다면체 그래프의 볼록 그림)으로 형성한다.교차점이 없기 때문에 모든 다면체 그래프도 평면 그래프입니다.또한, 발린스키의 정리에 따르면, 이것은 3개의 버텍스 연결 그래프이다.

Steinitz의 정리에 따르면, 이 두 개의 그래프 이론 특성은 다면체 그래프를 완전히 특성화하기에 충분하다. 즉, 정확히 3개의 버텍스 연결 평면 그래프이다.즉, 그래프가 평면 및 3-vertex 연결일 때마다 정점과 모서리가 동형 [1][2]그래프를 형성하는 다면체가 존재합니다.이러한 그래프가 주어지면, 볼록 다각형의 작은 볼록 다각형의 하위 분할로서의 표현은 Tutte [3]매립을 사용하여 찾을 수 있다.

해밀턴성과 단점

타이트는 모든 입방체 다면체 그래프(즉, 각 정점이 정확히 세 모서리에 입사하는 다면체 그래프)가 해밀턴 순환을 가지고 있다고 추측했지만, 이 추측은 다면체이지만 비 해밀턴 투테 그래프인 W. T. 투테의 반례에 의해 반증되었다.그래프가 입방체여야 하는 요건을 완화하면 훨씬 더 작은 비 해밀턴 다면체 그래프가 있다.정점과 가장자리가 가장 적은 그래프는 11-vertex 및 18-edge 허셜 그래프이며,[4] 모든 면이 삼각형인 11-vertex 비-해밀턴 다면체 그래프인 골드너-해리 그래프도 존재한다.[5]

보다 강하게는 상수α < 1(단축 지수)과 무한 다면체 그래프 패밀리가 존재하며, 그 패밀리에서 n-vertex 그래프의 가장 긴 단순 경로의 길이는 O(nα)[6][7]이다.

조합 열거

Duijvestijn은 최대 26개의 [8]모서리를 가진 다면체 그래프의 카운트를 제공한다.모서리가 6, 7, 8, ...인 그래프의 수는 다음과 같습니다.

1, 0, 1, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ...(OEIS의 시퀀스 A002840).

정점의 수로 다면체 그래프를 열거할 수도 있다: 4, 5, 6, ... 정점을 가진 그래프의 경우, 다면체 그래프의 수는 다음과 같다.

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ...(OEIS의 시퀀스 A000944).

특수한 경우

다면체 그래프는 입방체일 경우 단순 다면체 그래프이고(모든 정점은 모서리가 세 개 있음), 최대 평면 그래프일 경우 단순 다면체 그래프입니다.할린 그래프는 나무의 모든 잎을 연결하는 외부 주기를 추가하여 평면 임베디드 트리에서 형성된 그래프로서 다면체 그래프의 또 다른 중요한 하위 클래스를 형성한다.

레퍼런스

  1. ^ 귄터 M. 지글러(1995)의 폴리토피스 강연 ISBN0-387-94365-X, 제4장 "Steinitz"3-폴리토페스에 대한 정리", 페이지 103.
  2. ^ 를 클릭합니다Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, ISBN 978-0-387-40409-7.
  3. ^ 를 클릭합니다Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387.
  4. ^ 를 클릭합니다Weisstein, Eric W. "Herschel Graph". MathWorld..
  5. ^ 를 클릭합니다Weisstein, Eric W. "Goldner-Harary Graph". MathWorld..
  6. ^ 를 클릭합니다Weisstein, Eric W. "Shortness Exponent". MathWorld..
  7. ^ 를 클릭합니다Grünbaum, Branko; Motzkin, T. S. (1962), "Longest simple paths in polyhedral graphs", Journal of the London Mathematical Society, s1-37 (1): 152–160, doi:10.1112/jlms/s1-37.1.152.
  8. ^ 를 클릭합니다Duijvestijn, A. J. W. (1996), "The number of polyhedral (3-connected planar) graphs" (PDF), Mathematics of Computation, 65: 1289–1293, doi:10.1090/S0025-5718-96-00749-1.

외부 링크