그래프의 기초

점(꼭짓점)과 그 점들을 잇는 선(변)으로 이루어진 구조를 그래프라 한다. 지하철 노선도, SNS 친구 관계, 인터넷, 분자 구조가 모두 그래프이다. 1736년 오일러가 쾨니히스베르크의 다리 문제를 풀면서 시작되었다.

핵심 개념

  • 그래프 $G=(V,E)$: 꼭짓점 집합 $V$와 변 집합 $E$
  • 차수 $\deg(v)$: 꼭짓점 $v$에 연결된 변의 수
  • 경로: 변을 따라 꼭짓점을 차례로 지나는 것, 회로: 시작점으로 돌아오는 경로
  • 연결 그래프: 모든 두 꼭짓점 사이에 경로가 있는 그래프
  • 완전그래프 $K_n$: 모든 두 꼭짓점이 연결됨, 변의 수 ${}_nC_2$
  • 이분그래프: 꼭짓점을 두 무리로 나누어 같은 무리끼리는 변이 없는 그래프
  • 인접행렬: $a_{ij}=1$ ($i$, $j$가 연결됨), $0$ (아님)
꼭짓점 5개, 변 7개인 그래프와 각 꼭짓점의 차수
차수의 합 $14=2\times7$

핵심 정리 (악수 정리)

$$\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배
  • 홀수 차수 꼭짓점은 짝수 개
알림: 보호된 콘텐츠입니다.