11강. 그래프

점과 그 점들을 잇는 선으로 이루어진 그림을 그래프라 합니다. 지하철 노선도, 친구 관계, 웹 페이지의 링크, 분자 구조가 모두 그래프입니다. 이 강에서는 그래프의 기본 용어와 정리(악수 정리, 오일러 회로, 이분 그래프)를 다루고, 인접행렬로 그래프를 행렬 계산으로 바꾸는 방법을 봅니다.

그래프는 “무엇과 무엇이 이어져 있는가”를 나타내는 구조입니다. 도로망, 친구 관계, 웹 페이지의 링크, 회로, 이 사이트의 개념 그래프가 모두 그래프입니다. 5강의 관계를 그림으로 그린 것이라 볼 수도 있습니다.

11.1 정의

정의 11.1 (그래프). 그래프 $G = (V, E)$는 꼭짓점의 집합 $V$와 변의 집합 $E$로 이루어지고, 각 변은 두 꼭짓점을 잇습니다. 이 강에서는 따로 말하지 않으면 단순 그래프(방향이 없고, 자기 자신으로 가는 변과 겹친 변이 없는 그래프)를 다룹니다.

변 $\{u, v\}$가 있으면 $u$와 $v$는 인접(adjacent)합니다.

정의 11.2 (차수). 꼭짓점 $v$에 붙은 변의 수를 $v$의 차수(degree) $\deg v$라 합니다.

정의 11.3 (특별한 그래프).

• 완전그래프 $K_n$: 꼭짓점 $n$개, 모든 두 꼭짓점이 인접. 변은 $\binom{n}{2}$개.
• 순환그래프 $C_n$: 꼭짓점이 원을 이루는 $n$개의 변.
• 완전이분그래프 $K_{m,n}$: $m$개와 $n$개의 두 무리, 서로 다른 무리끼리만 모두 인접. 변은 $mn$개.

11.2 악수 정리

정리 11.4 (악수 정리). $\displaystyle\sum_{v \in V} \deg v = 2|E|$.

증명. 변 하나는 양 끝 꼭짓점의 차수에 1씩, 모두 2를 더합니다. □

따름정리 11.5. 차수가 홀수인 꼭짓점은 짝수 개입니다.

증명. 차수의 합이 짝수이므로, 홀수 차수들의 합도 짝수여야 하고, 그러려면 홀수 차수가 짝수 개여야 합니다. □

예제 11.6. 9명이 각자 정확히 3명과 악수하는 것은 불가능합니다. 차수의 합 $9 \cdot 3 = 27$이 홀수이기 때문입니다.

11.3 경로와 연결성

정의 11.7. 꼭짓점 $v_0, v_1, \dots, v_k$가 차례로 인접할 때 이를 길이 $k$인 보행(walk)이라 합니다. 꼭짓점이 겹치지 않으면 경로(path), 처음과 끝이 같고 그 밖에 겹치지 않으면 회로(사이클)입니다.

정의 11.8. 임의의 두 꼭짓점 사이에 경로가 있으면 그래프가 연결되어 있다고 합니다. “경로로 이어짐”은 동치관계이고, 그 동치류를 연결 성분(connected component)이라 합니다.

11.4 오일러 회로

18세기 쾨니히스베르크의 일곱 다리를 한 번씩만 건너 제자리로 돌아올 수 있는지가 그래프 이론의 시작입니다.

정의 11.9. 모든 변을 정확히 한 번씩 지나는 회로를 오일러 회로(Eulerian circuit), 처음과 끝이 달라도 되면 오일러 경로라 합니다.

정리 11.10 (오일러). 연결된 그래프에 오일러 회로가 있을 필요충분조건은 모든 꼭짓점의 차수가 짝수인 것입니다. 오일러 경로(회로가 아닌)가 있을 필요충분조건은 홀수 차수 꼭짓점이 정확히 2개인 것입니다.

증명 (필요). 회로가 꼭짓점을 지날 때마다 들어오는 변 하나와 나가는 변 하나를 쓰므로 차수는 짝수입니다. (충분) 짝수 차수에서 시작해 쓰지 않은 변을 따라가면 출발점에서만 막히므로 회로가 생기고, 빠진 변이 있으면 그 회로 위의 꼭짓점에서 다시 회로를 만들어 끼워 넣습니다. □

