수학과 사는 이야기

그림처럼 프로이센의 쾨니히스베르크(오늘날 러시아 칼리닌그라드)에는 강이 있고 강으로 둘러싸인 섬이 하나 있다. 섬을 잇는 다리가 7개가 있는데 사람들 가운데 운동이나 산책을 하면서 이 다리들을 모두 한 번씩만 건너서 출발한 곳으로 다시 돌아오려고 하는 이들이 있었다. 아무도 답을 찾지 못하고 있던 문제를 오일러가 각 지점을 점으로 다리는 변으로 생각하는 그래프를 고안하여 그럴 수 없다는 것을 밝혀냈다.(1735년) 위키디피아로 오일러는 어떤 그래프에 한 꼭짓점에서 시작하여 펜을 떼지 않고 모든 변을 한번씩만 지나서 처음 출발점으로 되돌아오는 길을 가지려면 각 꼭짓점에 연결된 변의 개수가 모두 짝수이어야 함을 증명했다. 오늘날 이산수학에서는 위 그림을 아래와 같이 간단하게 그래프로 나타낸다. 그래프 이론에..