그래프의 모델과 표현

친구 관계, 도시 사이의 도로, 작업 사이의 선후 관계는 모두 대상과 그 사이의 연결로 나타낼 수 있습니다. 대상과 연결만 남기고 나머지를 지운 모델이 그래프입니다. 관계의 표현과 성질에서 관계를 화살표 그림으로 그렸는데, 그 그림이 바로 방향 그래프입니다. 이 글에서는 그래프의 기본 용어를 정의하고, 같은 그래프를 여러 방법으로 적으며, 모든 그래프에 성립하는 몇 가지 사실을 증명합니다.

정점과 간선

그래프 $G=(V,E)$는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 이루어집니다. 정점은 노드(node)라고도 부릅니다. 무방향 그래프(undirected graph)의 간선은 순서 없는 두 정점의 쌍이라서 A—B는 A에서 B로도, B에서 A로도 이동할 수 있다는 뜻입니다. 방향 그래프(directed graph)의 간선은 순서쌍이라서 A→B와 B→A가 서로 다른 간선입니다. 간선에 거리나 시간 같은 수를 붙이면 그 수를 가중치(weight)라고 합니다.

모델을 만들 때는 무엇을 허용할지도 먼저 정해야 합니다. 한 정점에서 자기 자신으로 가는 간선을 자기 루프(loop)라 하고, 같은 두 정점 사이에 간선이 여러 개 있으면 다중 간선(multiple edge)이라고 합니다. 둘 다 없는 무방향 그래프를 단순 그래프(simple graph)라 하며, 이 장에서는 따로 말하지 않으면 단순 그래프를 다룹니다. 양방향 도로를 무방향 간선 하나로 적을지 방향 간선 두 개로 적을지도 하나로 정해 두어야 같은 그래프를 두고 서로 다른 답을 내지 않습니다.

차수의 합은 간선 수의 두 배다

무방향 그래프에서 정점 v에 붙은 간선의 개수를 v의 차수(degree)라 하고 $\deg(v)$로 씁니다. 자기 루프를 허용할 때는 루프 하나가 차수에 2를 더한다고 약속합니다. 방향 그래프에서는 들어오는 간선의 수인 진입 차수(in-degree)와 나가는 간선의 수인 진출 차수(out-degree)를 따로 셉니다.

어떤 무방향 그래프에서든 $\sum_{v\in V}\deg(v)=2|E|$입니다. "정점 v가 간선 e의 끝점이다"를 만족하는 쌍 (v, e)를 두 가지 방법으로 세면 증명됩니다. 정점마다 세면 정점 v에서 $\deg(v)$개씩이므로 차수의 합이 되고, 간선마다 세면 간선 하나에 끝점이 두 개이므로 $2|E|$가 됩니다. 같은 것을 센 두 값이므로 같습니다. 이 사실을 악수 정리(handshake lemma)라고 부르는데, 모임에서 사람들이 악수한 횟수를 사람마다 더하면 악수 한 번이 두 사람에게서 세어지는 것과 같은 이유입니다.

여기서 바로 따라 나오는 사실이 있습니다. 차수가 홀수인 정점은 언제나 짝수 개입니다. 차수의 합 $2|E|$는 짝수이고 짝수 차수들의 합도 짝수이므로, 홀수 차수들의 합도 짝수여야 합니다. 홀수를 홀수 개 더하면 홀수가 되므로, 홀수 차수인 정점의 개수는 짝수일 수밖에 없습니다. 방향 그래프에서는 간선마다 나가는 끝과 들어오는 끝이 하나씩이므로 진입 차수의 합과 진출 차수의 합이 모두 $|E|$입니다.

네 정점 예제를 두 가지 표로 적기

$V=\{A,B,C,D\}$이고 간선이 AB, AC, BC, CD인 단순 무방향 그래프를 예로 씁니다. 차수는 A가 2, B가 2, C가 3, D가 1이고, 합 8은 간선 수 4의 두 배입니다. 홀수 차수인 정점은 C와 D의 두 개입니다.

