그래프와 실생활 문제

18세기 쾨니히스베르크에는 강이 도시를 네 구역으로 나누고, 그 사이에 다리 일곱 개가 놓여 있었다. 시민들은 모든 다리를 꼭 한 번씩만 건너는 산책길이 있는지 궁금해했지만, 아무리 걸어 보아도 찾지 못했다. 강의 모양, 구역의 넓이, 다리의 길이는 이 문제와 상관이 있을까? 오일러는 지도를 점과 선만 남긴 그림으로 바꾸어, 그런 길이 없다는 것을 증명했다. 무엇을 남기고 무엇을 버렸을까?

4.1.1점과 선만 남기기

다리를 한 번씩 건너는 길이 있는지는 어느 구역과 어느 구역이 몇 개의 다리로 이어져 있는지에만 달려 있다. 구역이 얼마나 넓은지, 다리가 얼마나 긴지, 강이 어떻게 굽었는지는 상관이 없다. 그래서 각 구역을 점 하나로, 각 다리를 두 점을 잇는 선 하나로 바꾼다. 이렇게 점과 그 점들을 잇는 선으로 이루어진 그림을 그래프라 하고, 점을 꼭짓점, 선을 변이라 한다. 그래프에서는 점의 위치나 선의 길이와 모양은 뜻이 없고, 어느 점과 어느 점이 이어져 있는지만 뜻이 있다.

산책길이 어떤 구역을 지나갈 때마다 들어오는 다리 하나와 나가는 다리 하나를 쓴다. 그래서 출발점과 도착점이 아닌 구역은 다리를 짝수 개 써야 하고, 모든 다리를 한 번씩 쓰려면 그 구역의 차수가 짝수여야 한다. 홀수 차수가 허락되는 곳은 출발점과 도착점뿐이므로, 홀수 차수인 꼭짓점은 많아야 2개이다. 쾨니히스베르크의 그래프는 네 꼭짓점이 모두 홀수 차수여서 그런 산책길이 있을 수 없다.¹

4.1.2여러 문제를 그래프로

그래프는 서로 이어진 관계를 다루는 많은 문제에 쓴다. 지하철 노선도는 역을 꼭짓점, 이웃한 두 역을 잇는 구간을 변으로 하는 그래프이고, 실제 거리와 방향을 무시하고 연결만 보여 주어 갈아타기 쉽게 그린다. 친구 관계, 웹 페이지의 링크, 전력망, 분자의 원자 결합도 모두 그래프이다. 문제를 그래프로 바꾸면 겉모습이 다른 문제들이 같은 구조를 가졌음이 드러나, 한 가지 방법으로 여러 문제를 풀 수 있다.

4.1.3예제 풀이

A는 B와 두 다리, D와 한 다리로 이어져 차수 3이다. B는 A와 둘, C와 둘, D와 하나로 차수 5, C는 차수 3, D는 A, B, C와 하나씩 이어져 차수 3이다. 홀수 차수인 꼭짓점이 4개이므로, 출발점과 도착점을 어떻게 정해도 적어도 두 구역에서는 들어오고 나가는 다리의 짝이 맞지 않는다. 그래서 모든 다리를 한 번씩 건너는 산책길은 없다.

홀수 차수인 꼭짓점 둘 사이에 다리를 하나 더 놓으면 그 둘의 차수가 짝수가 되어 홀수 차수인 꼭짓점이 2개로 준다. 예를 들어 A와 C 사이에 다리를 놓으면 홀수 차수인 꼭짓점은 B와 D뿐이어서, B에서 출발해 D에 도착하는 산책길이 생긴다. 즉 그래프는 문제에서 연결 관계만 남기고 나머지를 버린 그림이며, 꼭짓점의 차수 같은 간단한 수만으로도 길이 있는지 판단할 수 있다.

아래 탐구 카드에서 일곱 다리를 한 번씩 건너는 길을 직접 찾아보고, 버스 노선 설명을 그래프로 그려 무엇이 보이는지 확인해 보자.

1. 오일러는 1736년 이 문제를 풀며 위치만 따지고 크기는 따지지 않는 기하학이 필요하다고 썼다. 이 논문이 그래프 이론과 위상수학의 출발점으로 꼽힌다. 쾨니히스베르크는 지금 러시아의 칼리닌그라드이며, 다리 일부는 전쟁으로 사라졌다.