쾨니히스베르크의 그래프는 꼭짓점 4개의 차수가 $5, 3, 3, 3$으로 모두 홀수이므로 오일러 경로조차 없습니다.

한편 모든 꼭짓점(vertex)을 한 번씩 지나는 해밀턴 회로는 비슷해 보이지만 이렇게 간단한 판정법이 알려져 있지 않고, 계산이 매우 어려운 문제로 여겨집니다.

11.5 이분 그래프

정의 11.11. 꼭짓점을 두 무리로 나눠, 모든 변이 서로 다른 무리를 잇게 할 수 있으면 이분 그래프(bipartite graph)입니다.

정리 11.12. 그래프가 이분 그래프일 필요충분조건은 길이가 홀수인 회로가 없는 것입니다.

증명 (필요). 회로를 따라가면 무리가 번갈아 바뀌므로, 제자리로 돌아오려면 짝수 번 움직여야 합니다. □

$C_n$은 $n$이 짝수일 때만 이분 그래프이고, $K_3$은 이분 그래프가 아닙니다.

11.6 인접행렬과 경로의 수

정의 11.13. 꼭짓점이 $v_1, \dots, v_n$인 그래프의 인접행렬(adjacency matrix) $A$는 $v_i$와 $v_j$가 인접하면 $A_{ij} = 1$, 아니면 0인 $n \times n$ 행렬입니다. 방향 없는 그래프에서 $A$는 대칭입니다.

정리 11.14. $(A^k)_{ij}$는 $v_i$에서 $v_j$로 가는 길이 $k$인 보행의 수입니다.

증명. 귀납법. $k = 1$은 정의입니다. $(A^{k+1})_{ij} = \sum_l (A^k)_{il} A_{lj}$는 “$v_l$까지 길이 $k$로 가고 마지막에 $v_l \to v_j$”인 보행을 $l$마다 센 것입니다. □

예제 11.15. 삼각형 $K_3$의 인접행렬 $A = \begin{bmatrix} 0&1&1\\1&0&1\\1&1&0 \end{bmatrix}$에서 $A^2 = \begin{bmatrix} 2&1&1\\1&2&1\\1&1&2 \end{bmatrix}$입니다. 대각성분 2는 “이웃에 갔다 돌아오는” 길이 2인 보행 2개입니다. $\operatorname{tr}(A^3)/6$은 삼각형(길이 3인 회로)의 수로, $K_3$에서는 1입니다.

선형대수 31장에서는 인접행렬과 라플라시안의 고윳값으로 그래프의 연결 구조를 읽습니다.

11.7 평면 그래프

정의 11.16. 변이 서로 교차하지 않게 평면에 그릴 수 있는 그래프를 평면 그래프(planar graph)라 합니다. 그렇게 그렸을 때 평면이 나뉘는 영역을 면이라 합니다(바깥 영역 포함).

정리 11.17 (오일러 공식). 연결된 평면 그래프의 꼭짓점 수 $v$, 변 수 $e$, 면 수 $f$는 $v - e + f = 2$를 만족합니다.

증명 개요. 변의 수에 대한 귀납법. 트리(12강)이면 $e = v - 1$, $f = 1$이므로 성립합니다. 회로가 있으면 회로 위의 변 하나를 지울 때 면이 하나 줄고 변이 하나 주므로 $v - e + f$가 그대로입니다. □

정육면체의 꼭짓점·변·면은 $8 - 12 + 6 = 2$입니다. 오일러 공식으로 $K_5$와 $K_{3,3}$이 평면 그래프가 아님을 보일 수 있습니다.

쓰이는 곳. 그래프 신경망(GNN), 소셜 네트워크 분석, 경로 탐색(지도 앱), 페이지랭크, 회로 설계가 그래프의 언어로 쓰입니다. 인접행렬의 거듭제곱과 고윳값은 선형대수 31장의 스펙트럴 방법으로 이어집니다.

11.8 이 장의 요약

• 악수 정리 $\sum \deg v = 2|E|$, 홀수 차수 꼭짓점은 짝수 개.
• 오일러 회로 ⟺ 연결 + 모든 차수가 짝수.
• 이분 ⟺ 홀수 회로가 없음. $(A^k)_{ij}$ = 길이 $k$ 보행의 수. $v - e + f = 2$.

문제

15
12
7
20

2,3,4

8

7

2