순환 그래프

그래프 이론에서 순환 그래프(循環graph, 틀:Llang)는 정다각형의 그래프이다.

정의

크기가 $n$ 인 순환 그래프 $C_{n}$ 은 다음과 같은, $n$ 개의 꼭짓점

V (C_{n}) = {v_{1}, \dots, v_{n}}

으로 구성된 (단순 무향) 그래프이며, 그 변은 다음과 같다.

v_{i} v_{j} \in E (C_{n}) ⟺ i \equiv j \pm 1 (\mod n)

순환 그래프 $C_{n}$ 의 색칠수는 다음과 같다.

χ (C_{n}) = χ (L (C_{n})) = {\begin{matrix} n & n \leq 1 \\ 2 & n \geq 2 \land 2 ∣ n \\ 3 & n \geq 2 \land 2 ∤ n \end{matrix}

순환 그래프는 연결 평면 그래프이며, $n > 2$ 인 경우 2-정규 그래프이다. $n$ 이 짝수일 경우, $C_{n}$ 은 이분 그래프이다. 그 대칭군은 정이면체군 $Dih (n)$ 이다. 순환 그래프는 하나의 닫힌 트레일을 가지며, 이는 순환 그래프 전체이다.

순환 그래프의 선 그래프는 스스로와 동형이다.

L (C_{n}) ≅ C_{n}

크기가 3 이하인 순환 그래프는 완전 그래프이다.

C_{n} ≅ K_{n} (n = 0, 1, 2, 3)

크기가 4인 순환 그래프는 완전 이분 그래프이다.

C_{4} ≅ K_{2, 2}

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

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

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