수학·컴퓨터

그래프 이론의 오일러 경로와 한붓그리기 문제의 해법

쾨니히스베르크의 일곱 개 다리를 한 번씩만 건너는 방법이 왜 존재할 수 없는지 증명하며 현대 위상수학과 네트워크 과학의 문을 연 오일러 경로의 수학적 원리를 탐구한다.

편집부 · 2026년 11월 18일 · 읽는 데 4분

점과 선으로 연결된 추상적인 수학적 그래프 네트워크 구조
점과 선으로 연결된 추상적인 수학적 그래프 네트워크 구조

18세기 동프로이센의 도시 쾨니히스베르크(현재의 러시아 칼리닌그라드)를 가로지르는 프레겔강에는 두 개의 큰 섬과 본토를 연결하는 일곱 개의 다리가 놓여 있었다. 당시 도시 주민들은 산책할 때 일곱 개의 다리를 각각 단 한 번씩만 건너서 원래 출발한 장소로 되돌아올 수 있는지에 대한 흥미로운 수수께끼를 풀고자 몰두하였다. 수많은 사람이 직관과 시행착오를 거듭하며 답을 찾으려 했으나, 그 누구도 명쾌한 산책 경로를 찾아내지 못하였다.

프레겔강을 가로지르는 일곱 개의 다리와 섬을 나타낸 고지도 모식도

이 난제에 종지부를 찍은 인물은 스위스의 천재 수학자 레온하르트 오일러였다. 오일러는 1736년 발표한 논문에서 실제 강의 너비나 다리의 길이, 지형의 세부 형상과 같은 물리적 조건은 문제 해결에 아무런 영향을 주지 않는다는 통찰을 제시하였다. 그는 강으로 둘러싸인 육지를 하나의 점(정점, Vertex)으로 축약하고, 육지를 연결하는 다리를 선(간선, Edge)으로 단순화하여 수학적 대상인 '그래프'를 최초로 정의하였다.

정점의 차수와 오일러 경로의 존재 조건

오일러는 그래프 위의 모든 간선을 빠짐없이 한 번씩만 지나가는 경로를 '오일러 경로'라고 명명하고, 이 경로의 존재 여부를 정점에 연결된 간선의 개수인 '차수(Degree)'를 통해 규명하였다.

어떤 정점을 방문했다가 떠나는 과정에서는 반드시 들어오는 간선 하나와 나가는 간선 하나가 짝을 이루어야 한다. 따라서 출발점과 도착점을 제외한 모든 중간 정점은 짝수 개의 간선과 연결되어 있어야 경로가 막히지 않고 연속해서 이어질 수 있다. 차수가 홀수인 정점은 경로의 시작점이 되거나 종착점이 될 수밖에 없으므로, 한붓그리기가 가능하기 위한 정점의 홀수 차수 개수는 엄격히 제한된다.

경로 유형 홀수 차수 정점의 개수 경로의 수학적 특징 실생활 응용 분야
오일러 회로 (닫힌 경로) 0개 (모든 정점의 차수가 짝수) 임의의 정점에서 출발하여 제자리로 복귀 가능 제설 차량 최적 경로, 배송 차량 순회
오일러 트레일 (열린 경로) 정확히 2개 홀수 정점에서 출발하여 다른 홀수 정점에서 종료 인쇄 회로 기판 드릴 가공 경로
한붓그리기 불가능 2개를 초과 (4개, 6개 등) 간선의 중복 없이 전체 순회 불가 네트워크 병목 지점 분석

쾨니히스베르크의 일곱 다리를 그래프로 변환하면 네 개의 육지 정점이 갖는 간선의 수는 각각 3개, 3개, 3개, 5개로 나타난다. 즉 네 개의 정점이 모두 홀수 차수를 가지므로 오일러 경로의 성립 조건인 '홀수 차수 정점 0개 또는 2개'를 충족하지 못하여 한 번씩만 건너는 경로는 절대 존재할 수 없음이 증명되었다.

평면도형의 위상적 변형과 오일러 다면체 정리

오일러의 접근법은 거리를 무시하고 연결 상태의 본질만을 탐구하는 현대 수학의 거대한 갈래인 위상수학(Topology)의 모태가 되었다.

다면체의 정점과 모서리를 기하학적으로 분해한 다이어그램

그래프 이론의 원리는 공간 속의 입체 다면체로 확장되어 '오일러의 다면체 정리'로 발전하였다. 구와 위상적으로 동형인 임의의 볼록 다면체에서 꼭짓점의 수(V), 모서리의 수(E), 면의 수(F) 사이에는 언제나 V - E + F = 2라는 불변의 관계식이 성립한다. 이 위상 불변량은 정다면체가 왜 오직 다섯 가지만 존재하는지를 증명하는 강력한 토대가 되었으며, 분자 구조의 대칭성을 규명하는 화학과 나노 기술 분야에서도 핵심 분석 도구로 쓰이고 있다.

현대 네트워크 과학과 최적화 알고리즘으로의 진화

오늘날 오일러가 정립한 그래프 이론은 단순한 퍼즐 풀이를 넘어 복잡계 네트워크를 다루는 컴퓨터 과학의 핵심 기반 기술로 확고히 자리 잡았다.

인터넷 패킷 라우팅 경로 설계, 소셜 네트워크 서비스의 친구 추천 알고리즘, 도시 가스관과 상하수도 배관망의 효율적 점검 순서 설계 등 무수한 공학적 문제가 오일러 경로 및 해밀턴 경로 알고리즘을 통해 최적화된다. 현실 세계의 복잡한 물리적 형태를 제거하고 본질적인 연결 관계에 집중했던 오일러의 추상화 사고는 3백 년이 지난 지금도 디지털 정보 혁명을 지탱하는 수학의 가장 아름다운 유산으로 빛나고 있다.

이어서 읽기