📂그래프이론

그래프 이론에서의 워크, 트레일, 패스, 사이클

정의 ¹

그래프 $G$ 가 주어져 있다고 하자.

1. 에지의 유한 시퀀스를 워크라 하고 다음과 같이 나타낸다. $$v_{0} v_{1} , v_{1} v_{2} , \cdots , v_{m-1} v_{m} \\ v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{m-1} \rightarrow v_{m}$$ 이 때 $v_{0}$ 을 시점^{initial Vertex} , $v_{m}$ 을 종점^{final Vertex}이라 하고 $m$ 을 길이^length라 부른다.
2. 워크의 에지가 모두 다르면 트레일이라 한다.
3. 워크의 버텍스가 모두 다르면 패스라 한다.
4. 워크의 시점과 종점이 같으면 닫혀있다^closed고 한다.
5. 닫힌 패스를 사이클이라 한다.

이 개념들은 유향 그래프에 대해서도 비슷하게 정의할 수 있고, 다음과 같이 무한 그래프에 대해서도 정의할 수 있다.

$G$ 가 무한 그래프라고 하자. 아래의 정의에서 워크는 트레일, 패스, 사이클로 대체될 수 있다. 6. (유한) 워크는 일반적인 그래프의 워크와 정확하게 같다. 7. 원웨이 무한 워크^{one-way Infinte walk}는 다음과 같이 정의된다. $$v_{0} \to v_{1} \to v_{2} \to \cdots$$ 8. 투웨이 무한 워크^{two-way Infinte walk}는 다음과 같이 정의된다. $$\cdots \to v_{-2} \to v_{-1} \to v_{0} \to v_{1} \to v_{2} \to \cdots$$

설명

패스의 정의에서 시점과 종점은 예외다. 다시 말해 $v_{0} = v_{m}$ 인 경우엔 패스가 될 수 있고, 따라서 ‘닫힌 패스’가 존재할 수 있다. 한편 패스와 트레일의 정의에서, 버텍스가 모두 다르면 에지도 모두 다를 수밖에 없으므로 패스면 트레일이다.

사이클은 쉽게 말해 그래프에서 찾을 수 있는 ‘고리 모양’으로, 그래프 이론 전반에서 광범위하게 사용되는 개념이다. 예로써 다음 그림을 보면 그래프에서 총 세 개의 사이클을 찾을 수 있다:

한편 사이클에 대해 다음의 정리가 알려져있다.

정리

유한 그래프 $G$ 의 모든 버텍스의 차수가 $2$ 이상이면 $G$ 는 사이클을 가진다.

증명

$G$ 가 루프나 멀티플 에지를 가지면 당연히 사이클이 존재하는 것이므로 $G$ 는 심플 그래프로 가정한다.

임의의 버텍스 $v_{0} \in V(G)$ 하나를 픽스하고 다음과 같은 패스를 생각해보자. $$v_{0} \to v_{1} \to v_{2} \to \cdots$$ 가정에서 모든 버텍스의 차수는 $2$ 이상이므로 적어도 두 개의 버텍스와 인접해있다. 따라서 $v_{i+1}$ 는 그 전 버텍스 $v_{i}$ 에 인접한 버텍스 중 $v_{i-1}$ 를 제외한 임의의 버텍스로 계속해서 잡을 수 있음이 보장된다. 그런데 $G$ 는 유한 그래프이므로 언젠간 이미 패스에 속한 버텍스 $v_{k}$ 를 선택할 수밖에 없다. 그러면 시점과 종점이 $v_{k}$ 인 패스 $v_{k} \to \cdots \to v_{k}$ 는 사이클로써 $G$ 에 존재함을 알 수 있다.

■