모든 변을 한 번씩 지나는 경로(오일러 경로)와 모든 꼭짓점을 한 번씩 지나는 경로(해밀턴 경로)는 비슷해 보이지만, 앞의 것은 간단한 판정법이 있고 뒤의 것은 아직 빠른 판정법이 알려지지 않았다. 지도 앱의 길찾기는 최단 경로 문제이다.
핵심 개념
- 오일러 회로: 모든 변을 정확히 한 번씩 지나 출발점으로 돌아오는 회로 (한붓그리기)
- 해밀턴 회로: 모든 꼭짓점을 정확히 한 번씩 지나 돌아오는 회로
- 최단 경로: 가중치가 있는 그래프에서 두 꼭짓점 사이의 가중치 합이 최소인 경로 (다익스트라 알고리즘)
핵심 정리 (오일러)
연결 그래프가 오일러 회로를 가질 필요충분조건은 모든 꼭짓점의 차수가 짝수인 것이다. 홀수 차수 꼭짓점이 정확히 $2$개이면 그 두 점을 양 끝으로 하는 오일러 경로가 있다.
증명 보기
필요조건. 오일러 회로를 따라가면, 어떤 꼭짓점을 지날 때마다 ‘들어오는 변’과 ‘나가는 변’을 하나씩 쓴다. 출발점도 처음에 나가고 마지막에 들어오므로 짝이 맞는다. 모든 변을 한 번씩 쓰므로 각 꼭짓점의 차수는 짝수이다.
충분조건 (생각의 흐름). 모든 차수가 짝수이면, 아무 점에서 출발해 쓰지 않은 변을 따라 계속 걸어 보자. 짝수 차수 때문에 출발점이 아닌 점에 들어가면 항상 나올 변이 남아 있으므로, 결국 출발점으로 돌아와 회로 $C$가 생긴다. 아직 쓰지 않은 변이 있으면, 연결되어 있으므로 $C$ 위의 어떤 점에서 쓰지 않은 변이 나간다. 그 점에서 같은 방법으로 새 회로를 만들어 $C$에 끼워 넣는다. 변은 유한하므로 이 과정이 끝나면 모든 변을 쓴 오일러 회로가 된다. $\blacksquare$
예제
- 쾨니히스베르크: 차수 $5,3,3,3$으로 홀수 차수가 $4$개이므로 오일러 경로도 회로도 없다.
- 정육면체의 모서리 그래프: 모든 꼭짓점의 차수가 $3$이므로 오일러 회로가 없지만, 해밀턴 회로는 있다.
- ‘봉투’ 모양(집 모양) 그림은 홀수 차수가 $2$개이므로 그 점에서 시작하면 한붓그리기가 된다.
확인 문제
$K_5$와 $K_6$은 각각 오일러 회로를 가지는가?
풀이 보기
$K_n$의 각 꼭짓점의 차수는 $n-1$이다. $K_5$는 차수가 $4$(짝수)이므로 오일러 회로가 있고, $K_6$은 차수가 $5$(홀수)이므로 없다.
정리
- 오일러 회로 ⇔ 연결 + 모든 차수 짝수
- 해밀턴 회로는 일반적인 판정법이 알려져 있지 않다 (NP-완전 문제).
