쾨니히스베르크 다리 문제: 한붓그리기와 홀수 차수 꼭짓점의 증명

18세기 프로이센의 도시 쾨니히스베르크에는 프레겔강과 섬들을 잇는 다리 7개가 있었습니다. 시민들 사이에서는 어느 곳에서 출발하든 각 다리를 정확히 한 번씩만 건너 모든 다리를 통과할 수 있는지가 문제로 떠올랐습니다. 같은 다리를 두 번 건너면 안 되고, 다리를 건너지 않은 채 강을 건널 수도 없습니다. 출발점으로 반드시 돌아와야 한다는 조건이 없어도 이 경로는 존재하지 않습니다.

레온하르트 오일러는 다리의 길이나 육지의 넓이를 계산하지 않았습니다. 육지 4곳을 점으로, 다리 7개를 점 사이의 선으로 바꾸었습니다. 이렇게 만든 그래프에서 네 꼭짓점의 차수는 3, 3, 3, 5입니다. 차수는 꼭짓점에 연결된 변의 개수입니다. 네 꼭짓점이 모두 홀수 차수이므로 모든 변을 한 번씩 지나는 오일러 경로, 즉 한붓그리기는 불가능합니다.

변이 있는 부분이 하나로 연결된 그래프는 홀수 차수 꼭짓점이 0개 또는 2개일 때만 모든 변을 정확히 한 번씩 지나는 경로를 갖습니다.

홀수 차수 꼭짓점이 0개면 출발점과 도착점이 같은 닫힌 한붓그리기가 가능하고, 정확히 2개면 한 홀수 꼭짓점에서 출발해 다른 홀수 꼭짓점에서 끝나는 열린 한붓그리기가 가능합니다. 여기에 그래프가 연결되어 있어야 한다는 전제가 붙습니다. 홀수 차수 꼭짓점의 개수만 세고 연결성을 확인하지 않으면 잘못된 결론이 나올 수 있습니다.

쾨니히스베르크의 일곱 다리 문제란 무엇인가요?

당시 쾨니히스베르크는 오늘날 러시아의 칼리닌그라드에 해당합니다. 프레겔강이 흐르는 도시에는 크나이프호프섬을 포함한 육지 구역들이 있었고, 7개의 다리가 이 구역들을 연결했습니다. 문제의 핵심은 산책 경로의 총거리나 가장 짧은 길이 아니라 각 다리를 한 번씩만 사용한다는 순서 조건이었습니다.

오일러 아카이브에 수록된 원 논문은 라틴어 제목 ‘Solutio problematis ad geometriam situs pertinentis’, 즉 위치의 기하학에 관한 문제의 해법이라는 이름으로 알려져 있습니다. 논문은 1736년의 연구로 인용되며, 학술지 제8권에 1741년 출판되었습니다. 오일러는 이 문제에서 거리와 각도 같은 측정값을 버리고 무엇이 무엇과 연결되어 있는지만 남겼습니다. 이 접근은 그래프 이론의 출발점으로 널리 평가됩니다.

지도에서 그래프로 바꾸면 문제가 단순해진다

지도를 그대로 보면 강의 모양, 다리의 방향과 섬의 크기가 눈에 들어옵니다. 하지만 다리를 한 번씩 건널 수 있는지를 판단하는 데 이런 정보는 필요하지 않습니다. 필요한 정보는 육지 구역과 다리의 연결 관계뿐입니다.

쾨니히스베르크에서는 같은 두 육지 사이에 다리가 두 개 이상 놓인 경우가 있습니다. 따라서 이를 엄밀하게 표현하면 두 꼭짓점 사이에 여러 변을 허용하는 다중 그래프입니다. 오일러 경로의 차수 조건은 이런 유한 무방향 다중 그래프에도 적용됩니다.

꼭짓점의 차수는 무엇인가요?

꼭짓점 v의 차수는 보통 deg(v)로 쓰며, 그 꼭짓점에 닿는 변의 개수입니다. 다리 문제에서는 한 육지에서 건널 수 있는 다리의 수와 같습니다. 다리가 4개 연결된 육지는 차수 4인 꼭짓점이고, 5개 연결된 육지는 차수 5인 꼭짓점입니다.

