[알고리즘 이야기] 오일러

​

오일러(Leonhard Euler, 1707~1783)는 스위스의 수학자, 물리학자, 천문학자, 논리학자, 공학자로서 그래프의 창시자라고도 알려져 있습니다.

​

 

---

 

​

 

특히나 오일러의 등식들은 수학의 아름다움(?)을 표현하는 식으로 유명하게 알려져 있습니다. 이 식을 잘 살펴보면 영역이 다른 다섯 가지 수인 0,1(상수/constant), 자연상수 e (해석학), 원주율 π, 그리고 허수 i (대수학)가 모두 하나의 식에 포함되어 있으며, 수학의 가장 기초가 되는 4가지 연산인 곱셈, 지수, 그리고 등호가 모두 쓰인 책이기 때문입니다. 아인슈타인과 함께 20세기의 최고 물리학자로 불리는 리처드 파인만(Richard Feynman)은 이 식을 "수학에서 가장 비범한 식(the most remarkable formula in mathematics)"이라며 극찬하였습니다.

 

---

 

​

​

 

한편 1735년 프러시아의 쾌니히스베르크(현재는 러시아의 칼리닌그라드)에 위치한 프레겔 강 한가운데 섬 2개에 놓은 7개 다리가 있는데 주민들이 오일러에게 이 다리들을 빠짐없이 1번씩만 지나서 출발점으로 돌아올 수 있는지 물어보았습니다. 오일러는 그렇게 할 수 없다는 답변을 전달해 주었는데, 이 문제가 최초의 그래프 문제로 알려져 있습니다.

​

 

이 문제는 한 붓 그리기와 같은 문제이고, 오일러는 다리(그래프의 간선)를 한 번씩만 지나서 출발점으로 되돌아오려면 각 정점의 차수가 짝수여야 한다는 것을 증명하였습니다. 주어진 그래프에서 임의의 정점에서 출발하여 모든 간선을 빠짐없이 한 번씩만 지나면서 출발점으로 돌아오는 경로를 오일러 서킷(Euler Circuit) 또는 오일러 사이클이라고 합니다.