컴퓨터에 그래프를 저장하는 대표적인 방법은 두 가지입니다. 인접 목록(adjacency list)은 정점마다 이웃의 목록을 적고, 인접 행렬(adjacency matrix)은 i번째 정점과 j번째 정점이 이어져 있으면 i행 j열에 1을 적습니다. 간선 목록에서 두 표를 만들고 차수의 합을 확인하는 코드는 다음과 같습니다.

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
vertices = sorted({v for edge in edges for v in edge})
adjacency = {v: [] for v in vertices}
for u, v in edges:
    adjacency[u].append(v)
    adjacency[v].append(u)
index = {v: i for i, v in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in vertices]
for u, v in edges:
    matrix[index[u]][index[v]] = matrix[index[v]][index[u]] = 1
print(adjacency)
for v, row in zip(vertices, matrix):
    print(v, row, sum(row))
print(sum(len(neighbors) for neighbors in adjacency.values()), 2 * len(edges))

{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}
A [0, 1, 1, 0] 2
B [1, 0, 1, 0] 2
C [1, 1, 0, 1] 3
D [0, 0, 1, 0] 1
8 8

무방향 간선 하나를 양쪽 정점의 목록에 모두 적으므로, 인접 목록의 길이를 다 더하면 차수의 합이 되어 간선 수의 두 배인 8이 나옵니다. 인접 행렬은 i행 j열과 j행 i열이 같은 대칭 행렬이고, 각 행의 합이 그 정점의 차수입니다. 방향 그래프라면 간선을 한쪽 목록에만 적으므로 행렬이 대칭이 아닐 수 있습니다.

정점이 n개, 간선이 m개일 때 인접 행렬은 두 정점이 이어졌는지를 한 칸만 보고 알 수 있지만 언제나 $n^2$칸을 씁니다. 인접 목록은 $n+m$에 비례하는 공간만 쓰고 한 정점의 이웃을 바로 훑을 수 있어서, 간선이 적은 그래프에 유리합니다. 가중치를 행렬에 적을 때는 간선이 없다는 표시를 가중치 0과 다른 값으로 해야 합니다. 둘을 같은 0으로 적으면 비용이 0인 간선이 사라집니다. 두 표현을 코드에서 다루는 방법은 자료구조·알고리즘 교재의 정점·간선·인접 목록과 인접 행렬에서 더 자세히 다룹니다.

보행·트레일·경로·사이클

간선을 따라 이동하며 지나는 정점의 나열을 보행(walk)이라 하고, 지나간 간선의 개수를 보행의 길이라고 합니다. 보행에서는 같은 정점이나 같은 간선을 다시 지나도 됩니다. 같은 간선을 다시 지나지 않는 보행은 트레일(trail), 같은 정점을 다시 지나지 않는 보행은 경로(path) 또는 단순 경로(simple path)라고 합니다. 정점이 반복되지 않으면 간선도 반복될 수 없으므로 모든 경로는 트레일입니다. 출발점으로 돌아오는 보행은 닫힌 보행(closed walk)이라고 합니다.

사이클(cycle)은 길이가 1 이상인 닫힌 트레일 가운데, 출발점이 마지막에 다시 나오는 것을 빼면 정점이 반복되지 않는 것입니다. 단순 무방향 그래프에서 사이클은 간선이 적어도 세 개 필요합니다. 간선 AB 하나만 있는 그래프에서 A, B, A는 닫힌 보행이지만 같은 간선 AB를 두 번 썼으므로 사이클이 아닙니다. 반면 예제의 A, B, C, A는 서로 다른 세 간선으로 돌아오므로 사이클입니다.

길이가 3 이상이라는 조건은 단순 무방향 그래프에만 해당합니다. 자기 루프를 허용하면 루프 하나가 길이 1인 사이클이고, 다중 간선을 허용하면 한 간선으로 갔다가 다른 간선으로 돌아오는 길이 2인 사이클이 생깁니다. 방향 그래프에서는 A→B와 B→A가 서로 다른 간선이므로 둘 다 있으면 길이 2인 사이클입니다. 이 구분은 트리를 "사이클이 없는 연결 그래프"로 정의할 때 중요해집니다.