핵심은 특정 꼭짓점을 경로의 중간에 방문할 때 들어오는 변과 나가는 변이 한 쌍을 이룬다는 점입니다. 들어오기만 하고 나오지 않는 곳은 도착점이며, 나오기만 하고 들어오지 않은 곳은 출발점입니다. 그래서 중간 꼭짓점과 양 끝점의 짝홀 조건이 달라집니다.

오일러 경로와 오일러 회로의 차이

일상적인 한붓그리기는 펜을 떼지 않고 선을 모두 한 번씩 그리는 문제입니다. 시작점과 끝점이 같아야 한다는 조건은 보통 필수가 아닙니다. 따라서 일반적인 한붓그리기는 오일러 경로에 대응합니다. 출발한 자리로 반드시 돌아와야 한다면 더 강한 조건인 오일러 회로를 찾아야 합니다.

필요조건 증명: 중간 꼭짓점의 차수는 왜 짝수여야 할까

모든 변을 정확히 한 번 지나는 경로가 이미 있다고 가정해 보겠습니다. 출발점과 도착점이 아닌 꼭짓점 v에 경로가 도착하면 사용하지 않은 다른 변으로 다시 나가야 합니다. 들어온 변 1개와 나간 변 1개가 한 쌍이 됩니다. 같은 꼭짓점을 여러 번 지나더라도 매번 변이 두 개씩 짝을 이룹니다.

중간 꼭짓점에서 사용되는 변 = 들어오는 변 1개 + 나가는 변 1개

모든 변을 다 사용했을 때 중간 꼭짓점에 닿는 변은 2개, 4개, 6개처럼 쌍으로 묶입니다. 따라서 출발점도 도착점도 아닌 모든 꼭짓점의 차수는 짝수여야 합니다. 차수가 3이나 5라면 변 하나를 짝지을 수 없으므로 중간 지점으로만 처리할 수 없습니다.

출발점과 도착점만 홀수가 될 수 있는 이유

출발점에서는 처음에 들어오지 않고 변 하나를 따라 나갑니다. 그 뒤 다시 출발점을 방문한다면 입장과 퇴장이 쌍을 이룹니다. 처음 나간 변 하나만 짝이 없으므로 출발점의 차수는 홀수가 될 수 있습니다. 도착점에서는 마지막에 들어온 뒤 다시 나가지 않습니다. 마지막으로 들어온 변 하나가 짝이 없으므로 도착점도 홀수 차수가 될 수 있습니다.

출발점과 도착점이 다르면 짝을 이루지 못한 변이 양 끝에 하나씩 생깁니다. 따라서 홀수 차수 꼭짓점은 정확히 2개이며, 경로는 한 홀수 꼭짓점에서 시작해 다른 홀수 꼭짓점에서 끝나야 합니다. 반대로 출발점과 도착점이 같으면 처음 나간 변과 마지막에 들어온 변까지 서로 짝을 이룰 수 있습니다. 이 경우 모든 꼭짓점의 차수가 짝수입니다.

열린 한붓그리기: 홀수 차수 꼭짓점 2개가 시작점과 끝점

닫힌 한붓그리기: 홀수 차수 꼭짓점 0개

홀수 차수 꼭짓점이 1개나 3개일 수 없는 이유

모든 유한 무방향 그래프에서는 꼭짓점 차수의 합이 변 개수의 두 배입니다. 변 하나는 양 끝의 꼭짓점 차수에 각각 1씩 기여하기 때문입니다. 이 관계를 악수 정리라고 부릅니다.

∑ deg(v) = 2|E|

오른쪽 2|E|는 항상 짝수입니다. 짝수 차수 꼭짓점들의 차수를 더한 값도 짝수입니다. 그러므로 홀수 차수 꼭짓점들의 차수를 더한 값 역시 짝수여야 합니다. 홀수를 홀수 개 더하면 홀수이고, 짝수 개 더하면 짝수이므로 홀수 차수 꼭짓점의 개수는 언제나 짝수입니다. 1개, 3개, 5개는 애초에 무방향 그래프에서 나올 수 없습니다.

