한붓그리기와 오일러 경로, 쾨니히스베르크의 다리 문제

한붓그리기와 오일러 경로, 쾨니히스베르크의 다리 문제

어릴 적, 종이 위에 펜을 떼지 않고 한 번에 도형을 그리는 ‘한붓그리기’ 놀이를 해본 적 있으신가요? 어떤 그림은 쉽게 성공하지만, 어떤 그림은 아무리 시도해도 실패하곤 합니다. 혹시 ‘왜 어떤 건 되고, 어떤 건 안 될까?’ 하는 궁금증을 가져본 적 없으신가요? 단순한 어린이 놀이처럼 보이는 이 문제 속에는 사실 세상을 움직이는 중요한 수학적 원리가 숨어 있습니다. 이 글에서는 쾨니히스베르크의 다리라는 유명한 실제 이야기로부터 시작해, 한붓그리기의 비밀인 ‘오일러 경로’에 대해 초보자도 쉽게 이해할 수 있도록 파헤쳐 보겠습니다. 이 원리를 알면 여러분도 한붓그리기 마스터가 될 수 있습니다.

쾨니히스베르크의 다리, 풀리지 않는 수수께끼

1. 모든 다리를 한 번씩만 건널 수 있을까?

오래전 프로이센에 있던 쾨니히스베르크(현재는 러시아의 칼리닌그라드)라는 도시에는 강이 흐르고 있었습니다. 이 강은 도시를 네 개의 지역으로 나누었고, 이 지역들은 총 일곱 개의 다리로 연결되어 있었습니다. 당시 시민들 사이에서는 ‘한 지점에서 출발하여 일곱 개의 다리를 모두 딱 한 번씩만 건너 처음 위치로 돌아올 수 있을까?’하는 문제가 유행처럼 번졌습니다. 수많은 사람이 이 도전을 시도했지만, 아무도 성공하지 못했습니다. 이 문제는 단순한 산책 코스 찾기를 넘어 도시의 큰 수수께끼가 되었습니다.

2. 위대한 수학자 오일러의 등장

이 흥미로운 소문은 18세기 최고의 수학자 중 한 명인 레온하르트 오일러의 귀에까지 들어갔습니다. 오일러는 이 문제가 다리의 길이나 위치 같은 복잡한 정보와는 관계가 없다는 사실을 간파했습니다. 그에게 중요했던 것은 오직 ‘어떤 지역이 다른 지역과 몇 개의 다리로 연결되어 있는가’였습니다. 그는 실제 지도를 매우 단순한 그림, 즉 점과 선으로 이루어진 그림으로 바꾸어 문제의 본질을 꿰뚫어 보았습니다. 이것이 바로 ‘그래프 이론’이라는 새로운 수학 분야가 탄생하는 순간이었습니다.

3. 문제의 핵심, 점과 선으로 단순화하기

오일러의 접근법은 혁신적이었습니다. 그는 네 개의 육지 지역을 각각 하나의 ‘점’으로 표시했습니다. 그리고 두 지역을 연결하는 일곱 개의 다리를 이 점들을 잇는 ‘선’으로 표현했습니다. 이렇게 복잡한 실제 지도는 네 개의 점과 일곱 개의 선으로 이루어진 아주 간단한 그림으로 바뀌었습니다. 이제 ‘모든 다리를 한 번씩 건너는 문제’는 ‘모든 선을 딱 한 번씩만 지나가는 그림 그리기’, 즉 우리가 아는 한붓그리기 문제와 똑같아졌습니다. 이 단순화 덕분에 누구든 문제의 핵심을 쉽게 파악할 수 있게 되었습니다.

한붓그리기의 비밀, 오일러 경로의 조건

1. '홀수점'과 '짝수점'이란 무엇일까?

오일러는 한붓그리기가 가능한지 알아내는 아주 간단한 규칙을 발견했습니다. 먼저 각 ‘점’에 연결된 ‘선’의 개수를 세어보는 것입니다. 만약 어떤 점에 연결된 선의 개수가 짝수(2개, 4개, 6개 등)이면 그 점을 ‘짝수점’이라 부릅니다. 반대로 연결된 선의 개수가 홀수(1개, 3개, 5개 등)이면 ‘홀수점’이라고 합니다. 예를 들어, 삼각형의 꼭짓점은 각 점에 선이 2개씩 연결되어 있으니 모두 짝수점입니다. 이 간단한 구분이 한붓그리기 가능 여부를 결정하는 열쇠가 됩니다.

2. 모든 점이 '짝수점'일 때: 완벽한 순환

만약 그림의 모든 점이 ‘짝수점’이라면, 한붓그리기는 완벽하게 가능합니다. 심지어 어느 점에서 출발하든 모든 선을 지나고 나서 정확히 처음 출발했던 점으로 돌아올 수 있습니다. 이것을 ‘오일러 회로’라고 부릅니다. 짝수점은 마치 문이 여러 개 달린 방과 같습니다. 하나의 문으로 들어가면 항상 다른 문으로 나갈 수 있기 때문에 길을 잃거나 막힐 일이 없는 것과 같은 원리입니다. 원이나 사각형 같은 도형이 대표적인 예시입니다.

