10.1 정점 차수 Vertex Degrees

유향 그래프(digraph)는 정점 집합 \(V\)와 정점들의 순서쌍을 원소로 갖는 간선 집합 \(E \subseteq V \times V\) 로 이루어진 쌍 \(G = (V, E)\)입니다. 무향 그래프와 달리 \((u, v)\)와 \((v, u)\)는 서로 다른 간선이에요. 화살표 \(u \to v\)는 "\(u\)에서 \(v\)로 가는 방향이 있다"는 뜻이고, 거꾸로는 가지 못할 수도 있습니다. 트위터의 팔로우 관계가 정확히 이런 구조죠. 내가 누군가를 팔로우한다고 그 사람이 나를 팔로우하는 건 아니니까요.

무향 그래프에서는 모든 차수의 합이 간선 수의 두 배라는 악수 정리가 있었죠. 유향 그래프에서는 한 간선이 한쪽엔 나가는 차수 1, 다른 쪽엔 들어오는 차수 1로만 기여하므로 다음이 성립합니다.

10.2 워크와 경로 Walks and Paths

그래프 위에서 화살표를 따라 정점들을 옮겨다니는 행위를 형식화합시다. 길이 \(k\)인 워크(walk)는 정점-간선 교대 수열 \(v_0, e_1, v_1, e_2, \dots, e_k, v_k\)이고, 각 \(e_i\)가 \(v_{i-1} \to v_i\)인 간선이어야 합니다. 정점이나 간선이 반복되어도 괜찮아요. 같은 모서리를 두 번 지나지 않으면 트레일(trail), 같은 정점을 두 번 지나지 않으면 단순 경로(simple path)라고 부릅니다.

한국어 학생들이 자주 헷갈리는 지점이 하나 있어요. 경로의 길이는 정점 수가 아니라 간선 수입니다. 정점 \(a, b, c\)를 지나는 경로 \(a \to b \to c\)의 길이는 2이지 3이 아닙니다. 사람을 셀 때는 두 명이 손을 잡으면 한 줄, 세 명이면 두 줄이듯, 간선이 한 칸이라고 생각하면 편해요.

10.3 인접 행렬 Adjacency Matrices

유향 그래프를 컴퓨터에 저장하는 가장 깔끔한 방법은 행렬을 쓰는 것입니다. 정점이 \(n\)개일 때, \(n \times n\) 행렬 \(A\)를 다음과 같이 정의해요. \(A_{ij} = 1\)이면 간선 \(v_i \to v_j\)가 있고, 아니면 \(0\). 이 행렬을 인접 행렬(adjacency matrix)이라 부릅니다. 무향 그래프와 달리 일반적으로 대칭이 아니에요.

이 정리는 단순한 산수처럼 보이지만 강력합니다. 길이 \(k\) 워크의 수를 일일이 세지 않고 행렬 곱셈만으로 답을 얻을 수 있고, 빠른 거듭제곱 알고리즘을 쓰면 \(O(n^3 \log k)\)에 끝납니다.

10.4 워크 관계 Walk Relations

그래프 위에서 "\(u\)에서 \(v\)로 갈 수 있는가?"라는 질문은 곧 도달가능성(reachability) 문제입니다. 유향 그래프 \(G\) 위에서 워크 관계 \(G^*\)를 다음과 같이 정의합시다. \(u\, G^*\, v\) 라는 것은 \(u\)에서 \(v\)로 가는 길이 \(\geq 0\)인 워크가 존재한다는 의미입니다 (길이 0 워크는 자기 자신이에요).

워크 관계 \(G^*\)는 두 가지 좋은 성질을 갖습니다. 첫째, 반사적이에요. 모든 정점 \(u\)에 대해 길이 0 워크가 자명히 있죠. 둘째, 추이적입니다. \(u G^* v\)이고 \(v G^* w\)이면 두 워크를 이어 붙여 \(u G^* w\)가 됩니다. 이 두 성질을 만족하는 관계를 일반적으로 전순서(preorder)라고 부릅니다.

10.5 DAG와 스케줄링 Directed Acyclic Graphs & Scheduling

유향 그래프 중에서 사이클이 없는 것을 DAG(directed acyclic graph)라고 부릅니다. 일상 어디에나 등장해요. 메이크파일의 빌드 의존성, 강의 계획표의 선수과목, 스프레드시트의 셀 의존성, 깃 커밋 이력 모두 DAG 구조를 갖죠. "A를 하기 전에 B와 C를 끝내야 한다"라는 종류의 제약은 모두 DAG로 표현됩니다.

증명의 핵심은 "DAG에는 들어오는 차수가 0인 정점이 항상 존재한다"는 보조정리예요. 만약 모든 정점의 \(\deg^- \geq 1\)이면, 어디서든 거꾸로 화살표를 따라 무한히 갈 수 있는데 정점이 유한하므로 비둘기집에 의해 사이클이 생깁니다 ― 모순. 그래서 \(\deg^-(v) = 0\)인 정점을 골라 맨 앞에 두고 그 정점을 지운 뒤 재귀하면 위상 정렬이 만들어집니다. 이걸 알고리즘으로 옮긴 게 칸(Kahn)의 알고리즘이에요.

def topo_sort(V, E):
    indeg = {v: 0 for v in V}
    for (u, v) in E:
        indeg[v] += 1
    ready = [v for v in V if indeg[v] == 0]
    order = []
    while ready:
        u = ready.pop()
        order.append(u)
        for (a, b) in E:
            if a == u:
                indeg[b] -= 1
                if indeg[b] == 0:
                    ready.append(b)
    if len(order) != len(V):
        raise ValueError("graph has a cycle")
    return order