쾨니히스베르크 그래프에는 홀수 꼭짓점이 4개다

육지 네 구역을 A, B, C, D라고 두면 역사적 쾨니히스베르크 그래프의 차수는 다음과 같이 정리됩니다. 이름을 어느 구역에 붙이는지는 그림에 따라 달라질 수 있지만 차수의 묶음은 5, 3, 3, 3으로 같습니다.

홀수 차수 꼭짓점 수 = 4개 > 2개

경로의 양 끝으로 사용할 수 있는 꼭짓점은 최대 2개뿐입니다. 홀수 차수 꼭짓점 4개 가운데 2개를 출발점과 도착점으로 정하더라도 나머지 2개는 경로 중간에 놓여야 합니다. 하지만 중간 꼭짓점에서는 모든 변이 입장과 퇴장의 쌍을 이루어야 하므로 차수가 짝수여야 합니다. 모순이 생기므로 어떤 출발점을 골라도 일곱 다리를 정확히 한 번씩 건너는 경로는 없습니다.

0개 또는 2개라는 조건은 충분하기도 할까

앞의 입장·퇴장 논리는 한붓그리기가 있다면 홀수 차수 꼭짓점이 0개 또는 2개여야 한다는 필요조건을 보여 줍니다. 하지만 조건을 만족하면 실제 경로가 반드시 존재하는지도 확인해야 정리가 완성됩니다. 유한 무방향 그래프에서 변이 있는 모든 꼭짓점이 하나의 연결 성분에 속한다는 조건을 더하면 충분조건도 성립합니다.

홀수 차수 꼭짓점이 0개일 때의 충분조건 증명

모든 꼭짓점의 차수가 짝수이고 그래프가 연결되어 있다고 하겠습니다. 변이 있는 아무 꼭짓점에서 출발해 아직 사용하지 않은 변만 따라갑니다. 현재 꼭짓점으로 들어올 때마다 변 하나를 사용하므로, 그 꼭짓점에서 이전에 사용한 변의 수는 입장과 퇴장의 쌍에 새 입장 하나가 붙은 홀수 개입니다. 원래 차수는 짝수이므로 사용하지 않은 변이 적어도 하나 남아 있어야 합니다. 따라서 출발점이 아닌 곳에서는 더 갈 변이 없어 멈출 수 없습니다.

그래프의 변은 유한하므로 이 과정은 언젠가 멈춥니다. 출발점이 아닌 곳에서는 멈출 수 없으므로 출발점으로 돌아와 닫힌 경로 하나를 만듭니다. 이 경로가 모든 변을 사용했다면 오일러 회로가 완성됩니다.

사용하지 않은 변이 남았다면 그래프의 연결성 때문에 현재 닫힌 경로 위의 어떤 꼭짓점에 미사용 변이 연결되어 있습니다. 그 꼭짓점에서 같은 방법으로 또 하나의 닫힌 경로를 만든 뒤 기존 경로에 끼워 넣습니다. 미사용 변이 없어질 때까지 반복하면 모든 변을 정확히 한 번 포함하는 하나의 닫힌 경로를 얻게 됩니다. 이것이 히어홀처 알고리즘의 핵심 아이디어입니다.

홀수 차수 꼭짓점이 2개일 때의 충분조건 증명

홀수 차수 꼭짓점이 정확히 u와 v 두 개라고 하겠습니다. u와 v 사이에 임시 변 하나를 추가하면 두 꼭짓점의 차수가 각각 1씩 늘어 짝수가 됩니다. 다른 꼭짓점들은 원래 짝수였으므로 모든 꼭짓점의 차수가 짝수가 됩니다.