3. '홀수점'이 두 개일 때: 출발과 도착이 다른 여정

그림에 ‘홀수점’이 딱 두 개만 존재할 때도 한붓그리기는 가능합니다. 하지만 이때는 조건이 붙습니다. 반드시 두 홀수점 중 한 곳에서 그림을 그리기 시작해야 하며, 그림을 마치면 항상 나머지 다른 홀수점에서 끝나게 됩니다. 출발점과 도착점이 달라지는 것이죠. 이때의 경로를 ‘오일러 경로’라고 합니다. 홀수점은 마치 여행의 시작점과 끝점처럼 정해져 있는 셈입니다. 그 외의 모든 짝수점들은 그저 지나쳐 가는 경유지에 불과합니다.

4. '홀수점'이 두 개보다 많을 때: 절대 불가능한 도전

만약 그림 안에 ‘홀수점’이 네 개, 여섯 개 등 두 개를 초과하여 존재한다면 한붓그리기는 절대로 불가능합니다. 왜냐하면 시작점과 끝점이 될 수 있는 홀수점이 너무 많기 때문입니다. 출발점과 도착점으로 사용할 두 개의 홀수점을 제외한 나머지 홀수점들에서는 들어오거나 나가는 길이 짝이 맞지 않아 결국 선이 남거나 끊기게 됩니다. 이 간단한 규칙만 알면 어떤 복잡한 그림이라도 한붓그리기가 가능한지 즉시 판단할 수 있습니다.

우리 주변에서 만나는 오일러 경로

1. 쾨니히스베르크 문제의 정답

이제 오일러의 규칙을 쾨니히스베르크 다리 문제에 적용해 봅시다. 지도를 단순화한 그림에서 네 개의 점(육지)에 연결된 선(다리)의 개수를 세어보면 각각 3개, 3개, 3개, 5개였습니다. 놀랍게도 네 개의 점 모두가 ‘홀수점’이었습니다. 홀수점이 두 개를 초과하는 네 개나 있었기 때문에, 오일러는 이 문제의 답이 ‘절대 불가능하다’는 것을 수학적으로 명쾌하게 증명했습니다. 시민들이 왜 그토록 실패했는지에 대한 이유가 마침내 밝혀진 것입니다.

2. 도시 계획과 네트워크 최적화

오일러 경로는 단순한 퍼즐 풀이에 그치지 않고 현대 사회에서도 매우 유용하게 쓰입니다. 예를 들어, 우편배달부나 쓰레기 수거 차량이 모든 거리를 한 번씩만 지나면서 최소한의 경로로 이동하고자 할 때 이 원리가 사용됩니다. 도로망을 점과 선으로 이루어진 그래프로 보고, 오일러 경로를 찾는 것은 연료와 시간을 절약하는 최적의 해법이 됩니다. 도시 계획가들은 효율적인 도로망을 설계할 때 이 원리를 참고하기도 합니다.

3. 복잡한 회로 설계와 유전자 배열

더 나아가 첨단 기술 분야에서도 오일러 경로의 원리가 빛을 발합니다. 반도체 칩 내부의 복잡한 전자 회로를 설계할 때, 수많은 연결선을 효율적으로 배치하는 과정에 응용됩니다. 또한, 인간의 유전자 지도를 완성한 ‘인간 게놈 프로젝트’에서도 핵심적인 역할을 했습니다. 수많은 짧은 DNA 조각들을 순서에 맞게 하나로 이어 붙이는 과정이 거대한 그래프에서 오일러 경로를 찾는 문제와 매우 유사했기 때문입니다. 이처럼 한붓그리기의 원리는 생명과학의 비밀을 푸는 데까지 확장되었습니다.

결론

쾨니히스베르크의 작은 도시에서 시작된 호기심은 레온하르트 오일러라는 위대한 수학자를 통해 ‘그래프 이론’이라는 새로운 학문의 문을 열었습니다. 그리고 그 핵심 원리인 ‘오일러 경로’는 한붓그리기라는 놀이의 비밀을 풀어주었을 뿐만 아니라, 오늘날 도시 계획, 통신 네트워크, 생명 공학에 이르기까지 우리 생활과 밀접한 여러 분야에서 문제를 해결하는 강력한 도구가 되었습니다. 결국, 세상의 복잡한 문제들도 본질을 꿰뚫어 보면 ‘홀수점과 짝수점’처럼 의외로 단순한 규칙으로 설명될 수 있다는 사실을 보여줍니다. 이제 어떤 도형을 보더라도, 여러분은 그것이 한 번에 그려질 수 있는지 없는지 단번에 알아차릴 수 있을 것입니다.