피터슨 그래프

피터슨 그래프
피터슨 그래프는 5개의 스포크가 있는 펜타그램으로 가장 일반적으로 그려진다.
이름을 따서 명명됨	율리우스 피터슨
정점	10
가장자리	15
반지름	2
지름	2
둘레	5
자동형성	120(S5)
색수	3
색도 지수	4
분수 색도 지수	3
속	1
특성.	큐빅 강력정규 거리-변환 스나크
그래프 및 모수 표

그래프 이론의 수학적 분야에서 피터슨 그래프는 10개의 정점과 15개의 가장자리를 가진 비방향 그래프다.그것은 그래프 이론의 많은 문제들에 유용한 예와 counterexample의 역할을 하는 작은 그래프 입니다.피터슨 그래프는 줄리어스 피터슨의 이름을 따온 것인데, 그는 1898년에 3엣지 색상이 없는 가장 작은 다리 없는 입방형 그래프로 만들었다.^[1]

비록 이 그래프가 일반적으로 피터슨에게 인정되지만, 사실 이 그래프는 A. B. 켐페 (1886)의 논문에서 12년 전에 처음 나타났다.켐페는 정점이 데사게스 구성의 10개 선을 나타낼 수 있으며, 가장자리는 구성의 10개 지점 중 하나에서 충족되지 않는 선 쌍을 나타낸다고 관찰했다.

도날드 크누스는 피터슨 그래프가 "일반적으로 그래프의 경우 무엇이 진실일 수 있는지에 대한 많은 낙관적인 예측에 대한 중요한 예시 역할을 하는 주목할 만한 구성"^[2]이라고 말한다.

피터슨 그래프는 열대 기하학에서도 나타난다.피터슨 그래프 위의 원뿔은 5개의 점으로 된 이성적인 열대 곡선의 모듈리 공간과 자연스럽게 동일시된다.

시공