방금 증명한 0개인 경우에 따라 임시 변을 포함하는 오일러 회로가 존재합니다. 이 회로에서 임시 변을 제거하고 그 지점을 끊으면, 원래 그래프의 모든 변을 정확히 한 번 지나는 열린 경로가 남습니다. 한쪽 끝은 u이고 다른 쪽 끝은 v입니다. 따라서 연결 그래프에서 홀수 차수 꼭짓점이 정확히 2개면 오일러 경로가 반드시 존재합니다.

연결성 조건을 빠뜨리면 왜 안 될까

서로 떨어진 삼각형 두 개를 생각해 보겠습니다. 각 삼각형의 꼭짓점 차수는 모두 2이므로 홀수 차수 꼭짓점은 0개입니다. 그러나 한 삼각형에서 다른 삼각형으로 이어지는 변이 없으므로 펜을 떼지 않고 두 도형의 모든 변을 그릴 수 없습니다. 차수 조건은 만족하지만 연결성 조건이 실패한 사례입니다.

정확한 조건은 ‘차수가 0보다 큰 모든 꼭짓점이 하나의 연결 성분에 있다’입니다. 아무 변도 연결되지 않은 고립 꼭짓점은 그릴 선이 없으므로 오일러 경로의 존재 여부에 영향을 주지 않습니다. 실용적으로는 선이 있는 부분 전체가 끊김 없이 이어지는지를 확인하면 됩니다.

한붓그리기 가능 여부를 3단계로 판정하는 법

1. 교차점과 선 끝, 여러 선이 만나는 지점을 꼭짓점으로 정하고 선분을 변으로 바꿉니다.
2. 변이 있는 부분이 하나로 연결되어 있는지 확인합니다.
3. 각 꼭짓점의 차수를 세고 홀수 차수 꼭짓점이 몇 개인지 확인합니다.

홀수 꼭짓점이 2개라면 아무 곳에서 시작하면 되는 것이 아닙니다. 반드시 둘 중 하나에서 시작해 나머지 하나에서 끝나야 합니다. 0개라면 변이 연결된 어느 꼭짓점에서 시작해도 오일러 회로를 구성할 수 있습니다.

교차하는 선을 언제 꼭짓점으로 보아야 할까

종이에 그린 두 선이 교차해도 실제로 그 지점에서 다른 선으로 갈아탈 수 없다면 그래프에서는 꼭짓점이 아닙니다. 고가도로와 지하도로가 평면 그림에서 겹쳐 보이지만 서로 연결되지 않은 경우가 대표적입니다. 반대로 교차점에서 방향을 바꿀 수 있다면 꼭짓점으로 세고, 만나는 선의 수를 차수에 반영해야 합니다.

다리 문제에서도 강물이 만나는 모양이 아니라 실제로 어느 육지에서 어느 다리로 이동할 수 있는지가 중요합니다. 그래프는 공간에 그려진 모양보다 연결 관계를 기록합니다. 링크가 어느 페이지로 이어지는지를 바탕으로 중요도를 계산하는 구글 페이지랭크의 링크 그래프와 마르코프 전이도 같은 그래프 표현을 사용하지만, 변의 방향과 계산 목적은 다릅니다.

오일러 경로와 해밀턴 경로는 다르다

오일러 경로는 모든 변을 정확히 한 번씩 지나는 문제입니다. 꼭짓점은 여러 번 방문해도 됩니다. 해밀턴 경로는 모든 꼭짓점을 정확히 한 번씩 방문하는 문제이며 변을 모두 사용할 필요는 없습니다. 한붓그리기나 다리 순회는 보통 오일러 경로 문제입니다.

두 문제를 혼동하면 홀수 차수 조건을 잘못 적용하게 됩니다. 오일러의 차수 정리는 모든 변을 한 번씩 쓰는 문제에 관한 것입니다. 도시를 한 번씩 방문하거나 배송 지점을 한 번씩 방문하는 문제에는 같은 판정법을 그대로 쓸 수 없습니다.

한붓그리기 경로를 실제로 찾는 히어홀처 알고리즘

차수 검사는 경로의 존재 여부를 판정합니다. 경로 자체를 찾으려면 히어홀처 알고리즘을 사용할 수 있습니다. 오일러 회로가 있는 연결 그래프에서는 아무 꼭짓점에서 시작하고, 오일러 경로만 있는 경우에는 홀수 차수 꼭짓점 하나에서 시작합니다.

