그래프와 트리

개요 — 동기·문제의식

그래프이론의 거의 모든 정리는 몇 가지 기본 단어 위에 세워진다: 정점, 간선, 차수, 경로, 순환, 연결성분, 트리. 이 단어들이 흔들리면 Hall 정리, Menger 정리, Euler 공식, Turán 정리도 모두 헷갈린다.

특히 트리(tree) 는 그래프이론의 최소 골격이다. 트리는 연결되어 있지만 순환이 없고, 두 정점 사이의 길이 하나가 유일하며, 간선을 하나 빼면 끊어지고, 간선을 하나 더 넣으면 순환이 생긴다. 이런 동치 특성화 때문에 트리는 증명에서 귀납의 발판이 되고, 알고리즘에서 탐색의 골격이 되며, 큰 그래프의 분해 모델이 된다.¹

이 페이지는 이후 matching and halls theorem, connectivity and menger, planar graphs euler의 공통 기반이다.

직관

그래프를 도시와 도로의 추상화로 생각하자. 정점은 도시, 간선은 직접 도로다. 경로는 여러 도로를 따라 이동하는 방법이고, 순환은 출발점으로 되돌아오는 닫힌 이동이다.

연결 그래프는 모든 도시 사이에 이동 경로가 있는 도로망이다. 트리는 그중에서도 불필요한 도로가 전혀 없는 연결 도로망이다. 그래서 트리에서는 어느 도로 하나를 없애면 도시망이 끊어진다.

반대로 연결 그래프에 순환이 있으면, 순환 위의 간선 하나를 지워도 여전히 돌아가는 길이 남는다. 따라서 "연결을 유지하면서 간선을 최대한 줄인 것"이 스패닝 트리다.

정의

그래프: $G=(V,E)$, $E\subseteq [V]^2$. 이 페이지에서는 유한 단순 무향 그래프를 기본으로 한다.

차수: 정점 $v$ 에 닿는 간선의 수를 $d_G(v)$ 또는 $d(v)$ 라 쓴다.

길이: walk나 path의 길이는 지나간 간선의 수다.

부분그래프와 유도부분그래프: $H\subseteq G$ 는 $V(H)\subseteq V(G)$, $E(H)\subseteq E(G)$ 인 그래프다. $U\subseteq V(G)$ 에 대해 $G[U]$ 는 $U$ 안의 모든 기존 간선을 포함하는 유도부분그래프다.

거리: $d_G(x,y)$ 는 $x$에서 $y$로 가는 최단 path의 길이다. 연결되지 않았으면 보통 $\infty$ 로 둔다.

주요 정리

정리 1 (악수 보조정리). 유한 그래프 $G$ 에서 $\sum_v d(v)=2|E(G)|$.

따름정리. 홀수 차수 정점의 수는 짝수다.

정리 2 (연결성분 분해). 모든 그래프의 정점집합은 연결성분들의 정점집합으로 분할된다.²

정리 3 (트리의 동치 특성화). 유한 그래프 $T$ 에 대해 다음이 동치다.³

1. $T$ 는 트리다.
2. $T$ 는 연결이고 모든 두 정점 사이의 path가 유일하다.
3. $T$ 는 최소 연결 그래프다: 임의의 간선을 지우면 연결이 깨진다.
4. $T$ 는 최대 비순환 그래프다: 서로 인접하지 않은 두 정점 사이에 간선을 더하면 순환이 생긴다.
5. $T$ 가 $n$개 정점을 가지면 $|E(T)|=n-1$ 이다.

정리 4 (스패닝 트리 존재). 모든 유한 연결 그래프는 스패닝 트리를 가진다.

정리 5 (트리의 leaf). $|T|\ge2$ 인 유한 트리는 적어도 두 개의 leaf를 가진다.

예제

예제 1 ($K_n$). 모든 정점의 차수는 $n-1$ 이고 간선 수는 $\binom n2$ 이다. $n\ge3$이면 순환이 많으므로 트리가 아니다. $K_n$ 의 스패닝 트리는 $n-1$개의 간선을 갖는 임의의 연결 부분그래프다.

예제 2 ($P_n$). $P_n$ 은 그 자체가 트리다. 두 끝점은 leaf이고, 내부 정점은 차수 2다. 간선 수는 $n-1$.

예제 3 ($C_n$). $C_n$ 은 연결이지만 순환이 있으므로 트리가 아니다. 간선 하나를 지우면 $P_n$ 이 되어 스패닝 트리가 된다.

예제 4 ($K_{1,n}$). 별 그래프는 중심 하나와 leaf $n$개를 가진 트리다. 중심 차수는 $n$, leaf 차수는 1이다.

