순환 그래프
Cycle graph| 순환 그래프 | |
|---|---|
 길이 6의 주기 그래프 | |
| 꼭지점 | n |
| 가장자리 | n |
| 둘레 | n |
| 자기동형 | 2n(Dn) |
| 색수 | n이 홀수일 경우 3 2 그 이외의 경우 |
| 색채 지수 | n이 홀수일 경우 3 2 그 이외의 경우 |
| 스펙트럼 | [1] |
| 특성. | 2-정규 정점-이행 엣지-트랜시 단위 거리 해밀턴식 오일러의 |
| 표기법 | Cn. |
| 그래프 및 매개 변수 표 | |
그래프 이론에서 순환 그래프 또는 원형 그래프는 단일 사이클로 구성된 그래프이며, 다른 말로, 닫힌 사슬에 연결된 몇 개의 꼭지점(그래프가 단순하다면 최소 3개)으로 구성됩니다.꼭지점이 n개인 주기 그래프를 [2]C라고n 합니다.C의n 꼭지점 수는 모서리 수와 같으며, 모든 꼭지점에는 도수 2가 있습니다. 즉, 모든 꼭지점에는 정확히 두 개의 모서리가 입사합니다.
용어.
"주기 그래프"에는 많은 동의어가 있습니다.여기에는 단순한 순환 그래프와 순환 그래프가 포함되지만, 후자의 용어는 단순히 비순환적인 그래프를 참조할 수도 있기 때문에 덜 자주 사용됩니다.그래프 이론가들 사이에서는 주기, 다각형 또는 n-곤도 자주 사용된다.n-cycle이라는 용어는 다른 [3]설정에서 사용되는 경우가 있습니다.
짝수의 정점이 있는 사이클을 짝수 사이클이라고 하며, 홀수의 정점이 있는 사이클을 홀수 사이클이라고 합니다.
특성.
주기 그래프는 다음과 같습니다.
- 짝수 정점이 있는 경우에만 색칠 가능한 2-엣지
- 2-정규
- 짝수의 정점이 있는 경우에만 2자리 색칠 가능.보다 일반적으로 그래프는 홀수 주기가 없는 경우에만 양분된다(Kőnig, 1936).
- 연결된
- 오일러의
- 해밀턴식
- 단위 거리 그래프
추가 정보:
- 주기 그래프는 정다각형으로 그릴 수 있으므로 n개의 변을 가진 정다각형과 차수 2n의 이면체군이다.특히, 어떤 정점이든 다른 정점으로, 어떤 가장자리가 다른 가장자리로 가는 대칭이 존재합니다. 따라서 n-cycle은 대칭 그래프입니다.
플라톤 그래프와 마찬가지로 사이클 그래프는 디헤드라 골격을 형성합니다.그들의 이중은 호소헤드라의 골격을 형성하는 쌍극자 그래프이다.
유향 주기 그래프
방향성 주기 그래프는 모든 가장자리가 동일한 방향을 향하는 방향 주기 그래프의 방향입니다.
유향 그래프에서 각 유향 사이클에서 적어도 1개의 에지(또는 호)를 포함하는 에지 세트를 피드백 아크 세트라고 합니다.마찬가지로 각 유도 사이클에서 적어도 하나의 정점을 포함하는 정점 집합을 피드백 정점 집합이라고 합니다.
유향 사이클 그래프는 균일한 인도 1과 균일한 아웃도 1을 가진다.
방향성 주기 그래프는 주기 그룹에 대한 Cayley 그래프입니다(예: 참조).트레비산)
「 」를 참조해 주세요.
레퍼런스
- ^ 몇 가지 간단한 그래프 스펙트럼.win.tue.nl
- ^ Diestel (2017) 페이지 8, 1 1.3
- ^ "Problem 11707". Amer. Math. Monthly. 120 (5): 469–476. May 2013. doi:10.4169/amer.math.monthly.120.05.469. JSTOR 10.4169/amer.math.monthly.120.05.469. S2CID 41161918.
원천
- Diestel, Reinhard (2017). Graph Theory (5 ed.). Springer. ISBN 978-3-662-53621-6.
외부 링크
- Weisstein, Eric W. "Cycle Graph". MathWorld. (2정규 사이클 그래프와 그룹 이론 개념의 사이클 다이어그램의 해석)
- Luca Trevisan, 캐릭터&
