그래프 이론 (Graph Theory)

그래프 이론은 꼭짓점(Vertex)과 변(Edge)으로 이루어진 그래프를 연구하는 수학 분야입니다. 네트워크, 경로 탐색, 최적화 등 다양한 응용이 있으며, 컴퓨터 과학, 통신, 생물학, 사회학 등 폭넓은 분야에서 활용됩니다.

이런 곳에 쓰여요

선수 지식: 이산수학

난이도: ★★★☆☆ (고등학교 심화)

그래프의 정의와 종류

그래프(Graph) $G = (V, E)$는 꼭짓점의 집합 $V$와 변의 집합 $E$로 구성됩니다. 변은 두 꼭짓점을 연결합니다.

그래프의 종류

부분그래프 (Subgraph)

그래프 $G = (V, E)$의 부분그래프(Subgraph) $H = (V', E')$는 $V' \subseteq V$이고 $E' \subseteq E$인 그래프입니다. 특히:

• 유도 부분그래프(Induced Subgraph): $V' \subseteq V$에 대해 $E' = \{\{u,v\} \in E \mid u, v \in V'\}$, 즉 $V'$에 속하는 꼭짓점들 사이의 모든 변을 포함합니다.
• 신장 부분그래프(Spanning Subgraph): $V' = V$이고 $E' \subseteq E$인 부분그래프입니다.

차수와 그래프 표현

차수 (Degree)

꼭짓점 $v$의 차수(Degree) $\deg(v)$는 $v$에 연결된 변의 수입니다.

악수 정리(Handshaking Lemma): 모든 그래프에서 차수의 합은 변의 수의 2배입니다.

방향 그래프의 경우:

인접 행렬 (Adjacency Matrix)

$n$개의 꼭짓점을 가진 그래프 $G$의 인접 행렬 $A$는 $n \times n$ 행렬로, $A_{ij} = 1$이면 꼭짓점 $i$와 $j$ 사이에 변이 존재합니다.

예시: 꼭짓점 $\{1, 2, 3, 4\}$, 변 $\{1{-}2, 2{-}3, 3{-}4, 1{-}4\}$인 순환 그래프 $C_4$의 인접 행렬:

인접 리스트 (Adjacency List)

각 꼭짓점에 대해 인접한 꼭짓점의 목록을 저장합니다. 위 예시의 인접 리스트:

이분 그래프 (Bipartite Graph)

이분 그래프는 꼭짓점 집합을 두 부분 $V = X \cup Y$ ($X \cap Y = \emptyset$)로 나누어 모든 변이 $X$와 $Y$ 사이를 연결하는 그래프입니다.

완전 이분 그래프 $K_{m,n}$: $|X| = m$, $|Y| = n$이고 $X$와 $Y$의 모든 꼭짓점 쌍이 연결된 그래프. 변의 수는 $m \cdot n$입니다.

경로와 순환

기본 개념

• 연결(Connected): 무방향 그래프에서 모든 꼭짓점 쌍 사이에 경로가 존재
• 강연결(Strongly Connected): 방향 그래프에서 모든 꼭짓점 쌍 $(u, v)$에 대해 $u \to v$와 $v \to u$ 경로 모두 존재
• 연결 성분(Connected Component): 극대 연결 부분그래프

오일러 경로와 회로

정의

• 오일러 트레일(Euler Trail): 그래프의 모든 변을 정확히 한 번씩 지나는 트레일
• 오일러 회로(Euler Circuit): 시작점으로 돌아오는 오일러 트레일

오일러 정리

증명 스케치 (오일러 회로)

($\Rightarrow$) 오일러 회로가 존재하면, 회로가 각 꼭짓점을 지날 때마다 들어오는 변과 나가는 변이 쌍을 이루므로 모든 차수는 짝수입니다.

($\Leftarrow$) 모든 차수가 짝수인 연결 그래프에서, 임의의 꼭짓점 $v$에서 출발하여 더 이상 진행할 수 없을 때까지 변을 따라갑니다. 차수가 짝수이므로 반드시 $v$로 돌아옵니다. 아직 사용하지 않은 변이 남아 있다면, 이미 방문한 꼭짓점 중 미사용 변이 있는 곳에서 새 회로를 만들어 합칩니다. 그래프가 연결이므로 이 과정을 반복하면 모든 변을 커버합니다.

쾨니히스베르크 다리 문제 — 그래프 이론의 탄생

1736년 오일러(Euler)는 프로이센의 쾨니히스베르크에 있는 7개의 다리를 모두 정확히 한 번씩 건너서 출발점으로 돌아올 수 있는지 연구했습니다.

이 그래프에서 모든 꼭짓점의 차수가 3(홀수)이므로, 오일러 회로도 오일러 트레일도 존재하지 않습니다. 이것이 그래프 이론의 탄생으로 여겨집니다.

해밀턴 경로

정의

• 해밀턴 경로(Hamiltonian Path): 모든 꼭짓점을 정확히 한 번씩 방문하는 경로
• 해밀턴 순환(Hamiltonian Cycle): 시작점으로 돌아오는 해밀턴 경로

오일러 경로(변 기반)와 달리 해밀턴 경로(꼭짓점 기반)의 존재를 판정하는 효율적인 알고리즘은 알려져 있지 않습니다 (NP-완전 문제).

오일러 vs 해밀턴 비교

디랙 정리 (Dirac's Theorem, 1952)

예시: $K_5$에서 $n = 5$, 모든 차수가 $4 \geq 5/2 = 2.5$이므로 해밀턴 순환이 존재합니다.

오레 정리 (Ore's Theorem, 1960)

오레 정리는 디랙 정리의 일반화입니다. 디랙 조건 $\deg(v) \geq n/2$를 만족하면 자동으로 오레 조건도 만족합니다.

트리

트리(Tree)는 순환이 없는 연결 그래프입니다.

트리의 동치 조건

$n$개의 꼭짓점을 가진 그래프 $G$에 대하여 다음은 모두 동치입니다:

1. $G$는 트리입니다 (연결 + 순환 없음).
2. $G$는 연결이고 $|E| = n - 1$입니다.
3. $G$는 순환이 없고 $|E| = n - 1$입니다.
4. 임의의 두 꼭짓점 사이에 유일한 경로가 존재합니다.
5. $G$는 연결이고, 어떤 변이든 하나를 제거하면 비연결이 됩니다.
6. $G$는 순환이 없고, 어떤 변이든 하나를 추가하면 정확히 하나의 순환이 생깁니다.

트리의 성질

• $n$개의 꼭짓점을 가진 트리는 정확히 $n - 1$개의 변을 가집니다.
• 2개 이상의 꼭짓점을 가진 트리에는 반드시 차수가 1인 꼭짓점(잎, leaf)이 2개 이상 존재합니다.
• 케일리 공식(Cayley's Formula): $n$개의 레이블된 꼭짓점으로 만들 수 있는 트리의 수는 $n^{n-2}$개입니다.

프뤼퍼 수열 (Prufer Sequence)

$n$개의 레이블된 꼭짓점으로 이루어진 트리와 길이 $n-2$인 수열 $\{1, 2, \ldots, n\}^{n-2}$ 사이에 전단사 함수가 존재합니다. 이것이 케일리 공식의 한 증명입니다.

트리 $\to$ 프뤼퍼 수열 알고리즘:

1. 트리에서 레이블이 가장 작은 잎(leaf)을 찾습니다.
2. 그 잎에 연결된 꼭짓점의 레이블을 수열에 추가합니다.
3. 잎을 제거합니다.
4. 꼭짓점이 2개 남을 때까지 반복합니다.

예시: 꼭짓점 $\{1,2,3,4,5,6\}$, 변 $\{1{-}4, 2{-}4, 3{-}5, 4{-}5, 5{-}6\}$인 트리:

프뤼퍼 수열: $(4, 4, 5, 5)$. 수열에서 트리를 복원하는 것도 가능합니다.

신장 트리 (Spanning Tree)

그래프 $G$의 모든 꼭짓점을 포함하면서 트리인 부분그래프를 신장 트리라 합니다.

• 연결 그래프는 반드시 신장 트리를 가집니다.
• 신장 트리의 변의 수는 항상 $|V| - 1$입니다.
• 키르히호프 정리(Kirchhoff's Theorem): 그래프의 신장 트리의 수는 라플라시안 행렬의 여인수(cofactor)로 계산할 수 있습니다.

최단 경로 알고리즘

알고리즘 비교

다익스트라 알고리즘 (Dijkstra's Algorithm)

음이 아닌 가중치를 가진 그래프에서 한 출발점으로부터 모든 꼭짓점까지의 최단 거리를 구합니다.

알고리즘:

1. 출발점의 거리를 0, 나머지를 $\infty$로 초기화합니다.
2. 방문하지 않은 꼭짓점 중 거리가 가장 작은 꼭짓점 $u$를 선택합니다.
3. $u$의 각 이웃 $v$에 대해, $\text{dist}[u] + w(u,v) < \text{dist}[v]$이면 갱신합니다.
4. 모든 꼭짓점을 방문할 때까지 반복합니다.

단계별 예시: 다음 그래프에서 꼭짓점 $A$로부터의 최단 거리를 구해 봅시다.

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

음의 가중치를 허용하며, 음의 순환도 감지할 수 있습니다.

1. 출발점의 거리를 0, 나머지를 $\infty$로 초기화합니다.
2. 모든 변 $(u, v)$에 대해 완화(relaxation)를 수행합니다: $\text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + w(u,v))$
3. 위 과정을 $|V| - 1$번 반복합니다.
4. 한 번 더 반복했을 때 갱신이 일어나면 음의 순환이 존재합니다.

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

모든 꼭짓점 쌍 사이의 최단 거리를 구합니다. 동적 프로그래밍 기반입니다.

$d_{ij}^{(k)}$: 중간 꼭짓점으로 $\{1, 2, \ldots, k\}$만 사용할 때 $i$에서 $j$까지의 최단 거리

핵심 코드 (의사 코드):

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

최소 신장 트리 (MST)

가중 연결 그래프에서 모든 꼭짓점을 연결하면서 변의 가중치 합이 최소인 신장 트리를 최소 신장 트리(Minimum Spanning Tree)라 합니다.

절단 성질 (Cut Property)

그래프의 꼭짓점을 두 집합 $S$와 $V \setminus S$로 나눈 절단(Cut)에서, 절단을 지나는 변 중 가중치가 최소인 변은 반드시 어떤 MST에 포함됩니다.

크루스칼 알고리즘 (Kruskal's Algorithm)

1. 모든 변을 가중치 오름차순으로 정렬합니다.
2. 가중치가 작은 변부터 선택하되, 순환이 생기지 않으면 추가합니다.
3. $|V| - 1$개의 변이 선택될 때까지 반복합니다.

시간 복잡도: $O(E \log E)$ (정렬이 지배). 순환 판정에는 분리 집합(Union-Find) 자료구조를 사용합니다.

프림 알고리즘 (Prim's Algorithm)

1. 임의의 꼭짓점에서 시작합니다.
2. 이미 선택된 꼭짓점 집합과 나머지를 연결하는 변 중 가중치가 최소인 변을 선택합니다.
3. $|V| - 1$개의 변이 선택될 때까지 반복합니다.

시간 복잡도: $O((V + E) \log V)$ (우선순위 큐 사용 시)

크루스칼 vs 프림

크루스칼 단계별 예시:

변 목록: $(A,B,1)$, $(B,C,4)$, $(A,C,3)$, $(C,D,2)$, $(B,D,5)$

MST 가중치 합: $1 + 2 + 3 = 6$

네트워크 흐름

흐름 네트워크의 정의

흐름 네트워크(Flow Network)는 방향 그래프 $G = (V, E)$에 다음이 주어진 것입니다:

• 용량 함수(Capacity) $c: E \to \mathbb{R}_{\geq 0}$: 각 변의 최대 흐름량
• 소스(Source) $s$: 흐름이 시작되는 꼭짓점
• 싱크(Sink) $t$: 흐름이 도착하는 꼭짓점

유효한 흐름 $f: E \to \mathbb{R}_{\geq 0}$은 다음을 만족합니다:

• 용량 제약: $0 \leq f(u,v) \leq c(u,v)$ (모든 변에 대해)
• 흐름 보존: $s, t$를 제외한 모든 꼭짓점 $v$에 대해 $\sum_{u} f(u,v) = \sum_{w} f(v,w)$

최대 흐름-최소 절단 정리 (Max-Flow Min-Cut Theorem)

여기서 $s$-$t$ 절단은 $V$를 $S$와 $\bar{S} = V \setminus S$로 나누어 $s \in S$, $t \in \bar{S}$인 분할이며, 절단의 용량은 $S$에서 $\bar{S}$로 가는 변의 용량 합입니다.

포드-풀커슨 방법

1. 초기 흐름을 0으로 설정합니다.
2. 잔여 그래프(Residual Graph)에서 $s$에서 $t$로의 증가 경로(Augmenting Path)를 찾습니다.
3. 증가 경로를 따라 흐름을 증가시킵니다.
4. 증가 경로가 없을 때까지 반복합니다.

에드몬드-카프(Edmonds-Karp) 알고리즘은 BFS로 증가 경로를 찾아 시간 복잡도 $O(VE^2)$를 보장합니다.

그래프 색칠

그래프 색칠(Graph Coloring)은 인접한 꼭짓점이 같은 색을 갖지 않도록 꼭짓점에 색을 배정하는 것입니다.

색수 (Chromatic Number)

그래프 $G$의 색수(Chromatic Number) $\chi(G)$는 적절한 색칠에 필요한 최소 색의 수입니다.

색수의 상한

• 탐욕 상한: $\chi(G) \leq \Delta(G) + 1$ (모든 그래프)
• 브룩스 정리(Brooks' Theorem): 완전 그래프와 홀수 순환을 제외하면 $\chi(G) \leq \Delta(G)$

색다항식 (Chromatic Polynomial)

$P(G, k)$는 그래프 $G$를 $k$가지 색으로 적절히 색칠하는 방법의 수를 나타내는 다항식입니다.

• $P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1) = k^{\underline{n}}$
• $P(T_n, k) = k(k-1)^{n-1}$ (트리)
• $P(C_n, k) = (k-1)^n + (-1)^n(k-1)$ (순환 그래프)

4색 정리 (Four Color Theorem)

5색 정리는 비교적 간단히 증명됩니다: 오일러 공식에 의해 평면 그래프는 차수가 5 이하인 꼭짓점을 반드시 포함하며, 귀납법으로 5색 색칠이 가능함을 보입니다.

평면 그래프

정의

평면 그래프(Planar Graph)는 변이 교차하지 않도록 평면에 그릴 수 있는 그래프입니다.

오일러 공식 (Euler's Formula)

증명 스케치: $E = 0$이면 $V = 1$, $F = 1$이므로 성립. 신장 트리에서 시작하여 변을 하나씩 추가할 때마다 면이 하나씩 늘어나므로 $V - E + F$는 항상 2를 유지합니다.

오일러 공식의 따름정리

단순 연결 평면 그래프 ($V \geq 3$)에서:

• $E \leq 3V - 6$
• 삼각형이 없으면: $E \leq 2V - 4$
• 차수가 5 이하인 꼭짓점이 반드시 존재합니다.

비평면 그래프 판별 예시:

쿠라토프스키 정리 (Kuratowski's Theorem, 1930)

바그너 정리(Wagner's Theorem): 동치 조건으로 "$G$에 $K_5$ 또는 $K_{3,3}$을 축소(minor)로 포함하지 않음"도 있습니다.

이분 매칭

매칭의 정의

그래프 $G$에서 매칭(Matching) $M \subseteq E$은 서로 꼭짓점을 공유하지 않는 변들의 집합입니다.

• 최대 매칭(Maximum Matching): $|M|$이 최대인 매칭
• 완전 매칭(Perfect Matching): 모든 꼭짓점이 매칭된 변에 포함되는 매칭 ($|M| = |V|/2$)

홀 결혼 정리 (Hall's Marriage Theorem)

직관: $X$의 어떤 부분집합을 택해도, 그 부분집합의 이웃이 충분히 많아야 모두 매칭할 수 있습니다. 이 조건을 홀 조건(Hall's condition)이라 합니다.

예시: 3명의 학생 $\{s_1, s_2, s_3\}$이 각각 지원 가능한 과목이 있을 때:

홀 조건 확인: $|N(\{s_1\})| = 2 \geq 1$, $|N(\{s_1, s_2\})| = 3 \geq 2$, $|N(\{s_1, s_2, s_3\})| = 3 \geq 3$ 등 모든 부분집합에 대해 성립하므로 완전 매칭이 존재합니다.

쾨니히 정리 (Konig's Theorem)

여기서:

• $\nu(G)$: 최대 매칭의 크기 (매칭 수, matching number)
• $\tau(G)$: 최소 꼭짓점 덮개의 크기 (모든 변의 적어도 한 끝점을 포함하는 최소 꼭짓점 집합)

이분 매칭 알고리즘

그래프 동형 판정

두 그래프 $G_1 = (V_1, E_1)$과 $G_2 = (V_2, E_2)$가 동형(Isomorphic)이라 함은, 전단사 함수 $\phi: V_1 \to V_2$가 존재하여 $\{u,v\} \in E_1 \iff \{\phi(u), \phi(v)\} \in E_2$를 만족하는 것입니다. 동형 판정은 일반적으로 어려운 문제이며, 다양한 접근법이 있습니다.

풀이 1: 그래프 불변량 활용

동형인 두 그래프는 반드시 다음 불변량(Invariant)이 같아야 합니다. 불변량이 다르면 동형이 아님을 즉시 판정할 수 있습니다.

예시: 다음 두 그래프가 동형인지 판별하십시오.

• $G_1$: $V_1 = \{a,b,c,d,e\}$, 차수열 $= (2,2,2,3,3)$
• $G_2$: $V_2 = \{1,2,3,4,5\}$, 차수열 $= (2,2,2,3,3)$

차수열이 같으므로 불변량만으로는 판별할 수 없습니다. 다음 방법을 시도해야 합니다.

풀이 2: 인접 행렬을 이용한 판정

두 그래프 $G_1$, $G_2$의 인접 행렬을 $A_1$, $A_2$라 하면, $G_1 \cong G_2 \iff$ 치환 행렬(permutation matrix) $P$가 존재하여 다음이 성립합니다:

꼭짓점의 순서를 바꾸는 모든 치환을 시도하면 $n!$가지를 확인해야 하므로, 꼭짓점 수가 적은 경우에만 실용적입니다.

풀이 3: 정점 정제 (Vertex Refinement)

색 정제(Color Refinement) 알고리즘은 반복적으로 꼭짓점을 분류하여 동형 가능성을 판단합니다.

1. 초기화: 모든 꼭짓점에 차수를 색(label)으로 부여합니다.
2. 정제: 각 꼭짓점의 색을 (현재 색, 이웃들의 색 다중집합)으로 갱신합니다.
3. 반복: 색 분포가 더 이상 변하지 않을 때까지 반복합니다.
4. 비교: 최종 색 분포가 두 그래프에서 다르면 동형이 아닙니다.

최단 경로 알고리즘 비교 심화

세 가지 주요 최단 경로 알고리즘의 핵심 원리와 적용 상황을 비교합니다.

다익스트라 알고리즘의 정당성 증명

다익스트라 알고리즘이 올바른 최단 거리를 구하는 이유를 귀납법으로 증명합니다.

벨만-포드: 음의 가중치 처리

벨만-포드 알고리즘은 음의 가중치를 허용하며, 음의 순환(Negative Cycle)까지 감지할 수 있습니다.

핵심 원리: $k$번째 반복 후, 최대 $k$개의 변을 사용하는 최단 경로가 올바르게 계산됩니다. 최단 경로는 최대 $|V|-1$개의 변을 가지므로 $|V|-1$번 반복이면 충분합니다.

음의 순환 감지:

단계별 예시: 음의 가중치가 포함된 그래프에서 벨만-포드 실행:

변 목록: $(A,B,4)$, $(A,C,2)$, $(B,D,3)$, $(C,B,-1)$, $(D,E,2)$, $(C,E,7)$

2번째 반복에서 $C \to B$의 음의 가중치 $-1$을 거쳐 $d(B) = 2 + (-1) = 1$로 갱신된 것을 확인할 수 있습니다. 다익스트라에서는 이런 갱신이 불가능합니다.

플로이드-워셜: 모든 쌍 최단 경로

동적 프로그래밍의 전형적 응용으로, 중간 꼭짓점을 하나씩 추가하며 최단 거리를 갱신합니다.

상태 전이:

여기서 $d_{ij}^{(k)}$는 꼭짓점 $\{1, \ldots, k\}$만 중간 경유지로 사용할 때 $i \to j$의 최단 거리입니다.

완전한 예시: 4개 꼭짓점 그래프:

세 알고리즘의 종합 비교

최소 신장 트리 알고리즘 비교 심화

크루스칼, 프림, 보루브카 세 알고리즘의 핵심 전략을 비교합니다. 세 알고리즘 모두 탐욕(Greedy) 전략에 기반하며, 절단 성질과 순환 성질이 정당성을 보장합니다.

순환 성질 (Cycle Property)

보루브카 알고리즘 (Borůvka's Algorithm, 1926)

MST를 구하는 가장 오래된 알고리즘으로, 병렬화에 유리합니다.

1. 각 꼭짓점을 별도의 성분(component)으로 시작합니다.
2. 각 성분에서 다른 성분으로 연결되는 변 중 가중치가 최소인 변을 선택합니다.
3. 선택된 변들을 모두 추가하여 성분들을 합칩니다.
4. 하나의 성분이 될 때까지 반복합니다.

시간 복잡도: $O(E \log V)$. 각 단계에서 성분 수가 절반 이하로 줄어들므로 최대 $O(\log V)$번 반복합니다.

세 MST 알고리즘 종합 비교

프림 단계별 예시: 크루스칼 예시와 같은 그래프에서 꼭짓점 $A$부터 시작:

MST 가중치 합: $1 + 3 + 2 = 6$ (크루스칼과 동일한 결과)

네트워크 흐름 알고리즘 비교

포드-풀커슨 방법과 에드몬드-카프 알고리즘의 차이점을 상세히 비교합니다.

포드-풀커슨 방법 상세

포드-풀커슨은 "방법(method)"이지 특정 "알고리즘"이 아닙니다. 증가 경로를 찾는 전략을 지정하지 않으므로, 경로 선택에 따라 성능이 크게 달라집니다.

잔여 그래프(Residual Graph) $G_f$:

• 순방향 변: $c_f(u,v) = c(u,v) - f(u,v) > 0$인 변 (아직 용량 여유 있음)
• 역방향 변: $c_f(v,u) = f(u,v) > 0$인 변 (이미 보낸 흐름을 취소 가능)

단계별 예시:

$s \to a$ (용량 10), $s \to b$ (용량 10), $a \to b$ (용량 2), $a \to t$ (용량 8), $b \to t$ (용량 9)인 네트워크에서:

최대 흐름: $17$

에드몬드-카프 알고리즘: BFS 기반 개선

에드몬드-카프는 포드-풀커슨에서 증가 경로를 BFS(너비 우선 탐색)으로 찾아 최단 증가 경로를 선택합니다.

포드-풀커슨 vs 에드몬드-카프

매칭 이론 심화

홀 정리의 증명

쾨니히 정리의 응용

쾨니히 정리 $\nu(G) = \tau(G)$는 이분 그래프에서만 성립합니다. 일반 그래프에서는 $\nu(G) \leq \tau(G) \leq 2\nu(G)$입니다.

예시: $K_{3,3}$에서:

• 최대 매칭: $\nu = 3$ (완전 매칭 가능)
• 최소 꼭짓점 덮개: $\tau = 3$ (한쪽 전체를 선택)
• 쾨니히 정리에 의해 $\nu = \tau = 3$

헝가리안 알고리즘 (Hungarian Algorithm)

가중 이분 매칭에서 최소(또는 최대) 비용 완전 매칭을 구하는 $O(V^3)$ 알고리즘입니다.

알고리즘 개요:

1. 초기 레이블링: 각 행에서 최솟값을 빼고, 각 열에서도 최솟값을 뺍니다 (축약).
2. 0-변 매칭: 비용이 0인 변들로 최대 매칭을 시도합니다.
3. 라벨 조정: 매칭이 완전하지 않으면, 쾨니히 정리를 이용하여 최소 꼭짓점 덮개를 구하고 라벨을 조정합니다.
4. 반복: 완전 매칭이 될 때까지 2-3을 반복합니다.

비용 행렬 예시:

0-변으로 완전 매칭: 행1→열2, 행2→열3, 행3→열1. 원래 비용: $2 + 1 + 4 = 7$ (최소 비용)

그래프 색칠 알고리즘 비교

탐욕 색칠 (Greedy Coloring)

꼭짓점을 순서대로 방문하며, 이웃에 사용되지 않은 가장 작은 번호의 색을 칠합니다.

• 항상 $\chi(G) \leq \Delta(G) + 1$을 보장합니다.
• 꼭짓점 순서에 따라 결과가 달라지며, 최악의 경우 최적과 크게 차이날 수 있습니다.

예시: 순환 $C_5 = (v_1, v_2, v_3, v_4, v_5)$에 탐욕 색칠:

3색 사용: 이 경우 $\chi(C_5) = 3$이므로 최적입니다.

웰시-파웰 알고리즘 (Welsh-Powell Algorithm)

탐욕 색칠의 개선 버전으로, 차수가 큰 꼭짓점부터 먼저 색칠합니다.

1. 모든 꼭짓점을 차수 내림차순으로 정렬합니다.
2. 정렬된 순서로 탐욕 색칠을 수행합니다.

브룩스 정리 증명 스케치

색칠 알고리즘 비교

평면 그래프 심화

오일러 공식의 다양한 증명

증명 1: 귀납법 (변의 수에 대한 귀납)

$E = 0$이면 연결 그래프는 단일 꼭짓점이므로 $V = 1$, $F = 1$ (외부 면만 존재), $1 - 0 + 1 = 2$. ✓

변 $e$가 순환에 포함된 경우: $e$를 제거하면 면 하나가 사라지고 변 하나가 줄어듭니다. 귀납 가설에 의해 $(V) - (E-1) + (F-1) = 2$이므로 $V - E + F = 2$. ✓

변 $e$가 다리(bridge)인 경우: $e$를 제거하면 성분이 둘로 나뉩니다. 각 성분에 대해 $V_i - E_i + F_i = 2$를 적용하고 합산하면 됩니다.

증명 2: 신장 트리를 이용한 증명

연결 평면 그래프의 신장 트리 $T$는 $V$개의 꼭짓점과 $V-1$개의 변을 가집니다. $T$는 면이 1개(외부 면)이므로 $V - (V-1) + 1 = 2$. ✓

$T$에 변을 하나씩 추가합니다. 트리가 아닌 변을 추가할 때마다 정확히 하나의 순환이 생기고, 이 순환이 기존 면을 둘로 나눕니다. 따라서 변 1 추가, 면 1 추가이므로 $V - E + F$는 변함없이 2입니다. ✓

증명 3: 쌍대 그래프를 이용한 논증

평면 그래프 $G$의 쌍대 그래프(Dual Graph) $G^*$는 $G$의 각 면을 꼭짓점으로, 인접한 면을 변으로 연결합니다. $G^*$의 신장 트리와 $G$의 여(complement) 신장 트리의 관계를 이용하면 오일러 공식이 자연스럽게 유도됩니다.

쿠라토프스키 정리 심화

$K_5$가 비평면인 증명:

$K_5$: $V = 5$, $E = 10$. 평면이면 $E \leq 3V - 6 = 9$이어야 하는데, $10 > 9$이므로 비평면입니다.

$K_{3,3}$이 비평면인 증명:

$K_{3,3}$: $V = 6$, $E = 9$. $3V - 6 = 12$이므로 이 부등식만으로는 판별할 수 없습니다. 그러나 $K_{3,3}$은 이분 그래프이므로 삼각형이 없어 모든 면이 길이 4 이상의 경계를 가집니다. 따라서 $2E \geq 4F$, 즉 $F \leq E/2 = 4.5$. 오일러 공식에 의해 $F = 2 - V + E = 2 - 6 + 9 = 5$인데, $5 > 4.5$이므로 모순. 따라서 비평면입니다.

대수적 그래프 이론

대수적 그래프 이론(Algebraic Graph Theory)은 행렬과 선형대수를 이용하여 그래프의 성질을 분석하는 분야입니다.

인접 행렬의 스펙트럼

그래프 $G$의 인접 행렬 $A$의 고유값(eigenvalue) $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$을 $G$의 스펙트럼(spectrum)이라 합니다.

기본 성질:

• $\sum_{i=1}^{n} \lambda_i = \text{tr}(A) = 0$ (대각 성분이 모두 0이므로)
• $\sum_{i=1}^{n} \lambda_i^2 = \text{tr}(A^2) = 2|E|$ (각 변이 두 방향의 길이-2 보행에 기여)
• $\sum_{i=1}^{n} \lambda_i^3 = \text{tr}(A^3) = 6 \times (\text{삼각형의 수})$
• 최대 고유값 $\lambda_1$에 대해: $\frac{2|E|}{|V|} \leq \lambda_1 \leq \Delta(G)$

예시: 순환 그래프 $C_4$의 스펙트럼:

라플라시안 행렬 (Laplacian Matrix)

그래프 $G$의 라플라시안 행렬은 다음과 같이 정의됩니다:

여기서 $D$는 차수 대각 행렬 ($D_{ii} = \deg(v_i)$), $A$는 인접 행렬입니다.

라플라시안의 성질:

• $L$은 양반정치(positive semidefinite)입니다: 모든 고유값 $\mu_i \geq 0$
• 최소 고유값 $\mu_1 = 0$이며, 대응하는 고유벡터는 $\mathbf{1} = (1, 1, \ldots, 1)^T$
• $\mu_2 = 0$인 것의 개수 = 연결 성분의 수
• 두 번째 작은 고유값 $\mu_2$를 대수적 연결도(Algebraic Connectivity) 또는 피들러 값(Fiedler Value)이라 하며, 그래프의 연결 강도를 나타냅니다

키르히호프의 행렬-트리 정리

예시: $K_4$의 라플라시안 고유값은 $0, 4, 4, 4$이므로:

검증: 케일리 공식 $4^{4-2} = 16$. ✓

예시: $C_4$의 라플라시안:

램지 이론

램지 이론(Ramsey Theory)은 "충분히 큰 구조에서는 반드시 특정 패턴이 나타난다"는 원리를 다룹니다.

램지 수의 정의

램지 수 $R(s, t)$는 다음을 만족하는 최소 자연수 $n$입니다:

$R(3,3) = 6$ 증명

이것은 "파티 문제"라고도 합니다: 6명이 모이면, 서로 모두 아는 3명 또는 서로 모두 모르는 3명이 반드시 존재합니다.

알려진 램지 수

램지 수의 상한과 하한

상한 (에르되시-세케레시, 1935):

특히 $R(s, s) \leq \binom{2s-2}{s-1} \leq 4^{s-1}$입니다.

하한 (에르되시, 1947, 확률적 방법):

이것은 확률적 방법(probabilistic method)의 초기 응용으로, 실제로 반례를 구성하지 않고 "존재성"만 증명합니다.

확률적 그래프

확률적 그래프(Random Graph)는 확률 모형에 따라 생성되는 그래프로, 그래프의 "전형적인" 성질을 연구하는 데 사용됩니다.

에르되시-레니 모형 (Erdős-Rényi Model)

두 가지 모형이 있습니다:

$G(n, p)$ 모형이 분석에 더 편리하여 널리 사용됩니다.

$G(n, p)$의 기본 성질

• 변의 기대값: $\mathbb{E}[|E|] = \binom{n}{2} p \approx \frac{n^2 p}{2}$
• 차수 분포: 각 꼭짓점의 차수는 $\text{Binomial}(n-1, p)$을 따릅니다. $np$가 상수일 때 포아송 분포로 근사됩니다.
• 삼각형의 기대값: $\mathbb{E}[\text{삼각형 수}] = \binom{n}{3} p^3$

문턱 현상 (Threshold Phenomenon)

확률적 그래프의 가장 놀라운 성질은 문턱 현상입니다. 특정 성질이 $p$가 문턱값 이하일 때 거의 확실히 성립하지 않다가, 문턱값 이상이 되면 거의 확실히 성립합니다.

거대 성분의 상전이 (Phase Transition)

$G(n, p)$에서 $p = c/n$으로 놓으면:

거대 성분의 크기: $c > 1$일 때, 거대 성분에 속하는 꼭짓점의 비율 $\rho$는 다음 방정식의 유일한 양의 해입니다:

확률적 방법과 그래프 이론

에르되시가 개척한 확률적 방법(Probabilistic Method)은 특정 성질을 만족하는 그래프의 존재성을 증명하는 강력한 도구입니다. 핵심 아이디어:

이 방법은 램지 이론의 하한, 그래프 색칠의 존재성 등 다양한 조합론적 문제에서 핵심적으로 사용됩니다.

주요 정리 요약

참고자료

• Diestel, R. — Graph Theory, Springer
• West, D. B. — Introduction to Graph Theory, Pearson
• Bondy, J. A. & Murty, U. S. R. — Graph Theory, Springer
• Cormen, T. H. et al. — Introduction to Algorithms (CLRS), MIT Press (최단 경로, 네트워크 흐름)
• 이산수학 — 그래프 이론의 기초
• 조합론 — 그래프의 세기 문제