본문 바로가기

그래프의 모델과 표현

네 정점짜리 그래프 하나를 그려 차수를 세고, 차수의 합이 간선 수의 두 배인 이유를 증명합니다. 같은 그래프를 인접 목록과 인접 행렬로 적고, 보행·트레일·경로·사이클, 연결 성분, 완전 그래프와 이분 그래프를 정의로 구별합니다.

친구 관계, 도시 사이의 도로, 작업 사이의 선후 관계는 모두 대상과 그 사이의 연결로 나타낼 수 있습니다. 대상과 연결만 남기고 나머지를 지운 모델이 그래프입니다. 관계의 표현과 성질에서 관계를 화살표 그림으로 그렸는데, 그 그림이 방향이 있는 그래프입니다.

이 글을 읽고 나면 다음을 할 수 있습니다.

  • 간선 목록으로 주어진 그래프의 차수를 세고, 인접 목록과 인접 행렬로 옮겨 적습니다.
  • 차수의 합이 간선 수의 두 배임을 증명하고, 이것으로 있을 수 없는 그래프를 가려냅니다.
  • 보행·트레일·경로·사이클을 정의로 구별하고 연결 성분을 찾습니다.

종이와 연필을 준비하세요. 이 글에서 그리는 네 정점 그래프는 이 장의 네 글이 모두 쓰고, 장 실습에서 다시 모읍니다. 코드는 교재 첫 쪽의 안내대로 lesson.py에 저장해 python lesson.py로 실행합니다.

선택 과정인 7장 행렬 실습을 했다면 표와 연결을 함께 떠올려 보세요. 그 실습을 건너뛰었어도 여기서 그래프의 용어부터 시작할 수 있습니다.

네 정점 그래프를 그려 보기

종이에 점 네 개를 찍고 A, B, C, D라고 이름을 붙입니다. A와 B, A와 C, B와 C, C와 D를 선으로 잇습니다. 이것이 그래프입니다. 그래프 G=(V,E)G=(V,E)는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 이루어지며, 방금 그린 그림은 V={A,B,C,D}V=\{A,B,C,D\}이고 간선이 AB, AC, BC, CD인 그래프입니다. 점을 어디에 찍었는지, 선이 곧은지 굽었는지는 그래프에 들어 있지 않습니다. 어느 정점끼리 이어졌는지만 남습니다.

간선에는 두 종류가 있습니다. 무방향 그래프(undirected graph)의 간선은 순서 없는 두 정점의 쌍이라서 A—B는 양쪽으로 모두 이동할 수 있다는 뜻입니다. 방향 그래프(directed graph)의 간선은 순서쌍이라서 A→B와 B→A가 서로 다른 간선입니다. 간선에 거리나 시간 같은 수를 붙이면 그 수를 가중치(weight)라고 합니다.

한 정점에서 자기 자신으로 가는 간선을 자기 루프(loop), 같은 두 정점 사이에 여러 개 있는 간선을 다중 간선(multiple edge)이라고 합니다. 둘 다 없는 무방향 그래프가 단순 그래프(simple graph)이고, 이 장에서는 따로 말하지 않으면 단순 그래프를 다룹니다. 방금 그린 그래프도 단순 그래프입니다.

이산수학 · 연결과 계산

한 간선을 양 끝 정점에서 읽습니다

무방향 그래프의 간선은 AB, AC, BC, CD 네 개입니다. 차수는 A=2, B=2, C=3, D=1입니다.

한 간선을 양 끝 정점에서 읽습니다무방향 그래프의 간선은 AB, AC, BC, CD 네 개입니다. 차수는 A=2, B=2, C=3, D=1입니다.ABCD
  • 선: 무방향 간선

굽은 선도 AC 한 간선입니다. 화살촉이 없으므로 양방향으로 이동할 수 있습니다. C에 연결된 선은 AC·BC·CD 세 개입니다.

도표는 같은 그래프를 그린 것입니다. A와 C를 잇는 선이 굽어 있어도 간선 하나이고, 화살촉이 없으므로 무방향 간선입니다. 도표에 적힌 차수는 다음 절에서 셉니다.

차수를 세면 보이는 것

무방향 그래프에서 정점 v에 붙은 간선의 개수를 v의 차수(degree)라 하고 deg⁡(v)\deg(v)로 씁니다. 예제에서 차수는 A가 2, B가 2, C가 3, D가 1입니다. 모두 더하면 8이고, 간선은 4개입니다.

여기에 간선 BD를 하나 더 그리면 차수의 합은 얼마가 될까요? 다시 세기 전에 먼저 예상해 보세요.

결과 확인하기