예제 5 ($K_{m,n}$). 완전이분그래프의 간선 수는 $mn$ 이다. $K_{1,n}$ 은 트리지만, $m,n\ge2$이면 $C_4$ 를 포함하므로 트리가 아니다.

예제 6 (Petersen 그래프). 모든 정점 차수가 3이므로 차수합은 30, 간선 수는 15다. 정점이 10개인 트리라면 간선 수가 9여야 하므로 Petersen 그래프는 트리가 아니다.

예제 7 (분리된 두 삼각형). $C_3\cup C_3$ 은 연결성분이 2개이고 각 성분은 순환을 가진다. forest가 아니다. 각 삼각형에서 간선 하나씩 지우면 두 개의 $P_3$ 로 이루어진 forest가 된다.

예제 8 (labeled tree 세기). 정점집합이 $[n]$ 으로 라벨된 트리는 Cayley 공식에 의해 $n^{n-2}$ 개다. 이 페이지의 구조론은 세기 문제로 가면 생성함수와 Stanley식 labeled tree 열거로 이어진다.⁴

흔한 오해와 함정

• walk와 path를 혼동하기 — walk는 정점을 반복할 수 있지만 path는 반복하지 않는다.
• 연결성과 완전성을 혼동하기 — 연결은 모든 두 정점 사이에 path가 있다는 뜻이고, 완전은 모든 두 정점 사이에 간선이 있다는 뜻이다.
• 트리는 "가지가 그려진 모양"이어야 한다고 생각하기 — 별 $K_{1,n}$ 도 트리이고, 긴 경로 $P_n$ 도 트리다.
• $|E|=|V|-1$ 만으로 트리라고 판단하기 — 유한 그래프에서 연결성 또는 무순환성 중 하나가 함께 필요하다. 예: 삼각형 $C_3$ 과 고립정점 하나는 $4$정점 $3$간선이지만 트리가 아니다.
• 스패닝 트리가 유일하다고 생각하기 — $C_n$ 에는 $n$개의 서로 다른 스패닝 트리가 있다.
• 무한 그래프에서 유한 트리 공식을 그대로 쓰기 — $|E|=|V|-1$ 같은 공식은 유한성에 의존한다.

큰 그림 / 연결

트리는 그래프이론의 "1차 근사"다. DFS/BFS 트리는 임의의 연결 그래프를 탐색 가능한 골격으로 바꾸고, 스패닝 트리는 연결성을 유지하는 최소 간선 집합을 제공한다.

connectivity and menger에서 트리는 낮은 연결성의 극단적 사례다. 트리는 모든 간선이 bridge이고, 내부 정점들은 cutvertex가 될 수 있다. 따라서 트리는 robust network라기보다 connectivity를 이해하기 위한 기준점이다.

planar graphs euler에서 트리는 Euler 공식의 첫 예다. 연결 plane tree는 face가 하나뿐이고 $V-E+F=n-(n-1)+1=2$ 를 만족한다.

spectral graph theory에서는 트리의 인접행렬·Laplacian 고유값이 구조 정보를 담는다. linear-algebra 위키 eigenvalues-and-characteristic-polynomial의 언어가 여기서 그래프 불변량으로 변한다.

연습문제

1. 악수 보조정리를 이용해 홀수 차수 정점 수가 짝수임을 증명하라.
2. $K_6$ 의 간선 수와 차수합을 구하라.
3. $C_7$ 에서 간선 하나를 지우면 트리가 됨을 확인하라.
4. 연결 그래프 $G$ 의 spanning subgraph 중 간선 수가 최소인 것은 트리임을 증명하라.
5. 유한 tree $T$ 에서 두 정점 사이 path가 유일함을 증명하라.
6. 정점 6개, 간선 5개인 그래프가 반드시 트리인지 판정하라.
7. $K_{2,3}$ 이 트리가 아님을 두 가지 방식으로 보여라.
8. leaf 제거 귀납으로 유한 tree의 간선 수가 $n-1$임을 증명하라.
9. 연결성분이 $c$개인 forest가 $n-c$개의 간선을 가짐을 증명하라.

관련 개념

• what is graph theory — 그래프이론의 큰 조감
• matching and halls theorem — 이분그래프와 매칭
• connectivity and menger — 연결성, cutvertex, bridge의 일반화
• planar graphs euler — tree를 출발점으로 보는 Euler 공식
• extremal and ramsey — 트리와 부분그래프 강제 문제
• 생성함수 — labeled tree와 연결성분 열거
• stanley ec2 — 열거조합론 보조 원천

각주