1. 시작 꼭짓점을 스택에 넣습니다.
2. 현재 꼭짓점에 사용하지 않은 변이 있으면 그 변을 지우거나 사용 표시하고 다음 꼭짓점으로 이동합니다.
3. 사용하지 않은 변이 없으면 현재 꼭짓점을 최종 경로에 추가하고 스택에서 이전 꼭짓점으로 돌아갑니다.
4. 모든 변이 처리될 때까지 반복한 뒤 기록된 꼭짓점 순서를 뒤집습니다.

인접 목록으로 그래프를 저장하면 각 변을 한 번씩 처리하므로 구현 시간은 꼭짓점 수 |V|와 변 수 |E|의 합에 비례하는 O(|V|+|E|)로 만들 수 있습니다. 경로가 있는지 가능한 모든 순서를 무작정 시험할 필요가 없습니다.

다리를 몇 개 추가하면 가능한 문제가 될까

쾨니히스베르크 그래프에는 홀수 차수 꼭짓점이 4개 있습니다. 두 홀수 꼭짓점 사이에 새 변 하나를 추가하면 두 꼭짓점의 차수가 각각 1씩 늘어 짝수가 됩니다. 나머지 홀수 꼭짓점은 2개가 남으므로 열린 오일러 경로가 가능해질 수 있습니다. 단, 새 다리가 실제로 어느 육지를 연결하는지와 전체 연결 상태도 함께 확인해야 합니다.

홀수 꼭짓점 4개를 두 쌍으로 묶어 변 2개를 추가하면 모든 차수를 짝수로 만들 수 있으므로 닫힌 오일러 회로를 구성할 수 있습니다. 일반적으로 홀수 차수 꼭짓점이 2k개인 연결 그래프에서 모든 차수를 짝수로 만들려면 홀수 꼭짓점들을 적절히 짝지어야 합니다. 실제 우편 배달이나 도로 점검에서는 이미 있는 길을 일부 다시 지나 최소 비용으로 모든 길을 순회하는 중국인 우편배달부 문제로 이어집니다.

도로망에서는 연결 하나가 전체 흐름을 바꾸기도 한다

오일러 경로는 각 도로를 한 번씩 지나야 하는 점검·순찰 문제와 직접 연결됩니다. 반면 운전자들이 각자 가장 빠른 길을 고르는 교통 문제에서는 새 도로가 생겼다고 전체 통행 시간이 반드시 줄지 않습니다. 브라에스의 역설에서 새 도로가 혼잡을 키우는 원리는 같은 네트워크라도 질문에 따라 필요한 수학이 달라짐을 보여 줍니다.

사람 사이의 관계를 꼭짓점과 변으로 나타낼 수도 있습니다. 친선의 역설에서 친구 수가 많은 사람이 표본에 더 자주 잡히는 이유는 꼭짓점의 차수 자체가 관측 확률에 영향을 주는 사례입니다. 쾨니히스베르크 문제에서는 차수의 짝홀이 핵심이고, 친선의 역설에서는 차수 분포와 가중 평균이 핵심이라는 차이가 있습니다.

한붓그리기 판정에서 자주 하는 실수

• 홀수 차수 꼭짓점만 세고 그래프가 연결되어 있는지 확인하지 않습니다.
• 선이 교차하는 모든 지점을 무조건 꼭짓점으로 셉니다.
• 모든 변을 한 번씩 쓰는 오일러 경로와 모든 꼭짓점을 한 번씩 방문하는 해밀턴 경로를 혼동합니다.
• 홀수 꼭짓점이 2개인데 짝수 꼭짓점에서 출발합니다.
• 출발점으로 돌아와야 하는 문제에서 홀수 꼭짓점 2개도 가능하다고 판단합니다.
• 다중 변이나 고리 변의 차수를 잘못 셉니다. 고리 하나는 같은 꼭짓점의 차수에 2를 더합니다.