10입니다. B와 D의 차수가 1씩 늘어 A 2, B 3, C 3, D 2가 됩니다. 간선은 5개입니다. 간선 하나를 그릴 때마다 양 끝의 두 정점에서 차수가 1씩 늘므로, 합은 언제나 2씩 늡니다.

두 번 모두 차수의 합이 간선 수의 두 배였습니다. 이것은 이 장의 유한 단순 무방향 그래프에서 항상 성립합니다. 곧 ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|입니다. 증명은 "정점 v가 간선 e의 끝점이다"를 만족하는 쌍 (v, e)를 두 가지 방법으로 세는 것입니다. 정점마다 세면 v에서 deg⁡(v)\deg(v)개씩이므로 차수의 합이 됩니다. 간선마다 세면 간선 하나에 끝점이 두 개이므로 2∣E∣2|E|가 됩니다. 같은 것을 센 두 값이므로 같습니다. 모임에서 악수 한 번이 두 사람에게서 세어지는 것과 같은 이유라서 악수 정리(handshake lemma)라고 부릅니다.

여기서 따라 나오는 사실이 있습니다. 차수가 홀수인 정점은 언제나 짝수 개입니다. 차수의 합 2∣E∣2|E|가 짝수이고 짝수 차수들의 합도 짝수이므로, 홀수 차수들의 합도 짝수여야 합니다. 홀수를 홀수 개 더하면 홀수가 되므로 홀수 차수인 정점은 짝수 개일 수밖에 없습니다. 예제에서는 C와 D의 두 개입니다.

방향 그래프에서는 들어오는 간선의 수인 진입 차수(in-degree)와 나가는 간선의 수인 진출 차수(out-degree)를 따로 셉니다. 간선마다 나가는 끝과 들어오는 끝이 하나씩이므로 두 합이 모두 ∣E∣|E|입니다.

인접 목록과 인접 행렬로 적기

컴퓨터에 그래프를 저장하는 방법은 대표적으로 두 가지입니다. 인접 목록(adjacency list)은 정점마다 이웃의 목록을 적습니다. 간선 목록에서 정점을 모으고 인접 목록을 만들어 봅니다.

lesson.py
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]

found = set()
for edge in edges:
    for v in edge:
        found.add(v)
print(sorted(found))
print(sorted({v for edge in edges for v in edge}))

vertices = sorted(found)
adjacency = {v: [] for v in vertices}
for u, v in edges:
    adjacency[u].append(v)
    adjacency[v].append(u)
print(adjacency)
print(sum(len(adjacency[v]) for v in vertices), 2 * len(edges))
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'D']
{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['C']}
8 8

처음 두 줄은 같은 일을 두 가지로 쓴 것입니다. {v for edge in edges for v in edge}는 위의 두 겹 for문을 한 줄로 줄인 컴프리헨션이고, for를 적는 순서가 풀어 쓴 것과 같습니다. 이 장의 코드는 이 표기를 자주 쓰므로, 낯설면 이렇게 풀어서 읽으세요. 무방향 간선 하나를 양쪽 정점의 목록에 모두 적으므로, 목록의 길이를 다 더한 값은 차수의 합이고 간선 수의 두 배인 8입니다.

인접 행렬(adjacency matrix)은 i번째 정점과 j번째 정점이 이어져 있으면 i행 j열에 1을 적습니다.

lesson.py
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
vertices = ["A", "B", "C", "D"]
index = {"A": 0, "B": 1, "C": 2, "D": 3}
matrix = [[0, 0, 0, 0] for _ in vertices]
for u, v in edges:
    matrix[index[u]][index[v]] = 1
    matrix[index[v]][index[u]] = 1
for v, row in zip(vertices, matrix):
    print(v, row, sum(row))
A [0, 1, 1, 0] 2
B [1, 0, 1, 0] 2
C [1, 1, 0, 1] 3
D [0, 0, 1, 0] 1

무방향 그래프의 인접 행렬은 i행 j열과 j행 i열이 같은 대칭 행렬이고, 각 행의 합이 그 정점의 차수입니다. 정점이 n개, 간선이 m개일 때 인접 행렬은 두 정점이 이어졌는지를 한 칸만 보고 알 수 있지만 언제나 n2n^2칸을 씁니다. 인접 목록은 n+mn+m에 비례하는 공간만 쓰고 한 정점의 이웃을 바로 훑을 수 있어서 간선이 적은 그래프에 유리합니다. 코드에서 두 표현을 다루는 방법은 자료구조·알고리즘 교재의 정점·간선·인접 목록과 인접 행렬에서 더 자세히 다룹니다.

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

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

예제 그래프에서 D, C, A, B, C는 보행, 트레일, 경로 가운데 어디까지 해당할까요?

결과 확인하기

