이산수학과 그래프 이론 입문

지하철 노선도, SNS의 친구 관계, 웹페이지 사이의 링크, 프로그램 사이의 의존성. 모양은 다르지만 모두 "무엇이 무엇과 연결돼 있다"는 구조예요. 이 연결을 점과 선으로 추상화한 것이 그래프예요. 그래프 하나만 잘 이해해도 길 찾기, 추천, 검색 순위, 네트워크 설계 같은 문제가 같은 언어로 보이기 시작해요.

이산수학이란

미적분이 매끄럽게 이어지는 연속적인 양을 다룬다면, 이산수학은 셀 수 있게 떨어져 있는 것들을 다뤄요. 정수, 집합, 논리, 경우의 수, 그래프가 모두 이산수학이에요. 컴퓨터는 0과 1로 된 떨어진 값만 다루니, 이산수학은 컴퓨터 과학의 모국어라고 할 수 있어요. 이 트랙의 앞선 강의들(논리, 집합, 조합, 증명)이 사실 모두 이산수학이었어요.

그래프의 기본 용어

그래프 $G = (V, E)$ 는 정점(꼭짓점, 노드)의 집합 $V$ 와 정점을 잇는 간선(에지)의 집합 $E$ 로 이뤄져요.

용어	뜻	예
무방향 그래프	간선에 방향이 없음	친구 관계(서로 친구)
방향 그래프	간선에 방향이 있음	팔로우, 웹 링크
가중치 그래프	간선에 값(거리, 비용)이 있음	도로와 거리
인접	간선으로 직접 이어짐	두 역이 한 정거장
차수	정점에 붙은 간선 수	친구 수
경로	간선을 따라 이어진 정점들의 나열	출발역에서 도착역까지
사이클	시작과 끝이 같은 경로	순환선
연결 그래프	모든 정점 쌍 사이에 경로가 있음	섬이 없는 도로망

악수 정리

파티에서 사람들이 악수를 했어요. 각 사람이 악수한 횟수를 모두 더하면, 전체 악수 횟수의 정확히 두 배예요. 악수 한 번에 두 사람의 횟수가 하나씩 늘어나니까요.

\sum_{v \in V} \deg(v) = 2|E|

여기서 재미있는 결론이 나와요. 차수의 합이 짝수이니, 차수가 홀수인 정점의 개수는 항상 짝수예요. "악수를 홀수 번 한 사람은 반드시 짝수 명이다." 간단한 세기로 의외의 사실을 증명하는 그래프 이론의 맛이에요.

트리: 사이클이 없는 연결

사이클이 없는 연결 그래프를 트리라고 해요. 폴더 구조, 회사 조직도, 가계도, HTML 문서의 구조가 모두 트리예요.

트리에는 깔끔한 성질이 있어요.

정점이 $n$ 개면 간선은 정확히 $n - 1$ 개예요.
아무 두 정점 사이의 경로가 딱 하나예요.
간선을 하나라도 빼면 끊어지고, 하나라도 더하면 사이클이 생겨요.

그래서 트리는 "가장 적은 연결로 모두를 잇는" 구조예요. 마을 몇 곳을 최소 비용의 도로로 모두 잇는 문제(최소 신장 트리)가 실제 네트워크 설계에 쓰여요.

그래프를 코드로 나타내기

인접 행렬

정점 $n$ 개를 $n \times n$ 표로 나타내고, $i$ 와 $j$ 가 이어져 있으면 1, 아니면 0을 적어요.

#       A  B  C  D
graph = [
    [0, 1, 1, 0],   # A는 B, C와 연결
    [1, 0, 0, 1],   # B는 A, D와 연결
    [1, 0, 0, 1],   # C는 A, D와 연결
    [0, 1, 1, 0],   # D는 B, C와 연결
]

두 정점이 이어졌는지 바로 확인할 수 있지만, 정점이 100만 개면 1조 칸이 필요해요. 실제 그래프는 대부분 연결이 드문드문해서 칸이 거의 0이라 낭비가 심해요.

인접 리스트

정점마다 이웃 목록만 적어요. 딕셔너리로 아주 자연스럽게 표현돼요.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

간선 수에 비례하는 공간만 써요. 실제 서비스의 그래프는 대부분 이 방식이에요.

연결 고리 인접 행렬은 선형대수의 행렬 그 자체예요. 행렬을 곱하면 "두 걸음에 갈 수 있는 경로의 수" 같은 것이 계산돼요. 그래프 신경망(GNN) 같은 AI 모델은 이 성질을 이용해 연결 구조를 학습해요.

그래프 탐색: 너비 우선과 깊이 우선

그래프의 모든 정점을 빠짐없이 방문하는 두 가지 기본 방법이 있어요.

너비 우선 탐색 (BFS)

가까운 정점부터 차례로, 물결이 퍼지듯 방문해요. 큐(먼저 넣은 것을 먼저 꺼내는 줄)를 써요.

from collections import deque

def bfs(graph, start):
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D']

BFS는 출발점에서 간선 수가 가장 적은 경로를 자연스럽게 찾아요. "몇 다리 건너면 아는 사이인가", "환승을 가장 적게 하는 길" 같은 문제에 써요.

깊이 우선 탐색 (DFS)

한 방향으로 끝까지 파고들었다가, 막히면 되돌아와 다른 길로 가요. 미로를 손으로 더듬으며 푸는 방식과 같아요. 재귀로 쓰면 아주 짧아요.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited

