일곱 다리 산책 퍼즐 하나로 그래프 이론을 연, 1736년 오일러
강 가운데 섬이 있고, 땅과 땅 사이에 일곱 개의 다리가 놓여 있습니다. 모든 다리를 꼭 한 번씩만 건너며 산책할 수 있을까요?
다리의 문제는 지도가 아니라 점과 선의 문제다.
Experiment
직접 만져보기
👇 먼저 출발할 땅을 탭하세요
📖 더 읽기 — 왜 필요한가 · 인사이트 · 흔한 오해 · 수식 정리펼치기 ▾
Why
왜 필요한가
18세기 프로이센의 도시 쾨니히스베르크(지금의 칼리닌그라드)에는 강 가운데 섬과 일곱 개의 다리가 있었습니다. 시민들 사이에 퍼즐 하나가 유행했어요. 모든 다리를 꼭 한 번씩만 건너는 산책이 가능할까?
1736년, 수학자 레온하르트 오일러는 다리를 한 번도 건너보지 않고 답을 냈습니다. 땅의 모양도 다리의 길이도 다 지우고, 땅은 점으로 다리는 선으로 바꾼 것이에요. 문제에 정말 필요한 정보만 남긴 압축이었습니다.
그 압축된 그림 위에서 답은 간단해졌어요. 각 점에 붙은 선의 수만 세면 됩니다. 이 한 수가 그래프 이론의 시작이었고, 오늘날 네트워크를 다루는 모든 수학의 뿌리가 되었습니다.
Insight
영상에서 말한 인사이트
“오일러는 다리를 건너지 않고 지도를 다시 그렸다.”
수백 번 걸어보는 대신, 문제를 다른 표현으로 바꾸는 것이 수학의 힘입니다. 땅의 크기와 다리의 길이는 산책의 성패와 무관해요. 점과 선만 남기면 답이 보입니다.
“홀수 점 하나가 산책 전체의 운명을 정한다.”
지나가는 점에서는 들어온 만큼 나가야 하니 선이 짝수로 필요합니다. 홀수 점이 허용되는 자리는 출발점과 도착점, 딱 두 곳뿐이에요. 쾨니히스베르크는 홀수 점이 넷이라 불가능했습니다.
Misconception
사람들이 흔히 하는 오해
출발점과 순서만 잘 고르면 언젠가는 성공할 수 있다.
몇 번을 해도 불가능합니다. 네 땅덩이 모두 홀수 개의 다리와 이어져 있어서예요. 홀수 점에서는 들어오고 나가는 짝이 맞지 않는데, 그런 점이 네 개나 되니 출발과 도착으로도 감당이 안 됩니다.
이런 산책 퍼즐은 수학이 아니라 그냥 심심풀이 놀이다.
오일러는 이 퍼즐에서 그래프 이론이라는 새 수학을 열었습니다. 지하철 노선도, 인터넷 망, 배달 경로, DNA 해독까지 모두 그 후손이에요. 문제를 점과 선으로 압축하는 눈이 핵심이었습니다.
Formula
수식으로 정리하기
실험에서 몸으로 겪은 '막힘'을 수학의 언어로 쓰면 이렇습니다. 점에 붙은 선의 수를 차수라고 부르고, 차수가 홀수인 점의 개수가 산책의 가능 여부를 정해요.
🔬 공식 해부 — 게임에서 겪은 것과 짝지어 보기
⇔
차수
점 하나의 연결 상태를 숫자 하나로 요약합니다. 쾨니히스베르크의 네 점은 차수가 5, 3, 3, 3이었어요.
오일러의 조건
모든 선을 한 번씩 지나는 길이 존재할 조건입니다. 홀수 점이 2개면 그 두 점이 출발과 도착이에요.
악수 정리
선 하나가 양 끝 점의 차수를 1씩 올리므로, 차수의 합은 항상 짝수입니다. 그래서 홀수 점은 언제나 짝수 개로만 존재해요.
In Real Life
현실에서 만나는 곳
지하철 노선도
실제 지형을 지우고 역과 연결만 남긴 지도가 노선도입니다. 오일러가 쾨니히스베르크에 한 압축과 정확히 같아요.
배달과 제설 경로
모든 골목을 한 번씩 지나는 최단 경로를 찾는 우편배달부 문제의 출발점이 오일러의 조건입니다. 홀수 점이 많을수록 같은 길을 다시 지나야 해요.
네트워크와 회로 설계
인터넷 망, 전력망, 회로 기판의 배선 검사까지 점과 선의 수학으로 설계하고 진단합니다.
DNA 해독
잘게 읽힌 DNA 조각들을 이어 붙여 유전체를 복원하는 알고리즘이 오일러 경로를 씁니다. 1736년의 산책이 생명과학 속에서 일하고 있어요.
Practice
풀어보기 — 유형 정복
✏️ 유형별 문제 4개 — 스스로 풀어 정복하기탭해서 문제 풀기 ▾
펜을 떼지 않고 모든 선을 한 번씩 그리려면(한붓그리기), 어떤 조건이 필요할까요?
1736년 쾨니히스베르크의 지도에서, 차수가 홀수인 땅덩이는 몇 개였을까요?
홀수 점이 정확히 2개인 그림을 한붓그리기 하려면, 어디에서 출발해야 할까요?
다리(선) 하나를 새로 놓으면 차수는 어떻게 변할까요?
Watch
관련 유튜브 영상
Connection
개념은 이어진다
이전 개념
다음 개념으로 연결
Related
함께 보면 좋은 실험실
관련 실험실
관련 실험실