피터슨 그래프는 $K{\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$ ${\$의 선 그래프를 보완한 것이다$.$또한 Kneser 그래프 ${\displaystyle {\mathrm{K}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {5\mathrm{}}_{}}$,${\displaystyle {}_{}}$2 ${\$ 이것은 5-element 세트의 각 2-element 부분 집합에 대해 하나의 꼭지점을 가지고 있고, 해당하는 2-element 하위 집합이 서로 분리되어 있는 경우에만 두 개의 꼭지점이 에지로 연결되어 있다는 것을 의미한다$.$$K$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{2n}}_{}}$- ${\displaystyle 1_{}}$,${\displaystyle {\mathrm{n}}_{}}$- ${\displaystyle 1_{}}$ ${\$ 형식의 크네저 그래프로서 홀수 그래프의 예다.

기하학적으로 Petersen 그래프는 헤미-도면체의 정점과 가장자리, 즉 반대점, 선, 면이 함께 식별되는 도면체에서 형성된 그래프다.

임베딩스

피터슨 그래프는 평면이 아니다.모든 비플래너 그래프는 전체 $그래프{\displaystyle {}_{}}$ ${\displaystyle {K\mathrm{}}_{}}$ 5${\$또는 전체 양분 ${\displaystyle {그래프\mathrm{}}_{}}$ K${\displaystyle 3_{}}$, 3$${\$displaystyle K_{3,3}$중 하나를 Minor로 포함하지만 Petersen 그래프는 둘 다 Minor로 표시한다.$K{\displaystyle {}_{}}$ ${\$ 부차는$$ 첫 번째 그림에서 5개의 짧은 가장자리 등 완벽한 매칭의 가장자리를 수축시켜 형성할 수 있다.$K{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$,${\displaystyle 3_{}}$ ${\$ 단점은$$ 하나의 꼭지점(예: 3-대칭 도면의 중심 꼭지점)을 삭제하고 삭제된 꼭지점의 각 인접점에 가장자리 사건을 수축시킴으로써 형성될 수 있다.

피터슨 그래프의 가장 보편적이고 대칭적인 평면 도면은 펜타곤 내에서 5개의 교차점이 있다.그러나 이것은 교차를 최소화하기 위한 최선의 도면이 아니다. 교차를 두 개만 가진 다른 도면(그림에 표시됨)이 존재한다.비 평면적이기 때문에 어떤 도면에도 최소한 하나의 교차점이 있으며, 어떤 도면에서도 교차 모서리를 제거하면 비 평면적으로 남아 있고 다른 교차점이 있으므로 교차 번호는 정확히 2이다.이 도면의 각 가장자리는 최대 한 번에 교차되므로 Petersen 그래프는 1-평면이다.토러스에서 피터슨 그래프는 가장자리 교차 없이 그려질 수 있다. 그러므로 그것은 방향성 있는 속 1을 가지고 있다.

또한 피터슨 그래프는 모든 가장자리의 길이가 같은 방법으로 평면에 그릴 수 있다(교차 포함).즉, 단위 거리 그래프다.

피터슨 그래프를 교차 없이 삽입할 수 있는 가장 단순한 방향성이 없는 표면은 투영면이다.이것은 피터슨 그래프의 헤미-도-도-카헤드론 구조(그림에 나타나 있음)에 의해 주어지는 내장이다.투영 평면 임베딩은 또한 도면 중앙에 있는 5점 별 안에 십자 캡을 배치하고 이 십자 캡을 통해 별 가장자리를 라우팅함으로써 피터슨 그래프의 표준 오각형 도면에서 형성될 수 있다. 결과 도면은 6개의 오각형 면을 가지고 있다.이 구성은 정규 지도를 형성하고 피터슨 그래프에 방향성이 없는 속 1이 있음을 보여준다.

대칭

Petersen 그래프는 매우 규칙적이다(10,3,0,1) 시그니처 srg(10,3,0,1)).또한 대칭이며, 가장자리 전이 및 정점 전이라는 뜻이다.보다 강하게 말하면, 3arc-transitive이다. 피터슨 그래프의 모든 방향의 3 에지 경로는 그래프의 대칭에 의해 다른 모든 경로로 변환될 수 있다.^[3]13입방 거리 정규 그래프 중 하나이다.^[4]

피터슨 그래프의 자동형성 그룹은 대칭 그룹 ${\displaystyle {S\mathrm{}}_{}}$ 5${\$이다$.$ 피터슨 그래프에$$ $대한{\displaystyle {}_{}}$ ${\displaystyle {S\mathrm{}}_{}}$ 5$${\$displaystyle S_{5}$의 작용은 크네저 그래프로서 그 구성에서 비롯된다.인접한 정점을 식별하지 못하는 피터슨 그래프의 모든 동형성은 자동형이다.그림에서 볼 수 있듯이 피터슨 그래프의 도면은 5방향 또는 3방향 대칭을 나타낼 수 있지만, 도면이 그래프의 전체 대칭 그룹을 나타내도록 평면에서는 피터슨 그래프를 그릴 수 없다.

높은 대칭도에도 불구하고 피터슨 그래프는 케이리 그래프가 아니다.케이리 그래프가 아닌 가장 작은 정점-변환 그래프다.^[5]

해밀턴의 경로와 순환

피터슨 그래프는 해밀턴의 경로는 있지만 해밀턴의 경로는 없다.해밀턴 사이클이 없는 브릿지리스 입방 그래프 중 가장 작다.해밀턴 주기는 없지만 정점을 삭제하면 해밀턴 주기가 되며, 가장 작은 해밀턴 주기가 된다는 뜻이다.

해밀턴 사이클이 없는 유한 연결 정점 변환 그래프로서 피터슨 그래프는 로바스 추측의 변종에 대한 백범례지만, 추측의 규범적 공식은 해밀턴 경로를 요구하고 피터슨 그래프에 의해 검증된다.

해밀턴 주기가 없는 연결된 정점 변환 그래프는₂ 전체 그래프 K, 피터슨 그래프, 콕시터 그래프, 각 정점을 삼각형으로 대체하여 피터슨과 콕시터 그래프에서 파생된 두 개의 그래프 등 5개만 알려져 있다.^[6]G가 최대 3r + 1 정점을 가진 2-연결 r-정규 그래프라면 G는 해밀턴식 그래프, G는 피터슨 그래프다.^[7]

Petersen 그래프에 해밀턴 사이클 C가 없는지 확인하려면 절단의 가장자리가 내측 사이클과 외측 사이클을 분리하는 것을 고려하십시오.해밀턴 사이클이 있는 경우 이 에지 중 짝수를 선택해야 한다.이들 중 2개만 선택한 경우, 이들의 엔드-버스는 두 개의 5주기 내에 인접해야 하며, 이는 불가능하다.그래서 그들 중 4명이 선택되었다.절단의 상단 가장자리가 선택되지 않았다고 가정한다(다른 모든 경우는 대칭에 의해 동일하다).외부 사이클의 5개 에지 중 2개의 상단 에지를 선택해야 하며, 2개의 측면 에지는 선택하지 않아야 하며, 따라서 하단 에지는 선택해야 한다.내부 사이클의 상단 두 모서리를 선택해야 하지만, 이것은 비스팬 사이클을 완료하며, 이것은 해밀턴 사이클의 일부가 될 수 없다.또는 해밀턴 사이클이 있는 10Vertex 3 정규 그래프를 설명할 수도 있고, 피터슨 그래프에서 어떤 사이클보다 짧은 사이클을 각각 찾아내어 그 중 어느 것도 피터슨 그래프라는 것을 보여줄 수도 있다.어떤 10Vx 해밀턴 3-정기 그래프는 10Vx 사이클 C와 5개의 화음으로 구성된다.만약 어떤 화음이 C를 따라 2-3번 거리에 있는 두 개의 정점을 서로 연결하는 경우, 그래프는 3 사이클 또는 4 사이클을 가지므로 피터슨 그래프가 될 수 없다.만약 두 개의 화음이 C를 따라 거리 4에서 C의 정점과 정점에 연결된다면, 다시 4 사이클이 있다.유일하게 남은 경우는 뫼비우스 사다리가 각각의 반대 정점 쌍을 현으로 연결하여 형성한 것으로, 다시 4 사이클이 있다.피터슨 그래프는 5번째 기수를 가지기 때문에 이런 식으로 형성될 수 없고 해밀턴 사이클도 없다.

컬러링

피터슨 그래프에는 색수 3이 있는데, 즉, 정점은 같은 색의 정점을 연결하지 않는 에지가 없는 세 가지 색상으로 색칠할 수 있다는 뜻이다.브룩스의 목록 배색 정리에 의해 목록 배색 3가지 색상이 있다.

피터슨 그래프는 색지수 4를 가지고 있다; 가장자리를 색칠하는 것은 네 가지 색을 필요로 한다.색도 지수 4와 연결된 브리지리스 입방 그래프로서 피터슨 그래프는 스나크다.그것은 가능한 가장 작은 저격이며, 1898년부터 1946년까지 알려진 유일한 저격수였다.2001년 로버트슨, 샌더스, 시모어, 토마스가 발표한 결과인 스나크 정리에는 모든 스나크가 피터슨 그래프를 마이너로서 갖고 있다고 명시돼 있다.^[8]

또한 그래프에는 부분 색도 지수 3이 있어 색도 지수와 부분 색도 지수 간의 차이가 1만큼 클 수 있음을 증명한다.오랜 세월 동안 지속되어온 골드버그-시모어 추측에 의하면 이것이 가능한 가장 큰 격차라고 한다.

피터슨 그래프의 Thue 번호(색도 지수의 변종)는 5이다.

피터슨 그래프는 모든 대칭을 깨는 (부적절한) 색상에 적어도 세 가지 색상을 요구한다. 즉, 그 구별 숫자는 세 가지다.전체 그래프를 제외하고 구분 번호가 2개가 아닌 유일한 Kneser 그래프다.^[9]

기타 속성

피터슨 그래프:

• 3개 연결로 되어 있고, 따라서 3개의 엣지로 연결되어 있고 브리지가 없다.용어집을 봐.
• 독립 번호 4를 가지고 있고 3파리다.용어집을 봐.
• 입방체, 3번 우위, 3번 우위, 2번 우위.
• 6개의 뚜렷한 완벽한 짝을 가지고 있다.
• 둘레 5의 가장 작은 입방 그래프(독특한${\displaystyle }$(${\displaystyle 3,}$ 5$){\displaystyle (3,5)}$ -cage이다.실제로 정점이 10개밖에 없기 때문에 고유한$({\displaystyle }$3${\displaystyle ,}$ ${\displaystyle 5}$) ${\디스플레이$ 스타일$(3,5$) -Moore$$ 그래프)이다.^[10]
• 콜린 드 베르디에르 그래프의 불변 μ = 5가 있는 가장 작은 입방 그래프 입니다.^[11]
• 3번 경찰관의 ^[12]가장 작은 그래프야
• 반지름 2와 지름 2를 가지고 있다.직경 2의 입방형 그래프 중 가장 크다.^[13]
• 그래프 스펙트럼 -2, -2, -2, 1, 1, 1, 1, 1, 1, 3,
• 스패닝 트리 2000개가 있는데, 10입방 그래프의 대부분을 차지한다.^[14]
• has chromatic polynomial ${\displaystyle t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)}$.^[15]
• 특성 다항식$({\displaystyle t}$- ${\displaystyle 1{}^{}}$) ${\displaystyle {5\mathrm{}}^{}{}^{}}$( ${\displaystyle t}$+ ${\displaystyle 2{}^{}}$) ${\displaystyle {4\mathrm{}}^{}{}^{}}$( t${\displaystyle }$- ${\displaystyle 3}$) ${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)$을 포함하며$,$ 이는 스펙트럼이 모두 정수로 구성되는 그래프인 통합 그래프다.

피터슨 컬러링 추측

DeVos, Nesetril, Raspaud에 따르면 그래프 G의 주기는 C${\displaystyle \mathrm{set}}$ ${\displaystyle E}$( G $){\displaystyle C\subseteq E(G)}$를 설정하여 그래프의 모든 꼭지점(V(G), C)이 일정한 정도를 갖도록 한다$$.If ${\displaystyle G,H}$ are graphs, we define a map ${\displaystyle \phi :E(G)\to E(H)}$ to be cycle-continuous if the pre-image of every cycle of ${\displaystyle H}$ is a cycle of ${\displaystyle G}$. A fascinating conjecture of Jaeger asserts that every bridgeless graph has a cycle-continuous가 Petersen 그래프에 매핑됨.재거는 이 추측이 5주기 더블커버 추측과 버지-풀커슨 추측을 내포하고 있다는 것을 보여주었다."^[16]

관련 그래프

일반화된 피터슨 그래프 $G{\displaystyle (n}$, k${\displaystyle }$) ${\displaystyle G(n,k)}$은 슐래플리 기호 {n/k}^[17]을(를) 사용하여 일반 n곤의 정점을 별 폴리곤의 해당 정점에 연결함으로써 형성된다$$.예를 들어, 이 표기법에서 피터슨 그래프는 $G{\displaystyle }$( ${\displaystyle 5}$ ,${\displaystyle }$2$){\displaystyle G$(5,$2)}$: 오각형 별과 5점 별의 해당 정점을 연결하여 형성할 수 있으며, 별의 가장자리는 매 초 정점을 연결한다.The generalized Petersen graphs also include the n-prism ${\displaystyle G(n,1)}$ the Dürer graph ${\displaystyle G(6,2)}$, the Möbius-Kantor graph ${\displaystyle G(8,3)}$, the dodecahedron ${\displaystyle G(10,2)}$, the Desargues graph ${\displaystyle G(10$$,$$3)}$ 및$$ Nauru 그래프 G${\displaystyle }$($12{\displaystyle ,}$ ${\displaystyle 5}$ ) $displaystyle$ G $(12,5)}$.

피터슨 계열은 Δ-Y 또는 Y-Δ 변환을 0개 이상 적용하여 피터슨 그래프에서 구성할 수 있는 7개의 그래프로 구성된다.완전한 그래프 K도₆ 피터슨 계열에 있다.이 그래프들은 무연장 내장형 그래프, 즉 그래프의 두 사이클이 연결되지 않는 방식으로 3차원 공간에 내장될 수 있는 그래프에 대해 금지된 미성년자를 형성한다.^[18]

Clebsch 그래프에는 유도 하위 그래프로서 Petersen 그래프의 많은 복사본이 포함되어 있다. Clebsch 그래프의 각 꼭지점 v에 대해, v의 비근위 10개는 Petersen 그래프의 복사본을 유도한다.

메모들

참조

위키미디어 커먼즈에는 피터슨 그래프와 관련된 미디어가 있다.

• Exoo, Geoffrey; Harary, Frank; Kabell, Jerald (1981), "The crossing numbers of some generalized Petersen graphs", Mathematica Scandinavica, 48: 184–188, doi:10.7146/math.scand.a-11910.
• Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5.
• Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, doi:10.2277/0521435943, ISBN 0-521-43594-3.
• Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050
• Kempe, A. B. (1886), "A memoir on the theory of mathematical form", Philosophical Transactions of the Royal Society of London, 177: 1–70, doi:10.1098/rstl.1886.0002
• Lovász, László (1993), Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN 0-444-81504-X.
• Petersen, Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens, 5: 225–227
• Schwenk, A. J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory, Series B, 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6
• Valdes, L. (1991), "Extremal properties of spanning trees in cubic graphs", Congressus Numerantium, 85: 143–160.
• Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory, 6 (2): 152–164, doi:10.1016/S0021-9800(69)80116-X

외부 링크

• Weisstein, Eric W. "Petersen Graph". MathWorld.
• 온라인 정수 시퀀스 백과사전의 피터슨 그래프