휠 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
{{그래프 정보
 | name = 휠 그래프
 | image = [[파일:Wheel graphs.svg|220px]]
 | image_caption = 휠 그래프의 일부 예시
 | girth    = 3
 | diameter = ''n>4''일 때는 2<br>''n''=4일 때는 1
 | vertices = ''n''
 | edges = 2(''n'' &minus; 1)
 | chromatic_number = ''n''이 홀수일 때는 3<br/>''n''이 짝수일 때는 4
 | chromatic_index =
 | spectrum = <math>\{2 \cos(2 k \pi / (n-1))^1; </math><br><math>k = 1, \ldots, n - 2\}</math><math>\cup \{1 \pm \sqrt{n}\}</math>
 | properties = [[해밀턴 그래프|해밀턴]]<br>[[쌍대 그래프|자기쌍대]]<br>[[평면 그래프|평면]]
 | notation = ''W''<sub>''n''</sub>
}}

[[그래프 이론]]의 [[수학]] 분야에서, '''휠 그래프'''는 한 꼭짓점이 [[순환 그래프]]의 모든 꼭짓점에 연결해서 생긴 것이다. 꼭짓점이 ''n''개인 휠 그래프는 (''n''-1)[[각뿔]]의 [[n차원 뼈대|1차원 뼈대]]로 정의할 수 있다. 일부 사람들<ref>{{매스월드 | urlname = WheelGraph | title = Wheel Graph}}</ref>은 ''W''<sub>''n''</sub>을 꼭짓점이 ''n''개(n≥ 4) 있는 휠 그래프를 가리킬 때 쓴다; 다른 사람들<ref>Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, p. 655.</ref>은 대신에 ''W''<sub>''n''</sub>를 꼭짓점이 ''n''+1개(n ≥ 3) 있는 휠 그래프를 가리킬 때 쓴다. 이것은 한 꼭짓점을 길이가 ''n''인 순환 그래프의 모든 꼭짓점에 연결하면서 생긴 것이다. 이 문서의 나머지는 앞의 표기법을 사용한다. 

==조건제시 구성==
꼭짓점의 집합 {1,2,3,…,v}이 주어졌을 때, 휠 그래프의 모서리의 집합은 [[조건제시법]]에서 {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}로 표현할 수 있다.<ref>{{서적 인용|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=56|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012}}</ref>

==특성==
휠 그래프는 [[평면 그래프]]이므로 유일한 평면 매립이 있다. 더 구체적으로, 모든 휠 그래프는 [[할린 그래프]]이다. 이것은 자기쌍대이다: 어떤 휠 그래프의 [[쌍대 그래프|평면 쌍대]]는 동형 그래프이다. ''K''<sub>4</sub> = ''W''<sub>4</sub>를 제외한 모든 최대 평면 그래프는 부분 그래프로 ''W''<sub>5</sub>나 ''W''<sub>6</sub>를 가진다.

휠 그래프에는 항상 [[해밀턴 순환]]이 있고 ''W''<sub>''n''</sub>에는 <math>n^2-3n+3</math>개의 경로가 있다{{OEIS|id=A002061}}.

{| class=wikitable
|[[파일:CyclesW4.svg|320px]]<BR>휠 그래프 ''W''<sub>4</sub>의 순환 7개.
|}

''n''이 홀수일 때, ''W''<sub>''n''</sub>은 [[색칠수]]가 3인 [[완벽 그래프]]이다: 순환의 꼭짓점은 두 색으로 주어질 수 있고, 중심의 꼭짓점은 세 번째 색이 주어진다. ''n''이 짝수일 때, ''W''<sub>''n''</sub>은 [[색칠수]]가 4이고, (''n'' ≥ 6일 때) 완벽하지 않다.  ''W''<sub>7</sub>은 유클리드 평면에서 [[단위 거리 그래프]]인 유일한 휠 그래프이다.<ref>{{인용
  | last1 = Buckley | first1 = Fred | last2 = Harary | first2 = Frank | author2-link = Frank Harary
  | title = On the euclidean dimension of a wheel
  | journal = [[Graphs and Combinatorics]]
  | volume = 4
  | issue = 1
  | year = 1988
  | doi = 10.1007/BF01864150
  | pages = 23–30}}.</ref> 

휠 그래프 ''W<sub>n</sub>''의 [[색칠 다항식]]은:
{{중앙|<math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).</math>}}

[[매트로이드]] 이론에서, 매트로이드의 특히 중요한 두 특수 클래스는 ''휠 매트로이드''와 ''whirl 매트로이드''으로 둘 다 휠 그래프에서 파생된 것이다. ''k''-휠 매트로이드는 휠 그래프 ''W''<sub>''k+1''</sub>의 [[그래픽 매트로이드]]이고, ''k''-whirl 매트로이드는 ''k''-휠 매트로이드에서 휠 그래프의 외부 순환과 그 [[신장 부분 그래프]]를 독립적으로 생각해서 파생된 것이다.

휠 ''W''<sub>6</sub>은 [[램지 이론]]에서 [[에르되시 팔]]의 추측의 반례를 제공한다: 그의 추측은 완전 그래프는 같은 색칠 수를 가지는 중에서 가장 작은 램지 수를 가진다는 것이나, Faudree와 McKay (1993)는 ''K''<sub>4</sub>가 램지 수 18을 가지는 반면 같은 색칠수를 가지는 ''W''<sub>6</sub>가 램지 수 17을 가진다는 것을 보였다.<ref>{{인용
  | last1 = Faudree | first1 = Ralph J. | author1-link = Ralph Faudree
  | last2 = McKay | first2 = Brendan D. | author2-link = Brendan McKay
  | title = A conjecture of Erdős and the Ramsey number ''r''(''W''<sub>6</sub>)
  | url = http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
  | journal = J. Combinatorial Math. and Combinatorial Comput. <!-- comment to prevent DOI bot from breaking the journal name again -->
  | volume = 13
  | year = 1993
  | pages = 23–31}}.</ref> 즉, 꼭짓점이 17개인 모든 그래프 ''G''에 대해서, ''G''나 그 [[여 그래프]]가 부분 그래프로 ''W''<sub>6</sub>을 가지고 있으나, 꼭짓점이 17개인 [[페일리 그래프]]나 그 여 그래프 모두 ''K''<sub>4</sub>를 가지고 있지 않다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{위키공용분류-줄}}

{{전거 통제}}

[[분류:평면 그래프]]