그래프 이론
“그래프는 위치를 버리고 '연결'만 남긴 지도다.”
수식
G = (V, E), Σ(v∈V) deg(v) = 2|E|읽는 법: 그래프는 점들의 모임 V와 그 점들을 잇는 선들의 모임 E로 이루어지고, 모든 점의 차수를 더하면 변 개수의 두 배다
- V
- — 꼭짓점(정점)의 집합 — '점'들
- E
- — 변(간선)의 집합 — 점들을 잇는 '선'들
- deg(v)
- — 정점 v에 붙은 변의 개수(차수)
- Σdeg(v) = 2|E|
- — 차수의 합은 변 개수의 두 배(악수 정리)
이야기의 시작
친구 관계, 지하철 노선, 인터넷, 분자 구조 — 이 모두가 '점과 선'이라는 단 하나의 그림으로 표현된다.
쉬운 말로
그래프는 점(정점)들과 그 점을 잇는 선(변)들의 모임이다. 무엇이 서로 '연결되어 있는가'만 담고 위치·모양·거리는 버린다. 관계의 뼈대만 남긴 지도다.
직관
지하철 노선도를 떠올려라 — 실제 거리나 방향은 엉터리지만, '어느 역이 어느 역과 이어지는가'는 완벽히 담는다. 그게 그래프의 정신이다. 점이 무엇이든(사람·도시·웹페이지), 선이 무엇이든(친구·도로·링크), 오직 '연결의 구조'만 보면 전혀 달라 보이던 문제들이 같은 문제가 된다.
어떻게 만들어지나
두 부품 — 정점 집합 V와 변 집합 E. 각 정점의 '차수'는 거기 붙은 변의 수다. 악수 정리: 모든 차수를 더하면 변 개수의 딱 두 배가 된다(변 하나가 양 끝에서 두 번 세어지므로). 이 단순한 셈이 놀랍도록 강력하다.
예시
삼각형 그래프: 정점 3개, 변 3개. 각 정점의 차수는 2이므로 차수의 합은 2+2+2 = 6 = 2 × 3(변 개수). 악수 정리가 딱 맞는다.
흔한 오해
여기서 '그래프'는 함수 y=f(x)를 그린 곡선이 아니다. 좌표축도 곡선도 없다 — 오직 점과 그 점들을 잇는 선의 연결망이다. 같은 단어지만 전혀 다른 대상.
어디에 쓰나
구글 검색순위(페이지랭크), GPS 최단경로, 소셜네트워크 분석, 회로 설계, 일정·색칠 문제, 전염병 확산 모형 — 무언가가 무언가와 이어져 있는 모든 문제가 그래프다.
어디서 왔나
1736년 오일러가 쾨니히스베르크의 다리 일곱 개를 한 번씩만 건너 모두 돌아올 수 있는가라는 퍼즐을 풀며 그래프 이론과 위상수학의 문을 열었다(답: 불가능).
선행 개념
확인 문제
악수 정리에 따라, 변이 5개인 그래프에서 모든 정점의 차수의 합은?
- 5
- 10✓
- 25
- 2.5
연습
변이 4개인 그래프에서 모든 정점 차수의 합을 구하라.
정답: 8
- 악수 정리: 차수의 합 = 2 × 변 개수
- = 2 × 4 = 8
핵심: 변 하나가 차수를 2 올린다.
완전그래프 K₄ (정점 4개, 모든 쌍이 연결) 의 변 개수를 구하라.
정답: 6
- 정점 4개 중 2개를 고르는 조합 수 C(4,2)
- = (4·3)/2 = 6
핵심: 완전그래프 Kₙ의 변 수 = n(n−1)/2.
정점 차수가 3, 3, 2, 2 인 그래프의 변 개수를 구하라.
정답: 5
- 차수의 합 = 3+3+2+2 = 10
- 변 개수 = 10 / 2 = 5
핵심: 변 개수 = 차수 합의 절반.
쾨니히스베르크의 일곱 다리를 한 번씩만 건너 모두 도는 산책이 왜 불가능한지 차수로 설명해보라.
정답: undefined
- 그런 산책(오일러 경로)은 홀수 차수 정점이 0개 또는 2개여야 가능
- 쾨니히스베르크는 네 육지가 모두 홀수 차수
- 홀수 차수가 4개(2 초과)이므로 불가능
핵심: 홀수 차수 정점이 3개 이상이면 오일러 경로는 없다.