순환 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Undirected_6_cycle.svg|섬네일|오른쪽|순환 그래프 <math>C_6</math>]]
[[그래프 이론]]에서 '''순환 그래프'''(循環graph, {{llang|en|cycle graph}})는 [[정다각형]]의 [[그래프]]이다.

== 정의 ==
크기가 <math>n</math>인 '''순환 그래프''' <math>C_n</math>은 다음과 같은, <math>n</math>개의 꼭짓점
:<math>V(C_n)=\{v_1,\dots,v_n\}</math>
으로 구성된 (단순 무향) [[그래프]]이며, 그 변은 다음과 같다.
:<math>v_iv_j\in E(C_n)\iff i\equiv j\pm1\pmod n</math>

== 성질 ==
순환 그래프 <math>C_n</math>의 [[색칠수]]는 다음과 같다.
:<math>\chi(C_n)=\chi(L(C_n))=\begin{cases}n&n\le1\\2&n\ge2\land 2\mid n\\3&n\ge2\land 2\nmid n\end{cases}</math>
순환 그래프는 [[연결 그래프|연결]] [[평면 그래프]]이며, <math>n>2</math>인 경우 2-[[정규 그래프]]이다. <math>n</math>이 짝수일 경우, <math>C_n</math>은 [[이분 그래프]]이다. 그 [[대칭군 (기하학)|대칭군]]은 [[정이면체군]] <math>\operatorname{Dih}(n)</math>이다. 순환 그래프는 하나의 [[그래프 이론 용어|닫힌 트레일]]을 가지며, 이는 순환 그래프 전체이다.

순환 그래프의 [[선 그래프]]는 스스로와 동형이다.
:<math>L(C_n)\cong C_n</math>

크기가 3 이하인 순환 그래프는 [[완전 그래프]]이다.
:<math>C_n\cong K_n\qquad(n=0,1,2,3)</math>
크기가 4인 순환 그래프는 [[완전 이분 그래프]]이다.
:<math>C_4\cong K_{2,2}</math>

== 유향 순환 그래프 ==
'''유향 순환 그래프''' 또는 '''방향 순환 그래프'''는 방향이 있는 순환 그래프이며 모든 간선이 같은 방향을 지향하고 있다.

[[방향 그래프]]에서 각 유향 순환으로부터 적어도 하나의 간선을 포함하는 간선의 집합은 [[피드백 아크 집합]](feedback arc set)이라고 한다. 이와 비슷하게 각 유향 순환으로부터 적어도 하나의 정점을 포함하는 정점의 집합은 [[피드백 버텍스 집합]]이라고 한다.

[[순환군]]의 경우 유향 순환 그래프는 [[케일리 그래프]]이다.

== 같이 보기 ==
* [[완전 이분 그래프]]
* [[완전 그래프]]
* [[무변 그래프]]
* [[경로 그래프]]

== 외부 링크 ==
* {{매스월드|id=CycleGraph|title=Cycle graph}}

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