그림을 보고 감으로 선을 여러 번 그어 보는 것보다 꼭짓점을 표시하고 차수를 적는 편이 빠릅니다. 홀수 꼭짓점이 4개 이상이면 경로 순서를 찾기 전에 불가능하다고 판정할 수 있습니다. 0개나 2개라면 연결성을 확인한 뒤 히어홀처 알고리즘으로 실제 순서를 구성하면 됩니다.

쾨니히스베르크 다리 문제 FAQ

쾨니히스베르크의 일곱 다리는 실제로 한 번씩 건널 수 있었나요?

역사적 배치에서는 불가능했습니다. 육지 4곳의 차수가 5, 3, 3, 3으로 모두 홀수였기 때문입니다. 오일러 경로가 있으려면 홀수 차수 꼭짓점이 0개 또는 2개여야 합니다.

홀수 차수 꼭짓점이 0개면 어디에서 시작해야 하나요?

변이 있는 연결 그래프라면 어느 꼭짓점에서 시작해도 닫힌 오일러 회로를 구성할 수 있습니다. 다만 임의로 변을 고르다 보면 중간에 곤란해질 수 있으므로 경로를 확실히 만들려면 히어홀처 알고리즘을 사용하는 편이 안전합니다.

홀수 차수 꼭짓점이 정확히 2개면 어디서 시작하나요?

두 홀수 차수 꼭짓점 가운데 하나에서 시작해 다른 하나에서 끝나야 합니다. 짝수 차수 꼭짓점에서 출발하면 두 홀수 꼭짓점을 모두 경로의 중간에 처리해야 하므로 완주할 수 없습니다.

홀수 차수 꼭짓점이 4개라면 어느 두 점에서 시작하고 끝내면 되나요?

어느 두 점을 골라도 불가능합니다. 출발점과 도착점으로 처리할 수 있는 홀수 꼭짓점은 두 개뿐이고, 나머지 두 개가 중간 꼭짓점으로 남기 때문입니다. 선을 추가하거나 일부 선을 다시 지나도록 조건을 바꾸어야 합니다.

홀수 차수 꼭짓점이 0개 또는 2개이면 항상 가능한가요?

그래프의 변이 있는 부분이 하나로 연결되어 있다는 조건까지 만족해야 합니다. 서로 떨어진 두 도형은 모든 꼭짓점의 차수가 짝수여도 펜을 떼지 않고 한 번에 그릴 수 없습니다.

쾨니히스베르크 다리 문제 핵심 정리

한붓그리기 문제는 그림을 유한 무방향 그래프로 바꾸면 명확하게 판정할 수 있습니다. 변이 있는 모든 꼭짓점이 연결되어 있고 홀수 차수 꼭짓점이 0개면 닫힌 오일러 회로가 존재합니다. 홀수 차수 꼭짓점이 정확히 2개면 두 홀수 꼭짓점을 양 끝으로 하는 열린 오일러 경로가 존재합니다. 4개 이상이면 모든 변을 정확히 한 번씩 지나는 경로는 없습니다.

필요조건은 중간 꼭짓점에서 들어오는 변과 나가는 변이 쌍을 이룬다는 사실로 증명됩니다. 충분조건은 모든 차수가 짝수인 경우 닫힌 경로를 만들고 남은 경로를 차례로 끼워 넣는 히어홀처 방식으로 증명할 수 있습니다. 홀수 꼭짓점이 2개인 경우에는 두 점 사이에 임시 변을 추가해 짝수 차수 문제로 바꾼 뒤 그 변을 제거하면 됩니다. 쾨니히스베르크에는 홀수 꼭짓점이 4개였으므로 문제의 답은 불가능입니다.

참고 자료

• Euler Archive, Solutio problematis ad geometriam situs pertinentis
• Leonhard Euler, Solution of a Problem in the Geometry of Position 영문 번역
• Mathematical Association of America, Euler’s Solution to the Königsberg Bridge Problem
• Whitman College, Euler Circuits and Walks
• Wolfram MathWorld, Eulerian Graph