순환 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''순환'''(循環, {{llang|en|cycle|사이클}})은 그래프 위의, 스스로와 겹치지 않는 [[폐곡선]]이다. '''회로'''라고도 한다.

== 정의 ==
(단순) [[그래프]] <math>G</math>에서, 길이가 <math>n</math>인 '''순환''' <math>C\subset\Gamma</math>은 다음 성질을 만족시키는 꼭짓점들의 열 <math>v_1,\dots,v_n\in V(G)</math>이다.
* 모든 <math>i=1,\dots,n-1</math>에 대하여, <math>v_iv_{i+1}\in E(G)</math>이며, 또한 <math>v_nv_0\in E(G)</math>이다.
* 임의의 <math>i,j\in\{1,\dots,n\}</math>에 대하여, <math>v_i=v_j</math>라면 <math>i=j</math>이다.

일부 문헌(특히, 오래된 문헌)에서는 "{{llang|en|cycle|사이클}}"이 [[그래프 이론 용어|닫힌 보행]]을 일컫는 경우가 있으므로 주의하여야 한다. 만약 혼동의 여지가 있으면, 순환을 "단순 순환"({{llang|en|simple cycle}})이라고 일컫는 경우도 있다.

마찬가지로, [[유향 그래프]]에서도 순환을 정의할 수 있다.

== 예 ==
다음과 같은 그래프를 살펴보자.
:[[파일:Graph cycle.svg|200px]]
여기서 BDEFDCB는 [[그래프 이론 용어|닫힌 보행]]이지만, 꼭짓점 D가 반복되므로 순환이 아니다. HAB는 시작점과 끝점이 다르므로 순환이 아니다. HDGH는 순환을 이룬다.

== 알고리즘 ==
무향 그래프의 순환은 이미 방문한 꼭짓점을 나타내는 변, 즉 역방향 변을 찾는 [[깊이 우선 탐색]]으로 찾아낸다.<ref>{{서적 인용|last=Tucker|first=Alan|title=Applied Combinatorics | 날짜=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5판|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings | 언어=en}}</ref>
또, 깊이 우선 탐색이 지나가지 않은 모든 역방향 변은 순환의 일부가 될 수 있다.<ref name="sedgewick">{{서적 인용
| first=Robert | last=Sedgewick | title=Algorithms | url=https://archive.org/details/algorithms00sedg | chapter=Graph algorithms
| 날짜=1983
| publisher=Addison-Wesley | isbn=0-201-06672-6 | 언어=en
}}</ref> 무향 그래프에서의 순환 탐색의 경우, 시간 복잡도는 n개의 꼭짓점을 가진 그래프에서 O(n)이다.

[[유향 그래프]]에서의 순환 역시 깊이 우선 탐색으로 역방향 변을 찾아내는 방식으로 찾아내며, 순방향 변(forward edge)이나 교차 변(cross edge)은 순환을 나타내는데 중요하지 않다. 많은 [[위상정렬]] 알고리즘을 통해서도 순환을 찾아낼 수도 있다. 또한, 유향 그래프가 강연결 성분({{llang|en|strongly connected component}})로 나누어 질 수 있을 때, 순환은 강연결 성분 속에서만 존재하므로, 강연결 성분 알고리즘으로도 찾아낼 수 있다.<ref name="sedgewick" />

== 각주 ==
{{각주}}
* {{서적 인용|last=Balakrishnan|first=V.K.|title=Schaum's outline of theory and problems of graph theory|year=2005|publisher=McGraw-Hill|isbn=978-0070054899| 언어=en}}

== 외부 링크 ==
* {{매스월드|id=GraphCycle|title=Graph cycle}}

== 같이 보기 ==
* [[순환 그래프]]
* [[경로 (그래프 이론)]]

[[분류:그래프 이론]]