정규 그래프 문서 원본 보기

[[파일:Petersen graph blue.svg|섬네일|[[페테르센 그래프]]는 3-정규 그래프이다.]]
[[파일:Biclique_K_3_3.svg|섬네일|[[완전 이분 그래프]] <math>K_{3,3}</math>는 3-정규 그래프이다.]]
'''정규 그래프'''(定規graph, {{llang|en|regular graph}})는 모든 꼭짓점이 동일한 수의 이웃을 가지는 [[그래프]]이다. 즉, 모든 꼭짓점이 같은 차수를 가진다.

== 정의 ==
자연수 <math>k\in\mathbb N</math>가 주어졌다고 하자. 만약 어떤 [[그래프]]에서 모든 꼭짓점의 차수(꼭짓점에 잇닿은 변의 수)가 <math>k</math>라면, 이 그래프를 '''<math>k</math>-정규 그래프'''(<math>k</math>-定規graph, {{llang|en|<math>k</math>-regular graph}})라고 한다.

3-정규 그래프는 '''삼차 그래프'''(三次graph, {{llang|en|cubic graph|큐빅 그래프}})라고도 한다.

== 성질 ==
'''내시윌리엄스 정리'''({{llang|en|Nash-Williams theorem}})에 따르면, <math>2k+1</math>개의 꼭짓점을 갖는 <math>k</math>-정규 그래프는 항상 [[해밀턴 순환]]을 갖는다.

3-정규 그래프의 최소 교차점 개수({{llang|en|crossing number}})를 찾는 문제는 [[NP-난해]]이다.<ref name="Hlinny2006">{{저널 인용|first=Petr|last=Hliněný|title=Crossing number is hard for cubic graphs|journal=Journal of Combinatorial Theory B|volume=96|issue=4|pages=455–471|year=2006|doi=10.1016/j.jctb.2005.09.009|언어=en}}</ref>

=== 존재 ===
두 자연수 <math>n,k\in\mathbb N</math>이 주어졌을 때, 다음 두 조건이 서로 [[동치]]이다.
* <math>n</math>개의 꼭짓점을 갖는 <math>k</math>-정규 그래프가 존재한다.
* <math>n\ge k+1</math>이며 <math>2\mid nk</math>이다.

== 예 ==
0-정규 그래프는 [[무변 그래프]]이다. 1-정규 그래프의 연결 성분은 [[경로 그래프]] <math>K_2=P_2</math>이다. 2-정규 그래프의 연결 성분은 [[순환 그래프]]나 무한 [[경로 그래프]]이다.

<math>n</math>개의 꼭짓점의 [[완전 그래프]] <math>K_n</math>은 <math>n-1</math>-정규 그래프이다.

<gallery>
파일:0-regular_graph.svg|0-정규 그래프
파일:1-regular_graph.svg|1-정규 그래프
파일:2-regular_graph.svg|2-정규 그래프
파일:3-regular_graph.svg|3-정규 그래프
</gallery>

== 역사 ==
[[1880년]]에 [[피터 거스리 테이트]]는 모든 삼차 그래프는 [[해밀턴 경로]]를 가진다는 추측을 내놓았지만, [[1946년]]에 [[윌리엄 토머스 텃]]이 46개 꼭짓점을 가진 반례를 찾았다.

[[1971년]]에 [[윌리엄 토머스 텃]]은 모든 [[이분 그래프|이분]] 삼차 그래프는 해밀턴 회로가 있을 것이라고 추측했지만, 조지프 호턴({{llang|en|Joseph Horton}})이 96개 꼭짓점을 가진 반례를 찾아냈다.

모든 이분 삼차 그래프가 해밀턴 회로가 짝수개 존재한다는 것은 증명되어 있다.

내시윌리엄스 정리는 영국의 수학자 크리스핀 내시윌리엄스({{llang|en|Crispin Nash-Williams}})가 증명하였다.

== 같이 보기 ==
* [[강한 정규 그래프]]
* [[무어 그래프]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=RegularGraph|title=Regular graph}}
* {{매스월드|id=CubicGraph|title=Cubic graph}}
* {{매스월드|id=StronglyRegularGraph|title=Strongly regular graph}}
* {{매스월드|id=WeaklyRegularGraph|title=Weakly regular graph}}
* {{매스월드|id=Snark|title=Snark}}
{{위키데이터 속성 추적}}

[[분류:정규 그래프| ]]
[[분류:그래프족]]