트레일까지입니다. 지나간 간선은 DC, CA, AB, BC로 모두 다르므로 트레일입니다. 그런데 정점 C를 두 번 지났으므로 경로는 아닙니다. 이 트레일은 네 간선을 모두 한 번씩 썼는데, 이런 트레일은 다음 글의 주제입니다.

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

연결과 연결 성분

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

"두 정점이 연결되어 있다"는 관계는 동치관계입니다. 모든 정점은 길이 0인 경로로 자기 자신과 연결되고, 경로를 거꾸로 따라가면 반대 방향의 경로가 되며, 두 경로를 이어 붙이면 보행이 되기 때문입니다. 그래서 이 관계의 동치류가 정점 집합을 분할하고, 각 동치류와 그 안의 간선을 연결 성분(connected component)이라고 합니다. 예제 그래프는 연결 성분이 하나이고, 간선 CD를 지우면 A, B, C의 성분과 D 혼자인 성분으로 나뉩니다.

방향 그래프에서는 모든 정점 쌍 u, v에 대해 u에서 v로도, v에서 u로도 갈 수 있으면 강하게 연결(strongly connected)되어 있다고 하고, 방향을 지운 그래프가 연결 그래프이면 약하게 연결(weakly connected)되어 있다고 합니다.

완전 그래프와 이분 그래프

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

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

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

정리

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

연습 문제

1. 간선 하나를 지우면

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

해설 보기

차수는 A가 2, B가 1, C가 2, D가 1이고 합은 6으로, 남은 간선 3개의 두 배입니다. 남은 간선 AB, AC, CD로 B—A—C—D가 이어지므로 여전히 연결 그래프입니다. 하나뿐이던 사이클 A, B, C, A가 사라져 사이클은 없습니다. 연결되어 있고 사이클이 없는 그래프는 다음 장에서 다룰 트리입니다.

2. 닫힌 보행과 사이클

다음 세 가지는 각각 사이클인가요? 정의의 어느 조건으로 판정했는지도 쓰세요. 간선 AB 하나인 단순 무방향 그래프의 A, B, A. 예제 그래프의 A, B, C, A. 방향 간선 A→B와 B→A를 가진 방향 그래프의 A, B, A.

해설 보기

첫째는 같은 간선 AB를 두 번 썼으므로 트레일이 아니고, 따라서 사이클이 아닙니다. 둘째는 서로 다른 세 간선 AB, BC, CA를 쓰고 중간 정점 B, C가 반복되지 않으므로 길이 3인 사이클입니다. 셋째는 서로 다른 두 간선 A→B와 B→A를 썼으므로 길이 2인 방향 사이클입니다. 지나간 정점의 모양이 아니라 실제로 쓴 간선이 반복되었는지를 보아야 합니다.

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

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

해설 보기

정점 7개의 차수가 모두 3이면 차수의 합이 21로 홀수입니다. 차수의 합은 간선 수의 두 배라 짝수여야 하므로 이런 그래프는 없습니다. 정점이 8개이면 합이 24라 간선이 12개여야 하고, 정육면체의 꼭짓점과 모서리가 실제로 이런 그래프입니다. 합이 짝수라는 것은 필요조건일 뿐이므로, 있다고 말하려면 이처럼 예를 하나 보여야 합니다.

4. 홀수 차수인 정점 찾기

인접 목록을 받아 차수가 홀수인 정점의 리스트를 돌려주는 함수 odd_vertices를 쓰세요. 예제 그래프와, 중심 O에 A, B, C가 하나씩 이어진 별 모양 그래프에서 실행해 결과의 길이가 짝수인지 확인합니다. 이 함수는 다음 글에서 다시 씁니다.

해설 보기
lesson.py
def odd_vertices(adjacency):
    odd = []
    for v in adjacency:
        if len(adjacency[v]) % 2 == 1:
            odd.append(v)
    return odd


example = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C"]}
star = {"O": ["A", "B", "C"], "A": ["O"], "B": ["O"], "C": ["O"]}
print(odd_vertices(example))
print(odd_vertices(star))
['C', 'D']
['O', 'A', 'B', 'C']

이웃 목록의 길이가 차수입니다. 결과는 2개와 4개로 모두 짝수 개입니다.

5. 홀수 차수인 두 정점은 이어져 있다

어떤 그래프에서 차수가 홀수인 정점이 u와 v 두 개뿐이라고 합시다. u와 v가 같은 연결 성분에 있음을 증명하세요.

해설 보기

u가 들어 있는 연결 성분을 H라고 합니다. H는 그 자체로 하나의 그래프이고, H의 정점에 붙은 간선은 모두 H 안에 있으므로 H에서의 차수는 원래 그래프에서의 차수와 같습니다. 악수 정리에 따라 H에서 차수가 홀수인 정점은 짝수 개입니다. u가 그런 정점이므로 H에는 홀수 차수인 정점이 u 말고 적어도 하나 더 있습니다. 전체 그래프에서 홀수 차수인 정점은 u와 v뿐이므로 그 정점은 v입니다. 따라서 v는 u와 같은 연결 성분에 있습니다.

