회로가 없는 연결 그래프를 트리라 한다. 가계도, 폴더 구조, 토너먼트 대진표가 트리이다. 트리는 ‘가장 적은 변으로 모든 점을 잇는’ 구조이며, 통신망과 도로망 설계(최소 생성트리)에 쓰인다.
핵심 개념
- 트리: 연결되어 있고 회로가 없는 그래프
- 잎: 차수가 $1$인 꼭짓점
- 생성트리: 그래프의 모든 꼭짓점을 포함하는 트리인 부분그래프
- 최소 생성트리: 변에 가중치가 있을 때 가중치의 합이 가장 작은 생성트리 (크루스칼 알고리즘: 가벼운 변부터 회로가 생기지 않게 추가)
핵심 정리
꼭짓점이 $n$개인 트리의 변은 정확히 $n-1$개이다. 또 트리의 두 꼭짓점 사이의 경로는 하나뿐이다.
증명 보기
1단계: 잎이 있다. 꼭짓점이 $2$개 이상인 트리에는 잎이 적어도 두 개 있다. 가장 긴 경로를 하나 잡으면 그 끝점은 잎이다. 끝점에 경로 밖의 다른 이웃이 있으면 경로를 더 늘릴 수 있고, 경로 안의 이웃이 있으면 회로가 생기기 때문이다.
2단계: 귀납법. $n=1$이면 변이 $0$개이다. $n$개인 트리에서 잎 하나와 그 변을 지우면 여전히 연결되어 있고 회로가 없으므로 $n-1$개의 꼭짓점을 가진 트리이다. 귀납 가정에 의해 변이 $n-2$개이므로 원래 트리는 $n-1$개이다.
경로의 유일성. 두 꼭짓점 사이에 서로 다른 경로가 두 개 있으면, 두 경로가 갈라졌다 다시 만나는 부분에서 회로가 생긴다. 트리에는 회로가 없으므로 모순이다. $\blacksquare$
예제
- 탁구 대회에 $64$팀이 단판 토너먼트로 참가하면 경기 수는 $63$이다. (경기마다 한 팀이 탈락하므로, 혹은 대진표가 잎 $64$개인 트리)
- 케일리 공식: 꼭짓점 $n$개에 이름을 붙인 트리의 개수는 $n^{n-2}$이다. $n=3$이면 $3$개, $n=4$이면 $16$개
확인 문제
변이 $20$개이고 회로가 없는 그래프가 연결 성분 $4$개로 이루어져 있다. 꼭짓점은 몇 개인가?
풀이 보기
각 연결 성분은 트리이다. 꼭짓점이 $n_i$개인 트리의 변은 $n_i-1$개이므로 전체 변은 $\sum(n_i-1)=n-4=20$, 꼭짓점은 $24$개이다.
정리
- 트리 = 연결 + 회로 없음, 변은 꼭짓점보다 하나 적다.
- 두 꼭짓점 사이의 경로는 하나뿐이다.
