📂그래프이론

쾨니히스베르크의 다리 문제와 풀이

문제 ¹

쾨니히스베르크의 다리 문제는 다음과 같이 도시에 놓인 7개의 다리를 한 번씩만 건너면서 처음 있는 위치로 돌아올 수 있는지에 관한 것이었다. 해법을 모른다면 언뜻 경우의 수를 다 따져봐야하는 막막한 문제로 보인다. 일단 수학 문제처럼 보이지도 않고, 모든 경우를 다 따져보면 풀릴 것 같은데 막상 따져보기가 쉽지는 않다.

위대한 수학자 오일러는 이것을 그래프 문제로 바꿔서 멋지게 해결해냈다. 놀라운 건 그래프 이론이 당시에 학계의 관심을 받기는커녕 공간을 위상적으로 바라본다는 발상 자체도 없었을 때의 해법이라는 것이다. 말하자면 오일러는 미래의 개념을 가져와 미래의 방법으로 문제를 풀어버렸다. 이제 그 풀이가 무엇인지 살펴보자.

풀이

위의 그림을 간단하게 도식화해보면 다음과 같다.

이제 강으로 나뉜 지역이 각각의 버텍스로, 지역을 잇는 다리를 에지로 나타내는 그래프를 생각해보면 다음과 같다.

이제 쾨니히스베르크의 다리 문제는 위 그래프에서 모든 에지를 포함하면서(모든 다리를 건너면서) 닫힌(처음 위치로 돌아오는) 트레일(방법)이 있는지 판별하는 그래프 문제로 바뀌었다. 이렇듯 모든 에지를 포함하면서 닫힌 트레일이 존재하는 그래프를 오일러 그래프라고 한다.

오일러 정리: $G$ 가 연결 그래프라고 하자. $G$ 가 오일러 그래프인 것과 $G$ 의 모든 버텍스의 차수가 짝수인 것은 동치다.

한편 오일러 그래프의 동치 조건에 따르면 단 하나라도 차수가 홀수인 버텍스가 존재한다면 오일러 그래프가 아니다. 위 그래프는 심지어 모든 버텍스의 차수가 홀수이므로 오일러 그래프가 아니다. 이는 다시 말해 쾨니히스베르크의 다리를 모두 건너면서 처음 위치로 돌아오는 방법이 존재하지 않음을 의미한다.

■