트리

회로가 없는 연결 그래프를 트리라 한다. 가계도, 폴더 구조, 토너먼트 대진표가 트리이다. 트리는 ‘가장 적은 변으로 모든 점을 잇는’ 구조이며, 통신망과 도로망 설계(최소 생성트리)에 쓰인다.

핵심 개념

  • 트리: 연결되어 있고 회로가 없는 그래프
  • 잎: 차수가 $1$인 꼭짓점
  • 생성트리: 그래프의 모든 꼭짓점을 포함하는 트리인 부분그래프
  • 최소 생성트리: 변에 가중치가 있을 때 가중치의 합이 가장 작은 생성트리 (크루스칼 알고리즘: 가벼운 변부터 회로가 생기지 않게 추가)
그래프와 그 생성트리(초록 변)
꼭짓점 7개를 잇는 데 변 6개면 충분하다

핵심 정리

꼭짓점이 $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$개이다.

정리

  • 트리 = 연결 + 회로 없음, 변은 꼭짓점보다 하나 적다.
  • 두 꼭짓점 사이의 경로는 하나뿐이다.
알림: 보호된 콘텐츠입니다.