순환 그래프
그래프 이론에서 순환 그래프(循環graph, 영어: cycle graph)는 정다각형의 그래프이다.
크기가
인 순환 그래프
은 다음과 같은,
개의 꼭짓점
![{\displaystyle V(C_{n})=\{v_{1},\dots ,v_{n}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16c4b03de3c75f3c78f7377117a12f35acccf158)
으로 구성된 (단순 무향) 그래프이며, 그 변은 다음과 같다.
![{\displaystyle v_{i}v_{j}\in E(C_{n})\iff i\equiv j\pm 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9b3ebf5561ca0dbefacfe77a9848eb4cd64e29d)
순환 그래프
의 색칠수는 다음과 같다.
![{\displaystyle \chi (C_{n})=\chi (L(C_{n}))={\begin{cases}n&n\leq 1\\2&n\geq 2\land 2\mid n\\3&n\geq 2\land 2\nmid n\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b1aaa4364afe3c919067787b7013d3ae028cf05)
순환 그래프는 연결 평면 그래프이며,
인 경우 2-정규 그래프이다.
이 짝수일 경우,
은 이분 그래프이다. 그 대칭군은 정이면체군
이다. 순환 그래프는 하나의 닫힌 트레일을 가지며, 이는 순환 그래프 전체이다.
순환 그래프의 선 그래프는 스스로와 동형이다.
![{\displaystyle L(C_{n})\cong C_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fe2616faf7c3389bef8f05103a5164ee4411f8c)
크기가 3 이하인 순환 그래프는 완전 그래프이다.
![{\displaystyle C_{n}\cong K_{n}\qquad (n=0,1,2,3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/370432650990597a5179dbe5177a4e7c9a1e4358)
크기가 4인 순환 그래프는 완전 이분 그래프이다.
![{\displaystyle C_{4}\cong K_{2,2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cae553747bf2e9169257c5ea62ad58770c6cd07f)
유향 순환 그래프[편집]
유향 순환 그래프 또는 방향 순환 그래프는 방향이 있는 순환 그래프이며 모든 간선이 같은 방향을 지향하고 있다.
방향 그래프에서 각 유향 순환으로부터 적어도 하나의 간선을 포함하는 간선의 집합은 피드백 아크 집합(feedback arc set)이라고 한다. 이와 비슷하게 각 유향 순환으로부터 적어도 하나의 정점을 포함하는 정점의 집합은 피드백 버텍스 집합이라고 한다.
순환군의 경우 유향 순환 그래프는 케일리 그래프이다.
같이 보기[편집]
외부 링크[편집]