오일러 경로와 오일러 회로 해설

어떤 도형은 연필을 떼지 않고, 어떤 선도 두 번 덧긋지 않고 한 획에 그릴 수 있지만, 어떤 도형은 아무리 애써도 그릴 수 없습니다. 애쓸 필요도 없습니다. 각 모서리에 모이는 선을 세어 보세요. 선의 개수가 홀수인 모서리가 둘 이하라면 그 도형은 그릴 수 있고, 획은 바로 그 모서리에서 시작하고 끝나야 합니다. 레온하르트 오일러는 1736년에 이 규칙을 찾아내고 그것으로 그래프 이론을 세웠습니다.

쾨니히스베르크의 일곱 다리를 그래프로 그린 그림. 네 땅이 꼭짓점이고 넷 모두 다리 수가 홀수이며, 강 양쪽에 걸쳐 있다
쾨니히스베르크의 일곱 다리를 그래프로 그린 그림. 네 땅이 꼭짓점이고 넷 모두 다리 수가 홀수이며, 강 양쪽에 걸쳐 있다

쾨니히스베르크의 일곱 다리

프로이센의 도시 쾨니히스베르크, 오늘날의 칼리닌그라드는 프레겔강 양쪽 기슭과 강 가운데 두 섬인 크나이프호프와 롬제에 걸쳐 있었습니다. 일곱 다리가 네 부분을 이었습니다. 크나이프호프에서 양쪽 기슭으로 둘씩, 두 섬 사이에 하나, 롬제에서 양쪽 기슭으로 하나씩이었습니다. 시민들은 모든 다리를 정확히 한 번씩 건너는 산책이 가능한지 궁금해했습니다. 오일러는 1735년 상트페테르부르크 학술원에 제출해 1741년에 인쇄된 논문에서 답했습니다. 불가능하다고. 그의 결정적 한 걸음은 도시의 부분과 그 사이의 다리만 남기고 나머지를 모두 버린 것이었습니다. 그래프가 하는 일이 바로 그것입니다. 땅마다 꼭짓점 하나, 다리마다 변 하나, 같은 곳을 두 다리가 이으면 변 둘.

레온하르트 오일러의 초상
레온하르트 오일러의 초상
Portrait of Leonhard Euler
Portrait of Leonhard Euler

차수 규칙

꼭짓점의 차수란 그 꼭짓점에 닿는 변의 개수입니다. 꼭짓점을 지나는 획은 한 변으로 들어와 다른 변으로 나가므로, 그 꼭짓점의 변을 짝지어 씁니다. 짝 없는 변을 남길 수 있는 것은 획의 첫 꼭짓점과 마지막 꼭짓점뿐입니다. 그래서 차수가 홀수인 꼭짓점은 획의 시작이거나 끝이어야 합니다. 크나이프호프에는 다리가 다섯, 나머지 세 부분에는 셋씩 있었습니다. 홀수 꼭짓점이 넷으로 둘이 많았던 셈입니다. 일반적으로 연결 그래프는 모든 차수가 짝수일 때 시작한 자리에서 끝나는 획, 곧 오일러 회로를 가지고, 차수가 홀수인 꼭짓점이 정확히 둘일 때 한쪽에서 다른 쪽으로 가는 오일러 경로를 가집니다. 홀수 꼭짓점의 개수는 결코 1이나 다른 홀수가 되지 않습니다. 변 하나가 모든 차수의 합에 2를 더하므로 그 합은 짝수이기 때문입니다. 오일러도 이를 알아차렸고, 오늘날에는 악수 보조정리라고 부릅니다.

왜 이 규칙으로 충분한가

