상위 질문
타임라인
채팅
관점

순환 그래프

위키백과, 무료 백과사전

순환 그래프
Remove ads

그래프 이론에서 순환 그래프(循環graph, 영어: cycle graph)는 정다각형그래프이다.

Thumb
순환 그래프

정의

크기가 순환 그래프 은 다음과 같은, 개의 꼭짓점

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

Remove ads

성질

요약
관점

순환 그래프 색칠수는 다음과 같다.

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

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

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

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

Remove ads

유향 순환 그래프

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

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

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

같이 보기

외부 링크

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads