천재 수학자 오일러는 어떻게 200년 묵은 난제를 풀었을까?

 

'한붓그리기'가 가능할까? 쾨니히스베르크의 다리 문제에서 시작된 그래프 이론의 탄생! 천재 수학자 오일러가 어떻게 이 문제를 해결하고 새로운 수학의 지평을 열었는지 알아봅니다.

 

옛 프로이센의 아름다운 도시 쾨니히스베르크에는 프레겔강이 흐르고 있었고, 강 위에는 도시의 각 지역을 잇는 7개의 다리가 있었습니다. 이 도시의 시민들은 오랜 시간 동안 한 가지 소박한 퍼즐을 풀려고 애썼죠. "산책을 나갈 때, 7개의 다리를 모두 딱 한 번씩만 건너서 출발점으로 돌아올 수 있을까?"

수많은 사람이 도전했지만 아무도 성공하지 못했고, 그 이유 또한 명확히 설명하지 못했습니다. 이 소소한 궁금증이 18세기 최고의 수학자, **레온하르트 오일러(Leonhard Euler)**의 귀에 들어가면서, 현대 수학과 컴퓨터 과학의 거대한 한 분야인 **'그래프 이론(Graph Theory)'**이 탄생하는 계기가 됩니다. 🤓

 

🤔 오일러의 천재적 발상: 본질만 남기기

오일러는 이 문제를 접하고, 다리의 길이, 강의 폭, 육지의 모양 같은 세부 정보는 전혀 중요하지 않다는 사실을 간파했습니다. 문제의 핵심은 오직 **'어떤 육지에서 어떤 육지로 다리가 연결되어 있는가'** 뿐이었죠.

그는 각 육지(A, B, C, D)를 **점(Vertex)**으로, 다리들을 점과 점을 잇는 **선(Edge)**으로 단순화했습니다. 이렇게 현실의 복잡한 문제를 점과 선의 연결 관계로 추상화한 것이 바로 '그래프'입니다. 쾨니히스베르크 다리 문제는 아래와 같은 간단한 그래프로 변신했습니다.

쾨니히스베르크 다리 문제의 그래프 표현

이제 문제는 "이 그래프의 모든 선(다리)을 딱 한 번씩만 지나서 그릴 수 있는가?"라는 '한붓그리기' 문제로 바뀌었습니다.

 

✨ 해답의 열쇠: 꼭짓점의 '차수(Degree)'

오일러는 한붓그리기가 가능한지를 판단하는 결정적인 단서가 각 꼭짓점에 연결된 변의 개수, 즉 **'차수(Degree)'**에 있음을 발견했습니다.

생각해보세요. 어떤 꼭짓점을 지나갈 때 우리는 그 점으로 들어오는 선 하나와 나가는 선 하나, 즉 2개의 선을 사용하게 됩니다. 따라서 출발점과 도착점이 아닌 중간에 있는 모든 꼭짓점들은 항상 짝수 개의 선(짝수 차수)을 가져야만 합니다.

💡 오일러 경로 & 오일러 회로의 조건
오일러는 이 통찰을 바탕으로 다음과 같은 명쾌한 규칙을 만들어냈습니다.

• 오일러 경로 (Eulerian Path): 모든 선을 한 번씩 지나는 경로. 홀수 차수인 꼭짓점이 0개 또는 2개일 때만 존재합니다. (홀수점이 2개라면, 그 두 점이 각각 경로의 시작점과 끝점이 됩니다.)
• 오일러 회로 (Eulerian Circuit): 모든 선을 한 번씩 지나고 출발점으로 돌아오는 경로. 모든 꼭짓점의 차수가 짝수일 때만 존재합니다.

그렇다면 쾨니히스베르크 문제의 답은? 각 육지(꼭짓점)에 연결된 다리(선)의 개수를 세어봅시다. A는 5개, B는 3개, C는 3개, D는 3개... 네 개의 꼭짓점 모두 차수가 홀수입니다! 오일러의 규칙에 따르면 홀수 차수 꼭짓점이 2개를 초과하므로, 오일러 경로는 존재하지 않습니다. 따라서 한붓그리기는 불가능합니다.

 

👩‍💻 현대 사회를 움직이는 그래프 이론

오일러의 발견은 단순한 퍼즐 풀이를 넘어, 점과 선으로 세상을 분석하는 '그래프 이론'의 시초가 되었습니다. 오늘날 이 이론은 우리 삶 곳곳에서 핵심적인 역할을 하고 있습니다.

오일러 경로의 현대적 활용 예시

• 최적 경로 탐색: 우편 배달부, 쓰레기 수거차, 도로 청소차가 모든 거리를 한 번씩만 지나도록 경로를 짜는 데 활용됩니다.
• 네트워크 설계: 통신 네트워크나 회로 기판에서 모든 연결을 효율적으로 검사하는 경로를 설계할 때 사용됩니다.
• 유전체학: DNA 염기서열을 재구성할 때, 잘게 잘린 DNA 조각(선)들을 이어 붙여 전체 서열(경로)을 찾는 문제에 응용됩니다.

 

📝 마무리: 문제를 꿰뚫어 본 통찰의 힘

쾨니히스베르크의 다리 문제는 오일러의 손을 거쳐 단순한 지역적 퍼즐에서 보편적인 수학 원리로 승화되었습니다. 복잡한 현실에서 핵심 구조를 꿰뚫어 보고, 그것을 단순한 모델로 표현해 내는 그의 통찰력은 오늘날 우리에게도 큰 영감을 줍니다.

혹시 주변에 한붓그리기가 가능한 그림이나 구조물이 있는지 찾아보는 건 어떨까요? 오늘 배운 '차수'의 비밀을 이용하면 금방 답을 찾을 수 있을 거예요! 궁금한 점은 언제든 댓글로 남겨주세요! 😊

💡

오일러 경로 핵심 요약

✨ 문제의 시작: 쾨니히스베르크의 7개 다리 건너기 퍼즐에서 출발했습니다.

📊 핵심 아이디어: 현실 문제를 점(Vertex)과 선(Edge)으로 이루어진 그래프로 추상화했습니다.

🧮 해결의 열쇠: 각 꼭짓점에 연결된 선의 개수인 '차수(Degree)'가 짝수인지 홀수인지가 한붓그리기의 가능성을 결정합니다.

👩‍💻 오일러 경로 조건: 홀수 차수 꼭짓점이 0개 또는 2개일 때만 존재하며, 이는 현대의 경로 탐색, 네트워크 설계 등 다양한 분야에 응용됩니다.

복잡한 현상의 본질을 파악하면 문제는 의외로 간단해집니다.

자주 묻는 질문 ❓

Q: 오일러 경로와 오일러 회로의 정확한 차이점은 무엇인가요?

A: '오일러 경로'는 그래프의 모든 선을 한 번씩만 지나가는 경로를 의미하며, 시작점과 끝점이 달라도 괜찮습니다. 반면 '오일러 회로'는 모든 선을 한 번씩 지나되, 반드시 출발했던 점으로 다시 돌아와야 하는 경로를 말합니다. 따라서 오일러 회로는 오일러 경로의 더 특별한 경우라고 할 수 있습니다.

Q: '한붓그리기'가 오일러 경로와 같은 말인가요?

A: 네, 거의 같은 개념으로 사용됩니다. '한붓그리기'는 연필을 떼지 않고 모든 선을 한 번씩만 그려 도형을 완성하는 것을 말하죠. 이는 수학적으로 그래프의 모든 변을 한 번씩만 통과하는 '오일러 경로' 또는 '오일러 회로'를 찾는 문제와 동일합니다.

Q: 오일러 경로를 찾는 구체적인 알고리즘도 있나요?

A: 네, 있습니다. 대표적으로 '플뢰리 알고리즘(Fleury's Algorithm)'이 있습니다. 이 알고리즘의 핵심은 '다음에 건널 선을 선택할 때, 그 선을 지워도 나머지 그래프가 두 동강 나지 않는 선을 우선적으로 선택하라'는 것입니다. 이 규칙을 따르면 막다른 길에 빠지지 않고 오일러 경로를 찾을 수 있습니다.

Q: 모든 꼭짓점의 차수가 홀수인 그래프는 존재할 수 있나요?

A: 불가능합니다. 그래프 이론에는 '악수 보조정리(Handshaking Lemma)'라는 중요한 정리가 있는데, 이는 그래프의 모든 꼭짓점의 차수를 전부 더하면 항상 (총 변의 개수 × 2)가 된다는 내용입니다. 즉, 차수의 총합은 항상 짝수여야 합니다. 따라서 홀수 차수를 가진 꼭짓점의 개수는 항상 짝수 개(0, 2, 4, ...)일 수밖에 없습니다.

Q: 레온하르트 오일러는 어떤 수학자인가요?

A: 오일러는 18세기 스위스 출신의 수학자이자 물리학자로, 역사상 가장 생산적인 수학자로 꼽힙니다. 그는 해석학, 정수론, 그래프 이론, 역학, 천문학 등 수학과 과학의 거의 모든 분야에 걸쳐 방대한 업적을 남겼습니다. 우리가 현재 사용하는 많은 수학 기호들(π, e, i, Σ, f(x) 등)이 그에 의해 정립되었습니다.