연결과 연결 성분

무방향 그래프에서 두 정점 사이에 경로가 있으면 두 정점이 연결되어 있다고 하고, 모든 정점 쌍이 연결되어 있으면 연결 그래프(connected graph)라고 합니다. 보행이 있으면 경로도 있습니다. 보행에 같은 정점이 두 번 나오면 그 사이의 구간을 빼도 여전히 같은 두 정점을 잇는 보행이 되고, 이것을 반복하면 반복되는 정점이 없어지기 때문입니다.

"두 정점이 연결되어 있다"는 관계는 동치관계입니다. 모든 정점은 길이 0인 경로로 자기 자신과 연결되고, u에서 v로 가는 경로를 거꾸로 따라가면 v에서 u로 가는 경로가 되며, u에서 v, v에서 w로 가는 경로를 이어 붙이면 u에서 w로 가는 보행이 되기 때문입니다. 그래서 이 관계의 동치류가 정점 집합을 분할하고, 각 동치류와 그 안의 간선을 연결 성분(connected component)이라고 합니다.

방향 그래프에서는 방향 때문에 연결을 두 가지로 나눕니다. 모든 정점 쌍 u, v에 대해 u에서 v로도, v에서 u로도 갈 수 있으면 강하게 연결(strongly connected)되어 있다고 합니다. 간선의 방향을 지운 무방향 그래프가 연결 그래프이면 약하게 연결(weakly connected)되어 있다고 합니다. A→B 하나만 있는 그래프는 약하게 연결되어 있지만, B에서 A로 갈 수 없으므로 강하게 연결되어 있지는 않습니다.

완전 그래프와 이분 그래프

서로 다른 모든 정점 쌍이 간선으로 이어진 단순 그래프를 완전 그래프(complete graph)라 하고, 정점이 n개이면 $K_n$으로 씁니다. $K_n$에서 모든 정점의 차수는 n − 1이므로 악수 정리에 따라 $2|E|=n(n-1)$이고, 간선은 $n(n-1)/2$개입니다. 정점 n개인 단순 그래프가 가질 수 있는 간선의 최대 개수이기도 합니다.

정점을 두 집합 X와 Y로 나누어 모든 간선이 X의 정점과 Y의 정점을 잇게 할 수 있으면 이분 그래프(bipartite graph)라고 합니다. 학생과 수강 과목처럼 두 종류의 대상 사이의 연결이 이런 모양입니다. X의 m개 정점과 Y의 n개 정점을 모두 이은 그래프를 완전 이분 그래프 $K_{m,n}$이라 하며, 간선은 mn개입니다.

이분 그래프에는 길이가 홀수인 사이클이 없습니다. 간선을 하나 지날 때마다 X와 Y를 오가므로, 출발한 쪽으로 돌아오려면 간선을 짝수 번 지나야 하기 때문입니다. 그래서 삼각형이 들어 있는 예제 그래프는 이분 그래프가 아닙니다. 거꾸로 홀수 길이의 사이클이 없는 그래프는 언제나 이분 그래프라는 것도 증명할 수 있으며, 깊이 우선 탐색과 너비 우선 탐색으로 정점을 두 쪽으로 나누어 확인할 수 있습니다.

더 깊이: 평면 그래프와 오일러 공식

