오일러 경로(Euler path)

18세기 프로이센의 쾨니히스베르크(지금의 러시아 칼리닌그라드)에서는 프레겔강이 도시를 네 덩어리 땅으로 나누고, 일곱 개의 다리가 그 사이를 이었습니다. 모든 다리를 꼭 한 번씩 건너는 산책이 가능할까요? 1735년 오일러는 땅의 모양과 다리의 길이를 모두 버리고, 어느 땅과 어느 땅이 다리 몇 개로 이어졌는지만 남겨 그런 산책은 없다는 것을 보였습니다. 오일러가 점과 선을 그리지는 않았지만, 오늘날 말로 하면 땅을 점으로, 다리를 변으로 바꾼 그래프의 문제입니다.

열쇠는 차수의 홀짝입니다. 길이 어떤 땅을 지나갈 때마다 들어오는 다리 하나와 나가는 다리 하나를 씁니다. 그러니 출발점과 도착점이 아닌 땅에는 다리가 짝수 개 있어야 합니다. 차수를 2로 나눈 나머지⁠(remainder)⁠만 보면 되는 셈입니다. 홀수 차수인 점은 많아야 둘(출발점과 도착점)이고, 제자리로 돌아오는 회로라면 하나도 없어야 합니다. 쾨니히스베르크의 네 땅은 차수가 5, 3, 3, 3으로 모두 홀수이니 불가능합니다.

보기: . 꼭짓점 두 개를 차례로 누르면 그 사이에 (눌러서 바꾸기). 분홍 점이 홀수 차수입니다. 판정: 길이 있으면 아래 ◀ ▶로 한 변씩 따라 걸을 수 있습니다.

거꾸로, 조건이 맞으면 길이 반드시 있습니다(변들이 모두 한 연결 성분⁠(connected component)⁠ 안에 있다면). 오일러는 이 방향을 증명 없이 적었습니다. 홀수 점에서(없으면 아무 데서나) 출발해 안 쓴 변을 따라 걷다가 막히면, 지나온 길 위에서 아직 안 쓴 변이 남은 점을 찾아 거기서 도는 작은 고리를 끼워 넣습니다. 이것이 독일의 수학자 카를 히어홀처가 찾은 방법이고(그가 죽은 뒤인 1873년에 발표되었습니다), 그림의 걷기도 이렇게 찾은 길입니다. 변마다 붙는 번호 1, 2, …, m은 변들과 순서 사이의 일대일대응입니다.

비슷해 보이는 '모든 꼭짓점을 한 번씩 지나는 길'은 해밀턴 경로⁠(Hamiltonian path)⁠라고 부릅니다. 1857년 아일랜드의 수학자 해밀턴이 정십이면체의 꼭짓점을 한 번씩 도는 퍼즐을 만든 데서 붙은 이름입니다. 해밀턴 경로에는 차수의 홀짝 같은 간단한 판정법이 알려져 있지 않습니다. 이 문제는 NP-완전⁠(NP-complete)⁠ 문제입니다. 누가 길을 내놓으면 맞는지 확인하기는 쉽지만, 길을 빠르게 찾는 방법은 아무도 모르는 문제들이 있는데, NP-완전 문제는 그 가운데 가장 어려운 무리입니다. 하나라도 빠르게 풀리면 그런 문제 전부가 빠르게 풀립니다.

반면 모든 길을 적어도 한 번씩 지나며 가장 짧게 돌아와야 하는 우편배달부 문제⁠(Chinese postman problem)⁠는 오일러 경로로 풀립니다. 홀수 점이 없으면 오일러 회로⁠(Euler circuit)⁠ 자체가 답입니다. 홀수 점이 있으면 그 점들을 둘씩 짝지어, 짝마다 최단 경로⁠(shortest path)⁠를 한 번 더 걷기로 합니다. 이렇게 겹쳐 걷는 길을 변으로 더하면 모든 점의 차수가 짝수가 되어 오일러 회로가 생깁니다. 짝짓는 방법 가운데 더 걷는 길이의 합이 가장 작은 것을 고르면 그것이 가장 짧은 순회입니다.

이어지는 곳. 0과 1로 된 길이 3의 문자열은 여덟 개입니다. 끝이 처음과 이어진 고리로 읽을 때 이 여덟 개가 모두 한 번씩 나타나는 가장 짧은 수열이 00010111입니다. 000, 001, 010, 101, 011, 111, 110, 100이 차례로 나타나며, 모두 3자리 이진수입니다. 네덜란드의 수학자 니콜라스 드 브라위언의 이름을 따 드 브라위언 수열⁠(de Bruijn sequence)⁠이라 부르는데, 오일러 회로로 만듭니다. 두 자리 문자열 00, 01, 10, 11을 꼭짓점으로 두고, 세 자리 문자열 abc마다 ab에서 bc로 가는 화살표를 긋습니다. 그러면 모든 꼭짓점에 화살표가 둘씩 들어오고 둘씩 나갑니다. 화살표가 있는 그래프에서는 들어오는 수와 나가는 수가 모든 점에서 같고 화살표를 따라 어디서든 어디로든 갈 수 있으면 오일러 회로가 있으므로, 화살표 여덟 개를 모두 한 번씩 지나는 회로가 있고, 그 회로를 따라 읽은 글자들이 바로 이 수열입니다. 짧게 읽은 DNA 조각들을 이어 붙여 긴 유전체를 복원할 때도 조각을 이렇게 화살표로 놓고 오일러 경로를 찾습니다. 오일러가 연 그래프 이론은 지도의 나라를 점으로, 국경을 변으로 바꾸어 색칠을 묻는 4색 정리⁠(four color theorem)⁠와, 수십억 개의 점으로 된 연결망에서 거리가 얼마나 짧은지를 묻는 좁은 세상⁠(small world)⁠ 연구로 이어집니다.