Graphs

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 09

Intuition

그래프는 객체들(정점) 사이의 관계(간선)를 수학적으로 추상화한 도구로, 네트워크, 경로 탐색, 자원 할당 등 실세계의 복잡한 연결성을 해결하는 강력한 이산 구조이다.

One-liner

객체 간의 관계를 정점과 간선으로 정의하고, 연결성, 경로 최적화, 평면성 및 채색 문제를 통해 다양한 공학적 문제를 해결하는 이론이다.

Prerequisites

• 집합론 (Set Theory) (Ch. 2): 정점과 간선은 집합으로 정의되므로 합집합, 교집합, 부분집합 개념이 필수적이다.
• 관계 (Relations) (Ch. 8): 방향 그래프는 이항 관계의 기하학적 표현임을 이해해야 한다.
• 알고리즘 복잡도 (Big-O Notation) (Ch. 3): 최단 경로 알고리즘 등의 효율성을 평가할 때 필요하다.

Goals

• 그래프의 다양한 유형(단순, 멀티, 의사, 방향 그래프)을 구분하고 정의할 수 있다.
• 핸드셰이킹 정리(Handshaking Theorem) 등 차수와 관련된 정리를 활용할 수 있다.
• 인접 행렬 및 인접 리스트를 이용해 그래프를 컴퓨터 상에 표현할 수 있다.
• 연결성(Connectivity), 오일러 경로, 해밀턴 경로의 존재 조건을 판별할 수 있다.
• 다익스트라(Dijkstra) 알고리즘을 사용하여 최단 경로 문제를 해결할 수 있다.
• 그래프의 평면성(Planarity)과 채색(Coloring)의 기본 원리를 이해한다.

Core Concepts

9.1 Graphs and Graph Models

그래프는 기본적으로 정점(Vertex)과 이들을 잇는 간선(Edge)의 집합으로 구성된다. (p.589)

9.2 Graph Terminology and Special Types

그래프의 성질을 기술하기 위한 기초 용어와 특수 그래프를 다룬다. (p.598)

Definition: Degree

무방향 그래프에서 정점 $v$의 차수 (Degree, $deg(v)$)는 해당 정점에 부속된 간선의 수이다. 단, 루프(Loop)는 차수에 2번 기여한다. (p.598)

• Isolated Vertex: 차수가 0인 정점.
• Pendant Vertex: 차수가 1인 정점.
• Complete Graph ($K_n$): 모든 정점 쌍 사이에 간선이 하나씩 있는 단순 그래프. (p.601)
• Bipartite Graph (이분 그래프): 정점 집합을 두 개의 서로소 집합 $V_1, V_2$로 나누어 모든 간선이 한쪽 집합의 정점과 다른 쪽 집합의 정점을 잇게 할 수 있는 그래프. (p.602)

9.3 Representing Graphs and Isomorphism

그래프를 행렬이나 리스트로 표현하고, 두 그래프의 구조적 동일성을 확인한다. (p.611)

• Adjacency Matrix (인접 행렬): 정점 간 인접 여부를 0과 1로 표현한 $n \times n$ 행렬. (p.612)
• Isomorphism (동형): 두 그래프 사이의 정점 일대일 대응 함수가 존재하여 인접 관계가 보존되는 경우. (p.615)

9.4 Connectivity

정점들이 경로로 연결되어 있는 상태를 정의한다. (p.621)

Definition: Path

길이 $n$의 경로 (Path)는 정점과 간선의 교대 열로, 단순 경로(Simple Path)는 같은 간선을 두 번 포함하지 않는다. (p.622)

• Connected Graph: 모든 정점 쌍 사이에 경로가 존재하는 무방향 그래프. (p.624)
• Strongly Connected: 방향 그래프에서 모든 $a, b$ 정점 쌍에 대해 $a$에서 $b$, $b$에서 $a$로 가는 방향 경로가 모두 존재하는 경우. (p.626)

9.5 Euler and Hamilton Paths

• Euler Circuit: 모든 간선을 정확히 한 번씩 지나는 회로. 모든 정점의 차수가 짝수여야 한다. (p.633)
• Hamilton Circuit: 모든 정점을 정확히 한 번씩 지나는 회로. 필요충분조건은 아직 밝혀지지 않았다. (p.638)

9.6 Shortest-Path Problems

간선에 가중치가 부여된 그래프에서 두 정점 사이의 최소 비용 경로를 찾는다. (p.647)

• Dijkstra's Algorithm: 단일 출발지에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘 ($O(n^2)$). (p.651)
• Traveling Salesman Problem (외판원 문제): 모든 정점을 방문하고 돌아오는 가중치 합이 최소인 해밀턴 회로를 찾는 문제 (NP-Hard). (p.653)

9.7 Planar Graphs

평면 위에서 간선들이 교차하지 않게 그릴 수 있는 그래프이다. (p.657)

Theorem: Euler's Formula

연결된 평면 단순 그래프의 정점 수 $v$, 간선 수 $e$, 면 수 $r$ 사이에는 다음 관계가 성립한다.

$$r = e - v + 2$$

(p.660)

• Kuratowski's Theorem: 그래프가 비평면일 필요충분조건은 $K_{3,3}$이나 $K_5$와 동상(homeomorphic)인 부분 그래프를 포함하는 것이다. (p.664)

9.8 Graph Coloring

인접한 정점을 서로 다른 색으로 칠할 때 필요한 최소 색상을 연구한다. (p.666)

• Chromatic Number ($\chi(G)$): 그래프 $G$를 채색하는 데 필요한 최소 색의 수. (p.667)
• Four Color Theorem: 모든 평면 그래프의 채색수는 4 이하이다. (p.668)

Notation