DFS는 사이클 찾기, 모든 경로 나열, 그리고 아래에서 볼 위상 정렬에 쓰여요.

두 탐색 모두 정점과 간선을 한 번씩만 보니 시간은 $O(|V| + |E|)$ 예요. 알고리즘 트랙의 트리와 그래프 강의에서 더 깊이 다뤄요.

최단 경로

가중치 그래프에서 가장 짧은 경로를 찾는 대표적인 방법이 다익스트라 알고리즘이에요. 아이디어는 이래요. 출발점에서 지금까지 확정된 가장 가까운 정점부터 하나씩 꺼내, 그 이웃들의 거리를 "이 정점을 거쳐 가면 더 짧아지는가"로 갱신해요. 지도 앱의 길 찾기가 이 생각을 바탕으로 해요. 단, 가중치가 음수인 간선이 있으면 쓸 수 없다는 조건이 있어요.

오일러 경로: 쾨니히스베르크의 다리

18세기 쾨니히스베르크에는 강 위에 다리 7개가 있었어요. 사람들은 "모든 다리를 정확히 한 번씩 건너는 산책길이 있을까?"를 궁금해했어요. 오일러는 땅을 정점으로, 다리를 간선으로 바꿔 생각했고, 이것이 그래프 이론의 시작이에요.

오일러의 답은 차수만 보면 된다는 거였어요.

모든 간선을 한 번씩 지나 제자리로 돌아오는 길: 모든 정점의 차수가 짝수일 때만 있어요.
한 번씩 지나는 길(돌아오지 않아도 됨): 차수가 홀수인 정점이 0개 또는 2개일 때만 있어요.

쾨니히스베르크는 네 땅의 차수가 모두 홀수라서 불가능했어요. 지나가는 곳마다 "들어오고 나가는" 짝을 맞춰야 하니, 중간 지점은 차수가 짝수여야 하거든요.

비슷해 보이지만 "모든 정점을 한 번씩 방문하는 길"(해밀턴 경로)은 훨씬 어려운 문제예요. 간단한 판별법이 알려져 있지 않고, 조합론 강의의 외판원 문제와 같은 어려움을 가져요. 비슷한 문제가 한쪽은 쉽고 한쪽은 극도로 어렵다는 것, 이게 계산 복잡도 이론의 출발점이에요.

의존성과 위상 정렬

방향 그래프에서 사이클이 없으면(DAG), 모든 간선이 앞에서 뒤로 향하도록 정점을 한 줄로 세울 수 있어요. 이걸 위상 정렬이라고 해요.

과목 수강 순서: "자료구조를 들어야 알고리즘을 들을 수 있다"
프로그램 빌드 순서: 의존하는 라이브러리부터 먼저
엑셀 수식 계산 순서: 참조하는 셀부터 먼저

사이클이 있으면 순서를 정할 수 없어요. A가 B를, B가 A를 기다리면 영원히 시작할 수 없죠. 프로그래밍에서 "순환 의존성" 오류가 바로 이거예요.

현실 속의 그래프

SNS: 사람은 정점, 친구 관계는 간선. "알 수도 있는 친구"는 공통 이웃이 많은 정점을 추천하는 거예요.
검색 엔진: 웹페이지는 정점, 링크는 방향 간선. 구글의 초기 핵심 아이디어인 페이지랭크는 "중요한 페이지가 많이 가리키는 페이지가 중요하다"를 그래프 위에서 계산해요.
인터넷: 라우터는 정점, 회선은 간선. 데이터가 오가는 길을 정하는 라우팅은 최단 경로 문제예요(네트워크 트랙).
지식 그래프: "서울 - 수도이다 - 대한민국"처럼 개체와 관계를 이어 AI에게 사실을 알려 줘요.

연습 문제

정점 6개, 간선 9개인 그래프에서 모든 정점의 차수 합은?
정점이 50개인 트리의 간선은 몇 개인가요?
7명이 모두 서로 한 번씩 악수하면 악수는 몇 번인가요? 그래프로 생각해 보세요.
정점 차수가 2, 2, 3, 3, 4인 연결 그래프에서 모든 간선을 한 번씩 지나는 길이 있을까요? 있다면 어디서 출발해야 할까요?
인접 리스트가 인접 행렬보다 유리한 경우는?

정답

악수 정리에 따라 $2 \times 9 = 18$ 이에요.
$50 - 1 = 49$ 개예요.
모든 정점이 서로 연결된 완전 그래프의 간선 수 $\binom{7}{2} = 21$ 번이에요.
홀수 차수 정점이 2개(차수 3인 두 정점)라 길은 있어요. 그 두 정점 중 하나에서 출발해 다른 하나에서 끝나요.
정점은 많은데 연결이 드문드문할 때(대부분의 실제 그래프)예요. 공간을 간선 수만큼만 쓰기 때문이에요.

수학 기초를 마치며

논리, 집합, 함수, 지수와 로그, 조합, 증명, 그래프까지 컴퓨터 수학의 기본 문법을 모두 훑었어요. 이제 수학 기호가 나와도 겁먹지 않고 "이건 집합이고, 이건 함수의 합성이구나" 하고 읽을 수 있을 거예요.

AI 집중 코스라면 다음은 선형대수예요. 데이터를 벡터와 행렬로 바꾸는 순간, 수백만 개의 숫자를 한 번에 다루는 길이 열려요.