트리 그래프
정의 1
설명
트리는 컴퓨터 공학의 자료 구조 등에서 흔히 볼 수 있는 개념으로써, 컴퓨터를 조금이라도 다루는 이공계 전공이라면 아마 힙 소팅이라는 말을 들어봤을 것이다. 여기서 말하는 그 힙이 바로 트리의 일종이다.트리의 유니언은 직관적이게도 포레스트forest라 부른다. 유향 그래프일 경우 입력 차수가 $0$ 인 노드를 루트root , 출력 차수가 $0$ 인 노드를 리프reaf라 부르기도 한다. 이렇듯 트리는 비교적 응용되는 분야를 찾기도 쉽고 단어도 친숙해보이지만, 안타깝게도 순수 수학에서는 그 복잡한 민낯을 그대로 드러낸다.
정리
다음은 트리 그래프가 되는 동치조건들이다.
$T$ 가 $n$ 개의 버텍스를 가진 그래프라고 하자. 다음은 서로 동치다.
- (i): $T$ 는 트리다.
- (ii): $T$ 는 사이클을 가지지 않으며 $n-1$ 개의 에지를 가진다.
- (iii): $T$ 는 연결그래프고 $n-1$ 개의 에지를 가진다.
- (iv): $T$ 의 모든 에지는 브릿지다.
- (v): $T$ 의 임의의 두 버텍스를 잇는 패스는 하나 뿐이다.
- (vi): $T$ 는 사이클을 가지지 않으나 에지를 추가하면 정확히 하나의 사이클이 생긴다.
- 에지 $b \in G$ 가 지워짐으로써 그래프가 단절되면 $b$ 를 브릿지라고 부른다.
증명
$(i) \implies (ii)$
$T$ 는 사이클이 존재하지 않으므로 아무 에지나 지우면 두 개의 트리로 분리된다. 귀납적으로 이를 반복해보면 각각의 트리에서 에지의 수는 버텍스의 수보다 정확히 하나 적다. 거꾸로 생각해보면 트리 $T$ 는 $n-1$ 개의 에지를 가져야한다.
$(ii) \implies (iii)$
$T$ 가 연결 그래프가 아니라고 하자. $T$ 의 각 컴포넌트는 사이클을 가지지 않고 각자 버텍스보다 $1$ 씩 적은 수의 에지를 가진다. 그러나 이는 에지가 $n-1$ 개라는 전제에 위배되므로, $T$ 는 연결 그래프여야한다.
$(iii) \implies (iv)$
단절 그래프의 에지: 심플 그래프 $G$ 가 $n$ 개의 버텍스를 갖고 있다고 하자. $G$ 가 $k$ 개의 버텍스를 가지면 $G$ 의 에지의 갯수 $m$ 은 다음을 만족한다. $$ n-k \le m \le (n-k)(n-k+1)/2 $$
$T$ 의 어떤 에지든 제거하고 나면 버텍스의 수는 $n$, 에지의 수는 $n-2$ 이므로 $n-k \le n-2$ 이고, $2 \le k$ 이라는 것은 어떤 에지를 제거하든 컴포넌트의 수가 늘어난다는 뜻이므로 $T$ 의 모든 에지는 브릿지다.
$(iv) \implies (v)$
$T$ 는 연결 그래프이므로 모든 버텍스의 쌍은 적어도 하나의 패스에 속한다. 만약 어떤 버텍스의 쌍이 두 패스에 속한다면 이는 사이클을 이루고, 모든 에지가 브릿지라는 전제에 모순이다.
$(v) \implies (vi)$
$T$ 가 이미 사이클을 포함한다면, 그 사이클에 속한 임의의 두 버텍스는 적어도 두 개의 패스에 속하게 되어 전제에 모순이다. 만약 에지 $e$ 가 $T$ 에 추가된다면, $e$ 에 딸린 버텍스들은 이미 $T$ 와 연결 되어 있으므로 사이클이 만들어지게 된다. 따라서 $T$ 에 에지를 추가하면 정확히 하나의 사이클이 생긴다.
$(vi) \implies (i)$
$T$ 가 연결 그래프가 아니라면 각각의 컴포넌트가 이어지도록 에지를 추가해도 사이클이 생기지 않는다. 그러나 이는 전제에 모순이므로 $T$ 는 연결 그래프여야하고, 전제에서 사이클을 가지지 않는다고 했으므로 $T$ 는 트리다.
■
Wilson. (1970). Introduction to Graph Theory: p43. ↩︎