📂그래프이론

그래프의 오리엔테이션

빌드업

유향 그래프 $D$ 가 주어져 있다고 하자.

1. 아크의 유한 시퀀스를 유향 워크^{directed walk}라 하고 다음과 같이 나타낸다. $$ 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. 유향 워크의 아크가 모두 다르면 유향 트레일^{directed Trail}이라 한다.
3. 유향 워크의 버텍스가 모두 다르면 유향 패스^{directed Path}라 한다.
4. 유향 워크의 시점과 종점이 같으면 닫혀있다^closed고 한다.
5. 닫힌 패스를 사이클^{directed cycle}이라 한다.

아크^arc란 유향 그래프에서 방향을 가진 에지를 말한다. 위의 정의는 본질적으로 워크와 트레일, 패스, 사이클에 대한 정의를 유향 그래프에 대해 다시 정의했을 뿐이다.

오리엔테이션의 정의를 소개하기 이전에 일반적인 그래프의 연결성에 대해 리뷰해보자.

그래프의 집합 표현: 두 그래프 $G_{1}$ 과 $G_{2}$ 에 대해 $V(G_{1}) \cap V(G_{2}) = \emptyset$ 이라고 하자. 그러면 두 그래프의 유니언^union $G = G_{1} \cup G_{2}$ 은 버텍스 셋 $V(G_{1}) \cup V(G_{2})$ 과 에지 셋 $E (G_{1}) \cup E ( G_{2} )$ 을 가지는 그래프다. 그래프 $H$ 가 그래프들의 유니언으로 표현될 수 없으면 $H$ 를 연결되었다^connected고 한다.

이제 그래프의 오리엔테이션을 정의해보자.

정의

6. 유향 그래프 $D$ 에서 임의의 두 버텍스 $v,w \in V(D)$ 에 대해 시점이 $v$ 고 종점이 $w$ 인 유향 패스가 존재하면 $D$ 가 강하게 연결되었다^{strongly Connected}고 한다.
7. 그래프 $G$ 의 에지에 방향을 줘서 강하게 연결된 유향 그래프를 만들 수 있으면 $G$ 가 오리엔터블^orientable하다고 하고, 그 강하게 연결된 유향 그래프를 $G$ 의 오리엔테이션이라 한다.

설명 ¹

그래프의 집합 표현을 통해 깔끔하게 정의된 연결성과 달리 강한 연결성은 패스의 존재성을 통해 정의한다. 수학적으로 우아하지는 않지만 오히려 더 직관적으로 이해할 수 있을 것이다. 이제와서 생각해보면 사실 일반적인 그래프의 연결성도 패스의 존재성으로 정의해도 상관 없는데, 집합으로 정의하는 편이 위상수학에서의 연결성을 정의하는 방식과 비슷하기 때문에 굳이 집합 표현을 쓰는 것이다.

쉽게 말해 오리엔터블 그래프란 일반적인 그래프 $G$ 를 유향 그래프로 바꿨을 때도 연결성이 유지될 수 있는 그래프다. 애초에 연결성이 없다면 당연히 강한 연결성도 가질 수 없다. 예로써 다음의 그래프를 보면 방향을 주었을 때 강한 연결성을 가짐으로써 오리엔터블 그래프가 됨을 확인할 수 있다.

한편 오리엔터블 그래프에 대해 사이클과 관련된 다음의 정리가 알려져 있다.

정리

$G$ 는 연결 그래프라고 하자. $G$ 가 오리엔터블인 것과 $G$ 의 모든 에지가 적어도 하나의 사이클에 포함되는 것은 동치다.

증명

전략: 그래프에 사이클에 속하지 않는 버텍스인 엔드 버텍스 $v_{0}$가 존재한다면 방향을 어떻게 주든 $v_{0}$ 로는 들어가거나 나갈수밖에 없으므로 오리엔터블 그래프가 될 수 없다. 이러한 사실에서 오리엔터블 그래프의 모든 버텍스와 에지는 반드시 사이클에 속해있어야 한다.

---

$(\Rightarrow)$

$G$ 사이클 $C$ 를 픽스하자. 만약 모든 에지가 $C$ 에 속하면 증명할 것이 없으므로, $C$ 에 인접하면서 $C$ 에 속하지는 않는 에지 $e \in E(G)$ 가 있다고 해보자. 그런데 $G$ 가 오리엔터블하므로 다른 사이클 $c '$ 에는 속해있어야한다. $c '$ 는 $C$ 에서 이미 주어진 방향을 포함해서 새로이 만들어진 사이클로 볼 수 있다. $G$ 는 연결 그래프이므로, 같은 방법으로 $C$ 혹은 $c '$ 에 속하지 않은 각각의 에지에 대해 새로운 사이클을 할당해줄 수 있다. 따라서 $G$ 의 모든 에지는 적어도 하나의 사이클에는 속하게 된다.

---

$(\Leftarrow)$

자명하다. 모든 에지가 적어도 하나의 사이클에 속해 있으므로 어떤 시점 $v \in V(G)$ 에서 출발하든 여러 사이클을 경유하며 임의의 종점 $w$ 에 도달할 수 있다.

■