꼭 있어야 하는 줄은 다음과 같습니다.

  • u의 연결 성분만 떼어 하나의 그래프로 본다는 줄.
  • 성분 안에서의 차수가 원래 차수와 같다는 확인.
  • 그 성분에 악수 정리를 써서 홀수 차수인 정점이 짝수 개라고 한 줄.
  • 남은 홀수 차수 정점이 v뿐이라 v가 그 성분에 있다는 마무리.

6. 틀린 증명 고치기

다음 주장과 증명에서 잘못된 줄을 찾고, 주장이 거짓임을 보이세요. 그리고 이 증명의 앞부분이 실제로 보여 주는 것이 무엇인지 쓰세요.

주장: 모든 정점의 차수가 2 이상인 그래프는 연결 그래프다.
증명: 아무 정점에서 출발해 걷는다. 어느 정점에 들어서든 차수가 2 이상이므로
들어온 간선 말고 나갈 간선이 있다. 따라서 걸음은 멈추지 않는다.
멈추지 않고 걸으므로 모든 정점을 지나고, 그래프는 연결되어 있다.
해설 보기

잘못된 줄은 마지막 줄입니다. 걸음이 멈추지 않는다는 것에서 모든 정점을 지난다는 것은 나오지 않습니다. 같은 곳을 돌기만 해도 걸음은 멈추지 않습니다. 반례는 서로 떨어진 두 삼각형 A, B, C와 D, E, F입니다. 모든 정점의 차수가 2이지만 A에서 D로 가는 경로가 없습니다.

앞의 세 줄이 보여 주는 것은 사이클이 있다는 사실입니다. 정점의 수가 유한하므로 멈추지 않는 걸음은 언젠가 이미 지난 정점에 다시 들어서고, 처음으로 그렇게 되는 순간 그 정점에서 그 정점까지의 구간이 사이클입니다. 방금 들어온 간선으로 되돌아가지 않았으므로 이 구간의 길이는 3 이상입니다.

꼭 있어야 하는 줄은 다음과 같습니다.

  • "멈추지 않는다"에서 "모든 정점을 지난다"로 넘어간 줄이 근거가 없다는 지적.
  • 반례 하나와, 그 반례가 가정을 만족하고 결론을 어긴다는 확인.
  • 고친 주장: 모든 정점의 차수가 2 이상인 유한 그래프에는 사이클이 있다.

7. 도전: 원 모양 그래프는 언제 이분 그래프인가

정점 v1,v2,…,vnv_1,v_2,\dots,v_n(n ≥ 3)을 차례로 잇고 vnv_n과 v1v_1도 이은 그래프를 CnC_n이라고 합니다. C4C_4와 C5C_5를 그려 두 쪽으로 나누어 본 뒤, CnC_n이 이분 그래프일 필요충분조건이 "n이 짝수"임을 증명하세요.

해설 보기

C4C_4는 {v1,v3}\{v_1,v_3\}과 {v2,v4}\{v_2,v_4\}로 나누면 네 간선이 모두 두 쪽을 잇습니다. C5C_5는 어떻게 나누어도 같은 쪽끼리 잇는 간선이 남습니다.

n이 홀수이면 CnC_n 자체가 길이 n인 홀수 사이클입니다. 이분 그래프에는 홀수 길이의 사이클이 없으므로 CnC_n은 이분 그래프가 아닙니다. 이것은 "이분 그래프이면 n이 짝수"의 대우입니다.

n이 짝수이면 번호가 홀수인 정점을 X, 짝수인 정점을 Y로 둡니다. 간선 vivi+1v_iv_{i+1}(1 ≤ i ≤ n − 1)은 번호가 1 차이 나므로 홀짝이 다른 두 정점을 잇습니다. 남은 간선 vnv1v_nv_1은 짝수 번호 n과 홀수 번호 1을 잇습니다. 모든 간선이 X와 Y를 이으므로 CnC_n은 이분 그래프입니다.

꼭 있어야 하는 줄은 다음과 같습니다.

  • 필요충분조건이므로 두 방향을 따로 증명한다는 것.
  • 홀수 쪽: CnC_n 자체가 홀수 사이클이라는 줄과, 본문의 "이분 그래프에는 홀수 사이클이 없다"를 쓴 자리.
  • 짝수 쪽: X와 Y를 구체적으로 정한 줄.
  • 마지막 간선 vnv1v_nv_1을 따로 확인한 줄. 이 줄이 빠지면 n이 홀수일 때도 같은 논증이 통하는 것처럼 보인다.

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