오일러는 홀수 꼭짓점이 둘을 넘는 도형은 그릴 수 없음을 보였고, 다른 모든 연결 도형은 그릴 수 있다고 증명 없이 말했습니다. 증명은 1871년 젊은 나이에 세상을 떠난 독일 수학자 카를 히어홀처에게서 나왔고, 그의 논문은 1873년에 나왔습니다. 홀수 꼭짓점이 있으면 거기서, 없으면 어디서든 시작해 쓰지 않은 변을 따라 갈 수 있는 데까지 갑니다. 다른 꼭짓점은 모두 차수가 짝수이므로 막히는 곳은 끝 꼭짓점뿐입니다. 변이 남아 있다면 도형이 연결되어 있으므로 그중 일부는 지금까지의 길에 닿습니다. 그런 꼭짓점에서 다시 막힐 때까지 걸으면 이번에는 그 꼭짓점으로 돌아와 멈추므로, 그 자리에서 고리를 길에 끼워 넣습니다. 변이 하나도 남지 않을 때까지 되풀이합니다. 이 증명은 그대로 가장 빠른 알고리즘이기도 합니다. 각 변을 보는 횟수가 정해져 있기 때문입니다.

플뢰리 알고리즘: 다리를 태우지 말 것

그릴 수 있는 도형에서도 한 획은 실패할 수 있습니다. 변 하나로 이어진 삼각형 두 개를 놓고 첫 삼각형의 모서리에서 시작해 보세요. 첫 삼각형을 끝내기 전에 두 번째로 건너가면 다시는 돌아올 수 없습니다. 이어 주는 그 변이 다리입니다. 없애면 도형이 둘로 갈라집니다. 1883년 플뢰리의 알고리즘은 한 가지 규칙을 줍니다. 각 꼭짓점에서는 남은 변들에 대해 다리가 아닌 변을 고르되, 다른 변이 없을 때는 예외라는 것입니다. 이 규칙을 따르면 언제나 끝까지 그릴 수 있습니다. 다리인지 확인하는 데 시간이 걸려 플뢰리 알고리즘은 히어홀처 알고리즘보다 느리지만, 연필을 들고 직접 따라갈 수 있는 쪽은 이것이고, 앱의 힌트도 이것을 씁니다.

도형 고치기

홀수 꼭짓점이 k개인 도형은 k/2획이 필요합니다. 한 획으로 그리려면 홀수 꼭짓점을 둘씩 짝지어 잇는 변을 더하면 됩니다. 새 변 하나가 홀수 꼭짓점 둘을 짝수로 바꿉니다. k/2 − 1개를 더하면 홀수 꼭짓점이 둘 남아 경로가 되고, k/2개를 더하면 하나도 남지 않아 회로가 됩니다. 쾨니히스베르크에서도 네 부분 가운데 어느 둘 사이에 다리를 하나 더 놓았다면 산책이 가능했고, 둘을 더 놓았다면 한 바퀴 돌아올 수도 있었습니다. 역사도 비슷한 일을 했습니다. 두 다리는 제2차 세계대전에서 사라지고 두 다리는 현대식 도로로 바뀌었으며, 오늘날 옛 자리에 선 다섯 다리는 한 섬에서 다른 섬으로 한 번씩 건널 수 있습니다.

방법 수 세기

산타클로스의 집은 두 대각선을 그은 정사각형에 지붕을 얹은 모양으로, 이 퍼즐의 독일 어린이판입니다. “Das ist das Haus vom Ni-ko-laus”는 여덟 음절이고 선 하나에 한 음절씩 붙습니다. 아래 두 모서리만이 홀수 꼭짓점이고, 각 모서리에서 정확히 44가지, 모두 88가지 방법이 있습니다. 방향 그래프라면 오일러 회로의 개수에 드브라윈, 판아르데너에렌페스트, 스미스, 투트의 이름을 딴 BEST 정리라는 공식이 있습니다. 보통 그래프에는 그런 공식이 알려져 있지 않고 세는 일 자체가 일반적으로 어렵다고 여겨지므로, 이 앱은 작은 도형에 대해 모든 방법을 시도하되 도형을 둘로 가르는 수는 건너뛰며 셉니다.

오일러 경로가 쓰이는 곳

