순환 그래프
1. 개요
순환 그래프는 n개의 꼭짓점과 꼭짓점 $v_i$와 $v_j$ 사이에 $i-j$가 1 또는 $n-1$일 때 변이 존재하는 그래프이다. 순환 그래프는 연결 평면 그래프이며, n이 짝수일 경우 이분 그래프이다. 순환 그래프의 색칠수는 꼭짓점 개수에 따라 다르며, 대칭군은 이면체군이다. 유향 순환 그래프는 방향이 있는 순환 그래프이며, 순환군의 케일리 그래프이다.
이미지 준비중입니다.
| 자기 동형군 | (}) |
|---|---|
| 색칠수 | 이 홀수일 경우 3, 그 외에는 2 |
| 색칠 지수 | 이 홀수일 경우 3, 그 외에는 2 |
| 속성 | 2-정규 정점-추이 변-추이 단위 거리 해밀턴 오일러 |
-
그래프 -
매케이 화살집
매케이 화살집은 유한군 G의 기약 표현을 꼭짓점으로, 텐서곱 분해를 통해 변을 정의하여 군의 표현론적 구조를 시각적으로 나타내는 도구이다. -
그래프 -
완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K<sub>n</sub>으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다. -
정규 그래프 -
페일리 그래프
-
정규 그래프 -
완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K<sub>n</sub>으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
2. 정의
크기가 인 순환 그래프 은 개의 꼭짓점 으로 구성된 (단순 무향) 그래프이며, 그 변은 다음과 같다.
:
순환 그래프는 단순 순환 그래프, 사이클, 다각형, n-각형등으로 불리기도 한다. 환상 그래프라고도 불리나, 비환상 그래프가 아닌 그래프 전반을 가리키는 경우도 있어 자주 사용되지는 않는다. n-사이클이라는 용어는 다른 상황에서 사용되기도 한다.
꼭짓점이 짝수 개인 사이클을 짝수 사이클, 홀수 개인 사이클을 홀수 사이클이라고 한다.
3. 성질
순환 그래프는 다음과 같은 특징을 갖는다.
* 연결 그래프이다.
* 인 경우 2-정규 그래프이다.
* 오일러 그래프이다.
* 해밀턴 그래프이다.
* 단위 거리 그래프이다.
* 대칭 그래프이다.
* 2-변 채색 가능 그래프이며, 정점의 수가 짝수일 때만 해당한다.
* 2-정점 채색 가능 그래프이며, 정점의 수가 짝수일 때만 해당한다. 더 일반적으로, 그래프가 이분 그래프가 되려면 홀수 사이클이 없어야 한다. (쾨니그, 1936).
* 선 그래프는 스스로와 동형이다.
:
* 크기가 3 이하인 순환 그래프는 완전 그래프이다.
:
* 크기가 4인 순환 그래프는 완전 이분 그래프이다.
:
* 순환 그래프는 정다각형으로 그릴 수 있으므로, n-순환 그래프의 대칭성은 차수가 2n인 이면체군인 n변의 정다각형의 대칭성과 동일하다.
* 하나의 닫힌 트레일을 가지며, 이는 순환 그래프 전체이다.
* 플라톤 그래프와 유사하게, 순환 그래프는 이각기둥의 골격을 형성한다. 이들의 쌍대 그래프는 쌍극자 그래프이며, 이는 호소헤드론의 골격을 형성한다.
순환 그래프 의 색칠수는 다음과 같다.
:
4. 유향 순환 그래프
유향 순환 그래프(또는 방향 순환 그래프)는 모든 간선이 같은 방향을 향하고 있는 방향이 있는 순환 그래프이다.
유향 순환 그래프는 모든 변의 방향이 동일한 사이클 그래프의 유향 버전이다. 유향 순환 그래프의 각 정점은 입차수와 출차수가 모두 1이다.
사이클이 없는 유향 그래프는 유향 비순환 그래프라고 한다.