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