점(꼭짓점)과 그 점들을 잇는 선(변)으로 이루어진 구조를 그래프라 한다. 지하철 노선도, SNS 친구 관계, 인터넷, 분자 구조가 모두 그래프이다. 1736년 오일러가 쾨니히스베르크의 다리 문제를 풀면서 시작되었다.
핵심 개념
- 그래프 $G=(V,E)$: 꼭짓점 집합 $V$와 변 집합 $E$
- 차수 $\deg(v)$: 꼭짓점 $v$에 연결된 변의 수
- 경로: 변을 따라 꼭짓점을 차례로 지나는 것, 회로: 시작점으로 돌아오는 경로
- 연결 그래프: 모든 두 꼭짓점 사이에 경로가 있는 그래프
- 완전그래프 $K_n$: 모든 두 꼭짓점이 연결됨, 변의 수 ${}_nC_2$
- 이분그래프: 꼭짓점을 두 무리로 나누어 같은 무리끼리는 변이 없는 그래프
- 인접행렬: $a_{ij}=1$ ($i$, $j$가 연결됨), $0$ (아님)
핵심 정리 (악수 정리)
$$\sum_{v\in V}\deg(v)=2|E|$$
따라서 차수가 홀수인 꼭짓점의 개수는 항상 짝수이다.
증명 보기
각 변은 두 끝점을 가지므로, 차수를 모두 더할 때 각 변은 정확히 두 번(양 끝에서 한 번씩) 세어진다. 따라서 차수의 합은 $2|E|$이다. 차수의 합이 짝수이므로, 홀수 차수들을 더한 값도 짝수여야 하고, 홀수를 더해 짝수가 되려면 홀수가 짝수 개여야 한다. $\blacksquare$
이름의 유래: 모임에서 사람들이 악수한 횟수를 모두 더하면 악수 한 번마다 두 사람이 세어지므로 항상 짝수이다.
예제
- $K_5$의 변의 수: ${}_5C_2=10$, 모든 꼭짓점의 차수는 $4$
- 각 꼭짓점의 차수가 $3$인 그래프는 꼭짓점이 홀수 개일 수 없다($3n=2|E|$이므로 $n$은 짝수).
확인 문제
어느 모임의 $9$명이 각자 정확히 $3$명과 악수하는 것이 가능한가?
풀이 보기
불가능하다. 차수의 합이 $9\times3=27$로 홀수가 되어 악수 정리에 모순이다.
정리
- 차수의 합 = 변의 수의 2배
- 홀수 차수 꼭짓점은 짝수 개
