순환 (그래프 이론)

그래프 이론에서 순환(循環, 영어: cycle 사이클^[*])은 그래프 위의, 스스로와 겹치지 않는 폐곡선이다. 회로라고도 한다.

정의

(단순) 그래프 ${\displaystyle G}$에서, 길이가 ${\displaystyle n}$인 순환 ${\displaystyle C\subset \Gamma }$은 다음 성질을 만족시키는 꼭짓점들의 열 ${\displaystyle v_{1},\dots ,v_{n}\in V(G)}$이다.

• 모든 ${\displaystyle i=1,\dots ,n-1}$에 대하여, ${\displaystyle v_{i}v_{i+1}\in E(G)}$이며, 또한 ${\displaystyle v_{n}v_{0}\in E(G)}$이다.
• 임의의 ${\displaystyle i,j\in \{1,\dots ,n\}}$에 대하여, ${\displaystyle v_{i}=v_{j}}$라면 ${\displaystyle i=j}$이다.

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

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

예

다음과 같은 그래프를 살펴보자.

여기서 BDEFDCB는 닫힌 보행이지만, 꼭짓점 D가 반복되므로 순환이 아니다. HAB는 시작점과 끝점이 다르므로 순환이 아니다. HDGH는 순환을 이룬다.

알고리즘

무향 그래프의 순환은 이미 방문한 꼭짓점을 나타내는 변, 즉 역방향 변을 찾는 깊이 우선 탐색으로 찾아낸다.^[1] 또, 깊이 우선 탐색이 지나가지 않은 모든 역방향 변은 순환의 일부가 될 수 있다.^[2] 무향 그래프에서의 순환 탐색의 경우, 시간 복잡도는 n개의 꼭짓점을 가진 그래프에서 O(n)이다.

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

각주

1. Tucker, Alan (2006). 〈Chapter 2: Covering Circuits and Graph Colorings〉. 《Applied Combinatorics》 (영어) 5판. Hoboken: John Wiley & sons. 49쪽. ISBN 978-0-471-73507-6. CS1 관리 - 추가 문구 (링크)
2. Sedgewick, Robert (1983). 〈Graph algorithms〉. 《Algorithms》 (영어). Addison-Wesley. ISBN 0-201-06672-6.

• Balakrishnan, V.K. (2005). 《Schaum's outline of theory and problems of graph theory》 (영어). McGraw-Hill. ISBN 978-0070054899.

외부 링크

• Weisstein, Eric Wolfgang. “Graph cycle”. 《Wolfram MathWorld》 (영어). Wolfram Research.

같이 보기

• 순환 그래프
• 경로 (그래프 이론)