10.6 부분 순서 Partial Orders

10.5의 의존성 관계를 추상화하면 부분 순서가 됩니다. 직관적으로 부분 순서는 "어떤 둘은 비교 가능하지만, 어떤 둘은 비교 불가능"한 상황을 모형화해요.

예시는 흔합니다. 자연수 위의 \(\leq\), 양의 정수 위의 정수 나눗셈 \(|\) (\(a \mid b\)는 \(a\)가 \(b\)를 나눈다는 뜻), 집합 위의 부분집합 관계 \(\subseteq\) 등이 모두 부분 순서예요. 자연수의 \(\leq\)는 모든 둘이 비교되지만, 정수 나눗셈에서는 3과 5가 서로 나누지도 나누어지지도 않으므로 비교 불가능합니다.

10.7 집합 포함으로 표현 Representing Partial Orders by Set Containment

겉모습은 다양해 보이지만, 사실 모든 부분 순서는 깊은 의미에서 본질적으로 한 가지 모양을 합니다. 그게 바로 집합 포함 관계 \(\subseteq\)예요.

이 정리는 단순하지만 철학적으로 시원합니다. "어떤 추상적인 순서든 결국 ‘이 원소 아래에 어떤 원소들이 있는가’의 집합 포함으로 환원된다." 즉 부분 순서론의 모든 일반론은 \(\subseteq\) 의 일반론과 같다는 뜻이에요. 컴퓨터 과학에서 타입의 서브타이핑(subtyping), 권한 격자(lattice of capabilities) 같은 구조도 결국 이 표현 정리의 그림자입니다.

10.8 전순서 Linear Orders

부분 순서 중에서 특히 임의의 두 원소가 비교 가능한 경우를 전순서(linear order, total order)라 부릅니다. 직관적으로 한 줄로 쭉 세울 수 있다는 뜻이에요.

전순서의 대표 예는 자연수 \((\mathbb{N}, \leq)\), 정수 \((\mathbb{Z}, \leq)\), 실수 \((\mathbb{R}, \leq)\), 그리고 사전식 순서로 정렬한 문자열들입니다. 반면 부분집합 \(\subseteq\)나 정수 나눗셈 \(\mid\)는 전순서가 아니에요.

이 정리의 알고리즘적 사촌이 바로 위상 정렬(10.5)이에요. DAG의 도달가능성 부분 순서를 어떤 전체적 일렬 순서(스케줄)로 확장한 것이 위상 정렬이거든요. 그래서 위상 정렬은 일반적으로 유일하지 않아요. 비교 불가능했던 두 원소를 어느 쪽이 먼저인지 자유롭게 선택할 수 있기 때문입니다.

10.9 곱 순서 Product Orders

두 포셋이 있으면 자연스럽게 그 곱집합 위에 새 부분 순서를 만들 수 있습니다. 이를 곱 순서라 해요. 컴퓨터과학에서는 다차원 좌표 비교, 다중 우선순위 정렬, 동적 계획법의 부분 문제 의존 관계 등에 끊임없이 등장합니다.

주의할 점: 두 인자 \((A, \preceq_A)\)와 \((B, \preceq_B)\)가 모두 전순서라 해도 곱 순서는 전순서가 아닙니다. 예를 들어 \((\mathbb{N}, \leq)\)와 자기 자신의 곱을 보면, \((1, 2)\)와 \((2, 1)\)은 어느 쪽도 다른 쪽을 좌표별로 지배하지 못해요. 비교 불가능합니다.

덧붙이자면, 사전식 순서는 곱 순서와 다른 또 한 가지 자연스런 곱 구조예요. \((a_1, b_1) <_{\text{lex}} (a_2, b_2)\)는 "\(a_1 < a_2\) 또는 \(a_1 = a_2\)이고 \(b_1 < b_2\)". 사전식 순서는 두 인자가 전순서이면 곱도 전순서로 유지되지만 직관과 어긋나는 결과(\(\epsilon\)-우월 같은)를 낳기도 하니 상황에 맞게 골라 써야 합니다.

10.10 동치관계 Equivalence Relations

부분 순서가 "어떤 것이 다른 것보다 더 큰가"를 다룬다면, 동치관계는 "두 원소가 같은 종류인가"를 다룹니다. 약간 다른 세계지만 정의 형식은 비슷해요.

동치관계의 가장 친숙한 예가 모듈로 합동 \(a \equiv b \pmod n\)입니다. 같은 나머지를 갖는 정수들끼리 같다고 보는 거죠. 또 7장에서 다뤘던 함수의 동치, 도형의 합동 등도 모두 동치관계입니다.

이 정리 덕분에 "동치관계"와 "분할"은 같은 개념의 두 얼굴이라고 봐도 됩니다. 한쪽에서 다른 쪽으로 자유롭게 오갈 수 있어요. 컴퓨터과학에서는 그래프의 강한 연결요소(SCC), 합동 연산을 통한 자료구조(union-find), 컴파일러의 등가 변수 분석 등에서 매일같이 등장합니다.

10.11 관계 성질 요약 Summary of Relational Properties

10장에서 등장한 다양한 관계의 성질을 한 표로 정리하고 마무리합시다. 각 행은 관계의 종류이고, 각 열은 그 관계가 만족해야 하는 조건이에요. 같은 정의를 외우려 하기보단, 어떤 조합이 어떤 의미를 갖는지 음미하면 좋습니다.

다음 챕터에서는 화살표 방향을 잊은 무향 그래프로 돌아가, 연결성과 트리의 세계를 본격적으로 탐험합니다. 거기서 만나는 도구들도 결국 이 챕터에서 다진 관계의 언어 위에 세워진 것임을 기억하면 좋겠어요.