제설차도, 청소차도, 우편배달부도 모든 길을 한 번씩 지나 돌아오고 싶어 합니다. 교차로마다 길의 수가 짝수라면 오일러 회로로 해결됩니다. 그렇지 않으면 어떤 길은 두 번 지나야 하고, 그중 비용이 가장 적은 조합을 고르는 것이 1962년 관메이구가 제기한 중국인 우편배달부 문제입니다. 펜 플로터나 레이저 커터도 펜을 떼지 않고 되도록 많은 선을 그어 시간을 아낍니다. 유전체 해독에서는 짧은 DNA 조각 수백만 개를, 각 조각이 변이 되는 드브라윈 그래프에서 오일러 경로를 찾아 이어 붙입니다. 같은 규칙은 퍼즐책의 어떤 선 그림이 해 볼 만한지도 알려 줍니다.

직접 해 보기

오일러 경로 찾기를 열면 1736년과 오늘의 쾨니히스베르크에서 별, 겹겹의 정사각형, 정육면체까지 열두 도형을 직접 따라 그릴 수 있고, 평행한 변을 넣어 자신만의 도형을 그릴 수도 있습니다. 홀수 꼭짓점은 채워져 있고, 꼭짓점마다 차수가 표시되며, 도형 아래의 차수 규칙이 무엇이 가능한지와 어떤 변을 더하면 도형이 고쳐지는지 알려 줍니다. 막히면 앱이 시작한 꼭짓점이 잘못된 것인지 다리를 너무 일찍 건넌 것인지, 그리고 그것이 몇 번째 수였는지 말해 줍니다. 힌트는 안전한 변을 주고, 풀기는 플뢰리 알고리즘으로 다리 판정을 보여 주며 그리거나 히어홀처 알고리즘으로 끼워 넣는 과정을 보여 주며 그립니다.

자주 묻는 질문

오일러 경로와 해밀턴 경로는 같은 것인가요?

아닙니다. 오일러 경로는 모든 변을 한 번씩 쓰고 같은 꼭짓점을 여러 번 지나도 됩니다. 해밀턴 경로는 모든 꼭짓점을 한 번씩 지나며 모든 변을 쓸 필요는 없습니다. 그래프에 오일러 경로가 있는지는 홀수 꼭짓점을 세면 바로 알 수 있지만, 해밀턴 경로에는 빠른 판정법이 알려져 있지 않고 하나를 찾는 일은 컴퓨터 과학의 고전적인 어려운 문제 가운데 하나입니다.

두 꼭짓점이 변 여러 개로 이어져 있어도 차수 규칙이 성립하나요?

성립합니다. 모든 변은 두 끝 꼭짓점의 차수에 각각 더해지며, 같은 두 꼭짓점을 잇는 다른 변이 있든 없든 상관없습니다. 쾨니히스베르크가 바로 그런 다중 그래프로, 크나이프호프와 각 기슭이 다리 두 개로 이어져 있습니다. 꼭짓점에서 자기 자신으로 가는 변, 곧 고리는 차수에 2를 더하므로 홀짝을 바꾸지 않습니다.

일방통행 도로는 어떻게 되나요?

방향 그래프에서는 변마다 방향이 있고, 규칙은 각 꼭짓점에 들어오는 변과 나가는 변을 견줍니다. 모든 꼭짓점에서 들어오는 변과 나가는 변의 수가 같고 변들이 하나로 이어져 있으면 오일러 회로가 있습니다. 한 꼭짓점은 나가는 변이 하나 많고 다른 한 꼭짓점은 들어오는 변이 하나 많으며 나머지가 모두 균형을 이루면 오일러 경로가 있고, 경로는 앞의 꼭짓점에서 뒤의 꼭짓점으로 갑니다.

홀수 꼭짓점이 정확히 하나인 도형이 있을 수 있나요?

없습니다. 모든 꼭짓점의 차수를 더하면 변 개수의 두 배가 됩니다. 변마다 끝이 둘이기 때문입니다. 이 합은 짝수이므로 그 안에 든 홀수 차수의 개수도 짝수여야 합니다. 0, 2, 4처럼 이어지며 1이나 3이 되는 일은 없습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

오일러 경로 찾기 열기