기호	의미
$G = (V, E)$	정점 집합 $V$와 간선 집합 $E$로 구성된 그래프
$deg(v)$	정점 $v$의 차수
$deg^+(v), deg^-(v)$	방향 그래프에서의 외차수(Out-degree)와 내차수(In-degree)
$K_n$	$n$개의 정점을 가진 완전 그래프
$K_{m,n}$	$m, n$개의 정점으로 나뉜 완전 이분 그래프
$\chi(G)$	그래프 $G$의 채색수

Key Theorems & Formulas

Theorem (The Handshaking Theorem)

조건: $G = (V, E)$가 무방향 그래프일 때.

결론:

$$2e = \sum_{v \in V} deg(v)$$

즉, 모든 정점 차수의 합은 간선 수의 2배이며, 따라서 차수가 홀수인 정점의 개수는 항상 짝수이다. (p.599)

Theorem (Dirac's Theorem)

조건: $n \ge 3$인 단순 그래프 $G$에서 모든 정점의 차수가 $n/2$ 이상일 때.

결론: $G$는 해밀턴 회로를 가진다. (p.641)

Intuitions

• 핸드셰이킹 정리: 악수를 하면 두 사람이 손을 한 번씩 내밀듯, 간선 하나는 두 정점의 차수를 각각 1씩 올리기 때문에 전체 합은 항상 짝수가 된다.
• 이분 그래프: 집합 내부에서는 서로 적대적이라 연결되지 않고, 오직 다른 집합하고만 상호작용하는 구조로 이해할 수 있다.
• 오일러 vs 해밀턴: 오일러는 '길(간선)'을 다 밟는 것이 중요하고(청소차), 해밀턴은 '지점(정점)'을 다 방문하는 것이 중요하다(택배 배송).
• 평면성: 입체적으로 꼬인 전선을 평면에 겹치지 않게 배치할 수 있는지를 묻는 회로 설계 문제와 직결된다.

Worked Examples

Example 1: Handshaking Theorem 적용

문제: 정점이 10개이고 모든 정점의 차수가 6인 그래프의 간선 수는? (p.599)

핵심 단계:

1. 모든 차수의 합을 구한다: $10 \times 6 = 60$.
2. 공식 $2e = 60$에 대입한다.
3. $e = 30$.

요점: 차수의 합은 간선의 중복 계산을 포함함을 이해한다.

Example 2: Dijkstra's Algorithm

문제: 가중치 그래프에서 출발점 $a$부터 목적지 $z$까지의 최단 거리 찾기. (p.650)

핵심 단계:

1. 출발점 $a$의 라벨을 0, 나머지를 $\infty$로 초기화한다.
2. 방문하지 않은 정점 중 라벨이 가장 작은 정점 $u$를 선택한다.
3. $u$와 인접한 정점 $v$들에 대해 $L(v) > L(u) + w(u,v)$이면 라벨을 갱신한다.
4. $z$를 방문할 때까지 반복한다.

요점: 탐욕적 선택(Greedy choice)이 전역적 최적해를 보장함을 보여준다.

Common Pitfalls

Pitfall

오일러 회로와 경로의 혼동: 모든 정점의 차수가 짝수여야 회로(출발지로 복귀)가 존재하며, 홀수 차수 정점이 정확히 2개일 때는 경로(복귀 불가)만 존재한다. 2개를 초과하면 둘 다 불가능하다. (p.636)

Pitfall

단순 그래프의 오해: 인접 행렬 $A$에서 대각 성분 $a_{ii}$가 0이 아니거나, $a_{ij}$가 1보다 크면 그것은 단순 그래프가 아니라 루프나 멀티 간선이 있는 그래프이다. (p.613)

Connections

• 선행 개념: Ch. 2 집합론 (정의), Ch. 3 행렬 (인접 행렬 표현 및 복잡도), Ch. 8 관계 (유향 그래프의 대수적 기초).
• 후속 개념: Ch. 10 트리를 포함한 그래프의 세부 알고리즘, 네트워크 흐름(Network Flow). Ch. 12 계산 모델링 (상태 전이도는 유향 그래프).
• 응용 분야: 소셜 네트워크 분석(연결성), 구글 페이지랭크(방향 그래프), 물류 최적화(TSP), 지도 제작(채색).

Critical Notes

교재가 강조하는 것

• 그래프 모델링의 다양성: 생태학, 조직도, 컴퓨터 네트워크 등 실사례를 통한 접근.
• 정형화된 표현법: 알고리즘 구현을 위한 행렬 및 리스트 표현의 중요성.

실제로 중요한 것

• 다익스트라 알고리즘: 실무에서 경로 탐색 엔진의 기초가 되며 면접 등에서도 자주 등장.
• NP-완전 문제의 인식: 해밀턴 회로와 TSP가 계산적으로 매우 어렵다는 것을 인지하고 근사 알고리즘의 필요성을 이해하는 것.

교재가 생략하거나 얼버무리는 것

• 4색 정리의 증명: 컴퓨터를 이용한 수천 시간의 계산이 포함되어 있어 직관적 증명은 생략됨. (p.668)
• Kuratowski 정리의 복잡한 증명: 정리의 진술만 하고 상세 증명은 범위를 벗어남. (p.664)

Open Questions

이해하지 못한 것

• 왜 해밀턴 회로의 존재 여부를 판별하는 간단한 필요충분조건은 발견되지 않았는가? (계산 복잡도 이론과의 연계 학습 필요)

더 알고 싶은 것

• 평면 그래프가 아닌 그래프를 평면에 그릴 때 교차점을 최소화하는 알고리즘(Crossing Number)의 최신 연구 현황. (p.666)
• 그래프 채색 문제를 활용한 실제 컴파일러의 레지스터 할당(Register Allocation) 최적화 과정. (p.672)