PART II — 구조
단순 그래프 — 점 몇 개와 선 몇 개. 그러나 인터넷, 사회, 분자, 일정표가 다 이 안에 있습니다. 점은 객체, 선은 객체 사이의 어떤 관계를 뜻하죠. 이 단순한 추상 위에서 우리는 친구 관계의 평균, 비행기 노선의 색칠, 회로의 연결성, 그리고 해밀턴이 평생 풀고 싶었던 일주 문제까지 다룰 수 있습니다. 이 챕터에서는 단순 그래프의 정의부터 시작해 동형, 이분 그래프와 매칭, 채색, 워크와 연결성, 오일러·해밀턴 회로, 그리고 트리까지 — 그래프 이론의 가장 기본적이고 가장 자주 쓰이는 도구들을 손에 익혀 봅니다.
그래프 이론에서 가장 먼저 배우는 종류의 그래프는 단순 그래프입니다. "단순"이라는 말은 두 가지 제한을 뜻해요. 같은 두 정점을 잇는 변이 두 개 이상 존재하지 않고(다중변 금지), 자기 자신을 잇는 변(루프)도 없다는 것이죠. 단순 그래프는 사람·도시·웹페이지처럼 "쌍이 관계 있느냐 없느냐"만 묻는 이산 구조에 자연스럽게 들어맞습니다.
정의 12.1.1 (단순 그래프)
단순 그래프 \( G \)는 순서쌍 \( G = (V, E) \)로 쓰며, 여기서 \( V \)는 비어 있지 않은 유한 집합(정점 집합), \( E \)는 \( V \)의 서로 다른 두 원소로 이루어진 부분집합들의 집합(변 집합)입니다. 즉 \( E \subseteq \binom{V}{2} \). 변 \( \{u, v\} \)가 \( E \)에 있으면 \( u \)와 \( v \)는 서로 인접(adjacent)하다고 하며, \( u \sim v \)로 적습니다.
변이 정점에 닿아 있을 때 우리는 그 변이 그 정점에 접속(incident)한다고 말합니다. 정점 \( v \)에 접속하는 변의 개수를 \( v \)의 차수(degree)라 하고 \( \deg(v) \)로 씁니다. 단순 그래프에서는 자기 자신과 잇는 루프가 없으므로 \( \deg(v) \)는 그냥 \( v \)의 이웃의 개수와 같습니다.
예제 12.1.2
정점 4개 \( \{a, b, c, d\} \)에 변이 \( \{a,b\}, \{b,c\}, \{c,d\}, \{a,c\} \)인 그래프를 봅시다. 차수를 세어 보면 \( \deg(a) = 2, \deg(b) = 2, \deg(c) = 3, \deg(d) = 1 \). 이 차수의 합은 \( 2+2+3+1 = 8 \)이고 변의 개수는 4개. 합이 정확히 변 개수의 두 배입니다. 우연일까요?
우연이 아닙니다. 모든 변은 양 끝의 두 정점 차수에 각각 1씩 기여합니다. 그래서 모든 정점의 차수를 더하면, 모든 변이 두 번씩 세어지죠.
정리 12.1.3 (핸드셰이크 보조정리, Handshake Lemma)
임의의 단순 그래프 \( G = (V, E) \)에 대해 \[ \sum_{v \in V} \deg(v) = 2|E|. \]
따름정리 12.1.4
임의의 단순 그래프에서 차수가 홀수인 정점의 개수는 짝수다.
이름이 "악수 보조정리"인 까닭은 이래요. 파티에서 사람들이 악수를 했을 때, 모든 사람이 악수한 횟수의 합은 항상 짝수다 — 모든 악수는 두 사람의 카운트를 1씩 올리니까요. 컴퓨터과학에서는 그래프의 평균 차수 \( \bar d = 2|E|/|V| \)를 추정할 때 이 식이 그대로 들어갑니다.
핸드셰이크 보조정리는 작은 식 같지만, 통계 기사를 비판하는 무기로 쓰일 수 있습니다. 미국에서 흔히 인용되던 설문 결과 하나를 가져와 봅시다. "남성은 평생 평균 7명의 이성 파트너를 가지며, 여성은 4명을 가진다." 이런 식의 보고서, 어디서 본 적 있죠? 그래프 이론으로 5초만 생각해 보면 이 숫자는 동시에 옳을 수 없다는 것을 알 수 있습니다.
이성 관계라는 그래프 \( G \)를 그려 봅시다. 정점은 사람이고, 변은 "이 두 사람이 한 번이라도 이성 파트너 관계였다"는 사실. 그러면 한쪽 끝은 남자, 다른 쪽 끝은 여자인 변만 있는 셈이죠. 이런 그래프를 우리는 곧 이분 그래프(bipartite)라 부르게 됩니다.
남성 집합을 \( M \), 여성 집합을 \( W \)라 하고, 모든 변의 양 끝이 한쪽은 \( M \), 한쪽은 \( W \)라고 합시다. 핸드셰이크 보조정리에서 차수의 합은 변 개수의 2배지만, 이 합을 두 그룹으로 쪼개면 \[ \sum_{m \in M} \deg(m) \;+\; \sum_{w \in W} \deg(w) = 2|E|. \] 그런데 이분 그래프에서는 한 변마다 \( M \) 쪽 차수에 1, \( W \) 쪽 차수에 1을 더하므로 \[ \sum_{m \in M} \deg(m) = |E| = \sum_{w \in W} \deg(w). \] 즉 남자들의 파트너 수의 합과 여자들의 파트너 수의 합은 정확히 같아야 합니다.
노트 (그래서 평균은?)
남성 평균 차수는 \( \bar d_M = |E|/|M| \), 여성 평균 차수는 \( \bar d_W = |E|/|W| \). 두 평균의 비는 \[ \frac{\bar d_M}{\bar d_W} = \frac{|W|}{|M|}. \] 미국 성인 남녀 인구는 거의 1:1이므로 이 비도 거의 1이어야 합니다. 그런데 7/4 ≈ 1.75라고요? 그러려면 여성 인구가 남성 인구의 1.75배여야 하죠. 그럴 리 없습니다.
그래서 이 종류의 통계는 수학적으로 동시에 참일 수 없습니다. 누군가는 거짓말을 하거나, 기억을 잘못하거나, 표본이 편향되었거나 — 적어도 둘 중 하나는 사실과 거리가 멉니다. 사회학자들이 이미 알고 있는 현상이지만, 핵심을 한 줄로 잡아 주는 것은 결국 핸드셰이크 보조정리예요. 그래프적 사고는 가끔 신문 기사 한 면을 통째로 의심하게 만듭니다.
그래프 이론을 공부하다 보면 같은 모양의 그래프가 반복해서 등장합니다. 이름을 붙여 두면 편하니까, 자주 보는 다섯 종류만 정리해 둡시다.
정의 12.3.1 (이름 있는 그래프들)
아래에서 \( n, m \ge 1 \)은 자연수입니다.
예제 12.3.2
\( Q_3 \)을 손으로 그려 봅시다. 정점은 \( 000, 001, 010, 011, 100, 101, 110, 111 \) 8개. 변은 한 비트만 다른 쌍들 — 예를 들어 \( 010 \sim 011 \), \( 010 \sim 000 \), \( 010 \sim 110 \). 그림으로 그리면 정확히 정육면체 모양이 나옵니다. 그래서 이름이 "큐브"죠. \( Q_n \)은 병렬 컴퓨터의 통신 네트워크, 비트 오류 보정 부호의 코드워드 집합 등에서 자주 등장합니다.
노트
\( K_n \)은 모든 정점의 차수가 \( n-1 \)로 같고, \( C_n \)은 모두 차수 2, \( Q_n \)은 모두 차수 \( n \). 이렇게 모든 정점의 차수가 같은 그래프를 정칙 그래프(regular graph), 차수 \( k \)이면 \( k \)-정칙이라 부릅니다. 정칙성은 대칭성의 한 형태이고, 분석이 훨씬 쉬워지는 좋은 성질입니다.
두 그래프가 그림으로 보면 다르게 생겼는데, 정점 이름만 바꿔 주면 사실은 같은 그래프인 경우가 많습니다. 이 "이름 바꾸기로 같다"는 관계가 동형입니다.
정의 12.4.1 (그래프 동형)
두 단순 그래프 \( G_1 = (V_1, E_1) \)와 \( G_2 = (V_2, E_2) \)가 동형(isomorphic, \( G_1 \cong G_2 \))이라 함은, 일대일 대응 \( f: V_1 \to V_2 \)가 존재해서 모든 \( u, v \in V_1 \)에 대해 \[ \{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2 \] 가 성립하는 것이다.
쉽게 말해 정점에 이름표를 다시 붙여서 변의 모임이 정확히 일치하게 만들 수 있느냐는 것이죠. 동형은 동치 관계입니다(반사·대칭·추이). 그래서 그래프를 분류할 때 우리는 보통 동형류(isomorphism class) 단위로 셉니다.
두 그래프가 동형인지 보이려면 적절한 \( f \)를 구체적으로 제시하면 됩니다. 동형이 아님을 보이는 게 더 흥미로운데, 이때 쓰는 도구가 동형 invariant입니다. 동형이라면 보존되어야 하는 양 — 정점 수, 변의 수, 차수 수열, 사이클의 길이, 연결 성분의 개수, 보 그래프의 차수 수열 등 — 가운데 하나라도 다르면 두 그래프는 절대 동형일 수 없습니다.
예제 12.4.2
정점 5개의 두 그래프 \( G_1, G_2 \). \( G_1 \)의 차수 수열은 \( (3, 3, 2, 2, 2) \), \( G_2 \)의 차수 수열은 \( (3, 3, 3, 2, 1) \). 차수 수열이 다르므로 두 그래프는 동형이 아닙니다. 그림 그릴 필요도 없죠.
노트 (그래프 동형 문제)
일반적인 두 그래프가 동형인지 판정하는 알고리즘은 효율성 면에서 미묘합니다. P인지 NP-완전인지조차 오랫동안 미지였고, 2017년경 László Babai가 준다항식 시간 알고리즘을 제시한 이후로도 결정적인 다항 시간 알고리즘은 알려져 있지 않습니다. 즉 그래프 동형 문제는 아직 살아 있는 연구 주제입니다.
이분 그래프는 정점을 두 그룹 \( L, R \)로 쪼갤 수 있고, 모든 변의 두 끝이 한쪽씩에 들어가는 그래프입니다(같은 쪽 안에서는 변이 없음). 12.2의 이성 파트너 그래프, 학생-수업 그래프, 작업자-할 일 그래프, 이미지 픽셀-라벨 그래프 등 현실에서 정말 흔히 나옵니다.
정의 12.5.1 (매칭과 완전 매칭)
그래프 \( G \)의 매칭(matching)이란, 변들의 부분집합 \( M \subseteq E \)으로서 어느 두 변도 정점을 공유하지 않는 것이다. 이분 그래프 \( G = (L \cup R, E) \)에서 \( M \)이 \( L \)의 모든 정점을 덮으면(즉 모든 \( \ell \in L \)이 \( M \)의 어떤 변에 속하면) L-완전 매칭이라 한다.
완전 매칭이 존재하기 위한 깔끔한 조건이 있습니다. 부분집합 \( S \subseteq L \)에 대해 \( S \)의 이웃들의 집합 \( N(S) = \{ r \in R : \exists \ell \in S, \{\ell, r\} \in E \} \)를 봅시다. 만약 어떤 \( S \)에 대해 \( |N(S)| < |S| \)라면, \( S \) 안의 사람들이 \( N(S) \) 안의 자리 안에서 서로 다른 짝을 모두 찾을 수 없죠 — 비둘기집 원리. 놀라운 것은 이 비둘기집 조건의 역도 성립한다는 것입니다.
정리 12.5.2 (홀의 정리, Hall's Marriage Theorem)
이분 그래프 \( G = (L \cup R, E) \)에 \( L \)-완전 매칭이 존재할 필요충분조건은 \[ \forall S \subseteq L, \quad |N(S)| \ge |S|. \]
증명 (스케치)
(⇒) 완전 매칭 \( M \)이 있으면 임의의 \( S \subseteq L \)의 \( M \)-짝들이 \( N(S) \)에 \( |S| \)개 이상 들어가 있으므로 \( |N(S)| \ge |S| \).
(⇐) 귀납법. \( |L| = 1 \)이면 자명. 일반 단계에서 두 경우. (i) 모든 \( \emptyset \neq S \subsetneq L \)에서 \( |N(S)| > |S| \)이면, 임의의 \( \ell \in L \)과 그 이웃 \( r \in R \)을 짝지어 그래프에서 빼도 남은 그래프가 여전히 홀 조건을 만족한다. 귀납 가설로 끝. (ii) 어떤 \( \emptyset \neq S \subsetneq L \)에서 \( |N(S)| = |S| \)이면, 이 \( S \)와 \( N(S) \)로 만든 부분 그래프, 그리고 그 보충부에서 각각 홀 조건이 유지됨을 보이고 두 매칭을 합친다.
∎
홀의 정리는 결혼 정리(marriage theorem)라고도 불립니다. \( L \)을 신부, \( R \)을 신랑이라 두고 누가 누구와 결혼할 수 있는지를 변으로 표시했을 때, 모든 신부가 자기가 받아들일 수 있는 사람과 짝을 이룰 수 있는 조건이 위와 같다는 동화 같은 해석이 있죠. 컴퓨터과학에서는 작업 분배, 강좌 배정, 네트워크 흐름 등에 곧장 적용됩니다.
그래프의 정점을 색칠할 때, 변으로 이어진 두 정점은 서로 다른 색이어야 한다는 제한을 둬 봅시다. 이런 식의 제약 만족 문제가 의외로 많은 응용을 갖습니다. 시험 시간표 짜기(과목이 정점, 시간 충돌이 변), 무선 주파수 할당(기지국이 정점, 간섭이 변), 컴파일러 레지스터 할당(변수가 정점, 동시 활성이 변) 같은 문제 모두 결국 그래프 채색이죠.
정의 12.6.1 (k-채색과 채색수)
그래프 \( G \)의 k-채색은 함수 \( c: V \to \{1, 2, \dots, k\} \)로서 모든 변 \( \{u, v\} \in E \)에 대해 \( c(u) \neq c(v) \)인 것이다. \( G \)에 \( k \)-채색이 존재하면 \( G \)는 \( k \)-채색 가능하다(\( k \)-colorable)고 한다. 그러한 \( k \) 가운데 가장 작은 값을 채색수(chromatic number) \( \chi(G) \)라 한다.
예제 12.6.2
\( \chi(K_n) = n \). 모든 정점이 모든 정점과 인접하니 색이 \( n \)개는 필요해요. \( \chi(C_n) \)은 \( n \)이 짝수면 2, 홀수면 3. \( \chi(K_{m,n}) = 2 \) — 한쪽은 색 1, 한쪽은 색 2면 끝. 이분 그래프는 정확히 2-채색 가능한 그래프와 같다는 사실이 곧 따라 나옵니다.
정리 12.6.3 (이분성 ↔ 2-채색성)
그래프 \( G \)가 이분 그래프인 것은 \( \chi(G) \le 2 \)인 것과 동치이며, 또한 \( G \)에 길이가 홀수인 사이클이 없는 것과도 동치이다.
채색수의 일반적 결정은 어렵습니다 — 정확히는 NP-완전. 하지만 평면 위에 변의 교차 없이 그릴 수 있는 그래프(평면 그래프)에 대해서는 이 세상에서 가장 유명한 그래프 정리가 답을 줍니다.
정리 12.6.4 (4색 정리, Four Color Theorem)
모든 평면 그래프는 4-채색 가능하다. 즉 \( \chi(G) \le 4 \).
노트 (역사)
이 정리는 1852년에 추측으로 제기되어 100년 넘게 풀리지 않다가 1976년 Appel과 Haken이 컴퓨터로 1936개의 경우를 따로따로 검증해 증명했습니다. "이게 진짜 증명이냐"는 철학적 논쟁을 일으킨 첫 사례 중 하나죠. 지금은 더 정돈된 컴퓨터 보조 증명들이 있지만, 사람이 머릿속에서만 검증할 수 있는 짧은 증명은 여전히 알려져 있지 않습니다.
그래프 안에서 정점들 사이를 변을 타고 이동하는 길을 정확히 정의해 둡시다. 일상어 "경로"와 수학 용어가 미묘하게 다르므로 주의가 필요합니다.
정의 12.7.1 (워크, 패스, 사이클)
단순 그래프 \( G \)에서 워크(walk)는 정점과 변을 번갈아 적은 유한한 수열 \[ v_0, e_1, v_1, e_2, v_2, \dots, e_k, v_k \] 로서 각 \( e_i = \{v_{i-1}, v_i\} \in E \)인 것이다. 워크의 길이는 변의 개수 \( k \). 변이 모두 다르면 트레일(trail), 정점이 모두 다르면 패스(path)라 한다. \( k \ge 1 \)이고 \( v_0 = v_k \)이면 닫힌 워크(closed walk), 정점이 \( v_0 \)을 빼고 모두 다르고 \( k \ge 3 \)이면 사이클(cycle)이라 한다.
단순 그래프에서는 변이 한 쌍의 정점으로 결정되니, 변을 명시하지 않고 정점만 \( v_0, v_1, \dots, v_k \)로 적어도 워크가 잘 정의됩니다. 이 표기를 보통 더 자주 씁니다.
예제 12.7.2
\( C_5 \)에서 정점을 \( 1, 2, 3, 4, 5 \)라 두고 \( 1 \sim 2 \sim 3 \sim 4 \sim 5 \sim 1 \)이라 하자. \( 1, 2, 3, 2, 1 \)은 길이 4의 워크지만 트레일도 패스도 아니다(변 \( \{1,2\} \)가 두 번, 정점 1, 2도 반복). \( 1, 2, 3, 4 \)는 길이 3의 패스. \( 1, 2, 3, 4, 5, 1 \)은 길이 5의 사이클.
노트 (왜 이렇게 구분?)
증명에서 도구의 세기가 다르기 때문입니다. "두 정점 사이에 워크가 있다"보다 "패스가 있다"가 더 강한 결론이고, 보통은 워크에서 출발해 같은 정점을 두 번 방문하는 부분을 잘라내 패스로 줄이는 식으로 한 단계 강화합니다. 한국어 학생들이 처음에 가장 헷갈려하는 부분이니, 정의를 곁에 두고 예제로 손에 익히는 게 좋아요.
워크가 정의되면 자연스레 따라오는 개념이 연결성입니다. 두 정점이 같은 "덩어리"에 있는지 묻는 것이죠.
정의 12.8.1 (연결, 연결 성분)
단순 그래프 \( G \)에서 두 정점 \( u, v \)가 연결되어 있다(connected)는 것은 \( u \)에서 \( v \)로 가는 워크(동치적으로 패스)가 존재함을 뜻한다. 그래프 전체가 연결이라 함은 모든 정점 쌍이 연결되어 있다는 것이다. "연결되어 있다"는 동치 관계이며, 이 관계의 동치류 각각이 만들어내는 부분 그래프를 \( G \)의 연결 성분(connected component)이라 한다.
연결 성분은 그래프를 여러 덩어리로 깔끔하게 쪼개는 분할입니다. 그래프 알고리즘에서 가장 먼저 하는 전처리 중 하나가 BFS/DFS로 연결 성분을 모두 찾아 라벨링하는 일이죠. 시간 복잡도는 \( O(|V| + |E|) \).
예제 12.8.2
정점 6개 \( \{1,2,3,4,5,6\} \), 변이 \( \{1,2\}, \{2,3\}, \{4,5\} \)뿐인 그래프. 연결 성분은 \( \{1,2,3\} \), \( \{4,5\} \), \( \{6\} \) — 세 개. 정점 6은 변이 없는 고립점이지만 그 자체로 하나의 성분입니다.
노트 (변 개수의 하한)
연결 그래프는 변을 적어도 \( |V| - 1 \)개 가져야 합니다. 더 적으면 어떤 식으로 그어도 모든 정점을 한 덩어리로 묶을 수 없죠. 변이 정확히 \( |V| - 1 \)개인 연결 그래프 — 이게 곧 트리입니다(12.11에서 다시 만나요).
그래프 이론은 18세기 쾨니히스베르크라는 도시의 다리 일곱 개에서 시작되었습니다. 시민들의 일요일 산책 퀴즈: "일곱 다리를 모두 정확히 한 번씩 건너서 출발지로 돌아올 수 있을까?" 1736년 오일러가 답했죠 — "할 수 없습니다." 그리고 그 이유를 일반화해 그래프 이론의 첫 정리가 탄생합니다.
정의 12.9.1 (오일러 회로, 해밀턴 회로)
그래프 \( G \)의 오일러 트레일은 모든 변을 정확히 한 번씩 사용하는 트레일이다. 닫힌 오일러 트레일을 오일러 회로(Eulerian circuit)라 한다. 한편 모든 정점을 정확히 한 번씩 방문하는 사이클을 해밀턴 회로(Hamiltonian cycle)라 한다.
오일러 회로의 특징은 변을 빠짐없이 한 번씩, 해밀턴 회로의 특징은 정점을 빠짐없이 한 번씩 — 한 글자 차이지만 난이도가 천양지차입니다.
정리 12.9.2 (오일러 정리)
연결 그래프 \( G \)에 오일러 회로가 존재할 필요충분조건은 모든 정점의 차수가 짝수인 것이다. 오일러 트레일(닫혀 있지 않아도 됨)이 존재할 필요충분조건은 차수가 홀수인 정점이 0개이거나 정확히 2개인 것이다.
증명 (스케치)
(⇒) 회로를 따라가면, 정점에 들어올 때마다 1개의 새 변, 나갈 때마다 1개의 새 변을 쓰니까 각 정점의 차수는 짝수가 되어야 한다.
(⇐) 귀납법. 임의의 정점에서 출발해 갈 수 있는 한 변을 골라 따라간다(쓴 변은 그래프에서 제거). 차수가 짝수인 그래프에서는 출발점에 돌아올 때까지 막히지 않는다. 돌아왔는데 변이 남아 있으면, 회로 위 어떤 정점에서 남은 변이 출발하므로 그 정점에서 다시 보조 회로를 만들고 둘을 합친다. 변이 유한이므로 끝난다.
∎
쾨니히스베르크 다리는 네 정점(섬·강안)의 차수가 각각 5, 3, 3, 3으로 모두 홀수, 홀수 차수 정점이 4개이므로 오일러 회로도 트레일도 불가능. 오일러는 이 단순한 기준으로 산책 문제에 종지부를 찍었습니다.
노트 (해밀턴 회로의 비대칭성)
해밀턴 회로 존재 판정은 NP-완전. 깔끔한 필요충분조건은 알려져 있지 않고, 충분조건들(예: 디락의 정리 — 모든 정점 차수 \( \ge n/2 \))이 있을 뿐입니다. 변의 문제(오일러)와 정점의 문제(해밀턴)가 본질적으로 다른 복잡도 클래스에 속한다는 사실은 그래프 이론의 가장 흥미로운 비대칭 중 하나예요.
연결 그래프는 한 덩어리지만, 정점 하나만 빼면 두 덩어리로 쪼개질 수도 있죠. 이런 "약한 연결"과 "튼튼한 연결"을 구분하기 위한 개념이 \( k \)-연결성입니다.
정의 12.10.1 (k-연결)
정점 수가 \( k+1 \) 이상인 단순 그래프 \( G \)가 \( k \)-연결(\( k \)-connected)이라 함은, 어떤 \( k-1 \)개 이하의 정점을 제거해도 남은 그래프가 여전히 연결인 것이다. 동치적으로, 임의의 두 정점 \( u, v \) 사이에 정점이 서로 겹치지 않는 \( k \)개의 패스가 존재한다(멩거의 정리).
1-연결은 보통의 연결과 같습니다. 2-연결 이상은 흔히 "안전한 네트워크"와 관련됩니다. 라우터 한 대가 죽어도 인터넷이 죽지 않으려면 라우팅 그래프가 2-연결이어야 하죠. 데이터센터 토폴로지나 항공 노선망 설계에서 \( k \)-연결성은 핵심 지표입니다.
예제 12.10.2
\( C_n \) (\( n \ge 3 \))은 정확히 2-연결이다. 어떤 정점 하나만 빼도 \( P_{n-1} \)이 남아 연결이지만, 잘 고른 두 정점을 빼면 두 조각으로 쪼개진다. 한편 \( K_n \)은 \( (n-1) \)-연결이며, 그래프가 가질 수 있는 최대 연결도가 \( n-1 \)임을 보여 준다. 트리는 항상 잎 노드를 빼면 연결이지만 내부 노드를 빼면 쪼개지므로 1-연결이지만 2-연결은 아니다.
정리 12.10.3 (멩거, Menger)
그래프 \( G \)의 두 정점 \( u, v \) 사이에 정점이 서로 겹치지 않는 패스의 최대 개수는, \( u \)와 \( v \) 사이의 모든 패스를 끊기 위해 제거해야 하는 정점의 최소 개수와 같다.
멩거의 정리는 그래프 이론의 모든 "최소 컷 = 최대 흐름" 류 정리들의 원형이며, 알고리즘적으로는 네트워크 흐름으로 환원해 효율적으로 풀 수 있습니다.
마지막으로 그래프 이론에서 가장 깔끔한 가족, 트리를 만나봅시다. 컴퓨터과학 전체의 자료구조 절반을 떠받치고 있는 구조죠.
정의 12.11.1 (트리, 숲)
사이클이 없는 그래프를 숲(forest)이라 하고, 연결된 숲을 트리(tree)라 한다. 차수가 1인 정점은 트리의 잎(leaf)이다.
트리는 동치인 정의가 여러 개여서, 어떤 게 가장 자연스럽냐는 책마다 다릅니다. 다음 정리가 핵심입니다.
정리 12.11.2 (트리의 다섯 동치 정의)
정점 수 \( n \ge 1 \)의 그래프 \( G \)에 대해 다음 다섯 명제는 모두 동치이다:
증명 (스케치)
(1)⇒(2): 연결이고 사이클이 없으면 변 개수 = 정점 개수 − 1을 정점 수에 대한 귀납법으로 보임. 잎이 항상 존재함을 이용해 잎을 떼어내며 줄이면 됩니다.
(2)⇒(3): 연결이면 어쨌든 사이클이 있으면 변을 하나 빼도 연결이라 변 개수가 \( n-1 \)인 연결 그래프에 사이클이 있다면 모순.
(3)⇒(4): 사이클이 없다면 두 패스가 있을 때 그 둘을 합치면 사이클이 만들어져 모순. 변 개수 \( n-1 \) + 사이클 없음 ⇒ 연결도 함의.
(4)⇒(5): 패스가 유일하면 그 패스 위 어느 변을 빼도 두 정점이 끊어진다.
(5)⇒(1): 연결이고 변 하나만 빼도 끊긴다면 사이클이 있을 수 없다(사이클이 있으면 그 위 변 하나는 빼도 됨).
∎
예제 12.11.3
회사의 조직도, 파일 시스템, HTML DOM, 의사 결정 트리, 이진 검색 트리, 허프만 코딩 트리, 게임의 가능한 수의 펼침 — 모두 트리. 정점 \( n \)개짜리 트리의 변은 \( n - 1 \)개로 작지만, 표현하는 정보의 양은 어마어마하죠. 그래프 알고리즘의 많은 부분이 "그래프에서 트리를 찾기"(예: 최소 신장 트리, BFS/DFS 트리)로 환원됩니다.
노트 (왜 트리가 그렇게 자주 나오나)
트리는 "정점을 다 잇는 가장 적은 변"이라는 미니멀리즘의 끝입니다. 사이클이 없으니 분석이 단순하고, 패스가 유일하니 알고리즘이 결정적이며, 변이 \( n-1 \)개뿐이니 메모리도 작습니다. 컴퓨터과학 전체에서 가장 사랑받는 그래프인 데에는 다 이유가 있어요. 다음 챕터부터는 이 트리들을 무대 삼아 더 정교한 그래프 분석을 이어가게 됩니다.