간선이 서로 교차하지 않게 평면에 그릴 수 있는 그래프를 평면 그래프(planar graph)라고 합니다. 어떤 그림에서 간선이 교차한다고 해서 평면 그래프가 아니라고 판단하면 안 됩니다. 다른 배치로 교차 없이 그릴 수 있는지가 기준입니다. 연결 평면 그래프를 교차 없이 그리면 정점 수 v, 간선 수 e, 간선이 나누는 영역인 면(face)의 수 f 사이에 $v-e+f=2$가 성립하는데, 이것을 오일러 공식(Euler's formula)이라고 합니다. 그림 바깥으로 끝없이 이어지는 바깥 면도 하나로 셉니다.

사각형 ABCD의 둘레 AB, BC, CD, DA에 대각선 AC를 안쪽으로 그리면 v = 4, e = 5이고, 면은 삼각형 ABC, 삼각형 ACD, 바깥 면의 3개라 4 − 5 + 3 = 2입니다. AC를 지우면 안쪽의 두 면이 하나로 합쳐져 e와 f가 함께 1씩 줄고, 4 − 4 + 2 = 2로 값이 그대로입니다. 일반적인 증명도 같은 방법을 씁니다. 사이클 위의 간선을 하나 지우면 연결은 유지되면서 그 간선 양쪽의 두 면이 합쳐지므로, e와 f가 함께 1씩 줄어 $v-e+f$가 변하지 않습니다. 사이클이 없어질 때까지 반복하면 트리가 남는데, 트리는 e = v − 1이고 면이 바깥 면 하나뿐이므로 $v-(v-1)+1=2$입니다. 연결 성분이 c개이면 같은 방법으로 $v-e+f=1+c$를 얻습니다.

이 공식으로 평면 그래프가 아님을 증명할 수 있습니다. 정점이 3개 이상인 단순 연결 평면 그래프에서 면마다 경계를 따라 간선을 세면 적어도 3이고, 모든 면에서 센 값을 더하면 간선마다 양쪽에서 한 번씩 세어 2e입니다. 그래서 $3f\le2e$이고, 오일러 공식의 $f=2-v+e$를 넣어 정리하면 $e\le3v-6$입니다. $K_5$는 v = 5, e = 10인데 $3\cdot5-6=9$보다 간선이 많으므로, 어떻게 그려도 교차를 없앨 수 없습니다.

정리

• 그래프는 정점의 집합과 간선의 집합이며, 무방향 간선은 순서 없는 쌍, 방향 간선은 순서쌍입니다. 자기 루프와 다중 간선이 없는 무방향 그래프가 단순 그래프입니다.
• 차수의 합은 간선 수의 두 배이고, 그래서 홀수 차수인 정점은 짝수 개입니다. 방향 그래프에서는 진입 차수의 합과 진출 차수의 합이 모두 간선 수입니다.
• 인접 목록은 $n+m$에 비례하는 공간을, 인접 행렬은 $n^2$칸을 쓰며, 무방향 그래프의 인접 행렬은 대칭입니다.
• 보행은 반복을 허용하고, 트레일은 간선을, 경로는 정점을 반복하지 않습니다. 단순 무방향 그래프의 사이클은 간선이 3개 이상 필요합니다.
• "연결되어 있다"는 동치관계이고 그 동치류가 연결 성분입니다. 방향 그래프는 강한 연결과 약한 연결을 구분합니다.
• $K_n$의 간선은 $n(n-1)/2$개, $K_{m,n}$의 간선은 mn개이며, 이분 그래프에는 홀수 길이의 사이클이 없습니다.

연습 문제

1. 간선 하나를 지우면

예제 그래프에서 간선 BC를 지우면 차수, 연결 여부, 사이클은 어떻게 바뀌나요?

2. 차수의 합으로 판정하기

모든 정점의 차수가 3인 정점 7개짜리 그래프가 있을 수 있나요? 정점이 8개라면 어떤가요?

3. 닫힌 보행과 사이클

간선 AB 하나인 단순 무방향 그래프의 A, B, A, 삼각형의 A, B, C, A, 방향 간선 A→B와 B→A를 가진 방향 그래프의 A, B, A는 각각 사이클인가요?

4. 선택 심화: $K_{3,3}$은 평면 그래프인가

$K_{3,3}$을 교차 없이 그릴 수 있는지 오일러 공식으로 판정하세요.

그래프 문제가 헷갈리면 정점과 간선이 각각 무엇을 뜻하는지 한 문장으로 적어 보세요. 다음 글 오일러와 해밀턴 경로에서는 모든 간선을 한 번씩 지나는 길과 모든 정점을 한 번씩 지나는 길이 각각 언제 있는지 따집니다.