그래프 — 점과 선으로 세상 그리기

1736년 쾨니히스베르크. 강 위에 다리가 7개 있었고, 시민들 사이에 이런 내기가 돌았습니다. "모든 다리를 딱 한 번씩만 건너 원래 자리로 돌아올 수 있을까?"

오일러는 이 문제를 풀면서 지도를 지웠습니다. 땅의 모양도, 다리의 길이도 상관없어요. 중요한 것은 어디가 어디와 이어져 있는가뿐입니다. 땅을 점으로, 다리를 선으로 바꾸자 문제가 이렇게 변했습니다.

"이 그림을 한붓그리기할 수 있는가?"

이것이 그래프 이론의 시작입니다. 그래프 G = (V, E) 에서 V는 정점의 집합, E는 간선의 집합 — 9강에서 배운 관계를 그림으로 그린 것이에요.

🎮 한붓그리기에 도전해 보세요

점을 이어 그래프를 만들고 한붓그리기가 되는지 확인해 보세요. 홀수 차수 정점의 개수만 세면 답이 나옵니다 — 그려 보지 않고도요.

오일러의 답 — 홀수 점을 세라

어떤 점을 지나간다는 것은 들어왔다가 나간다는 뜻, 즉 선 2개를 쓴다는 뜻입니다. 그러니 출발점과 도착점을 뺀 모든 점은 차수가 짝수여야 해요.

• 홀수 차수 정점이 0개 → 한붓그리기 가능, 제자리로 돌아옴 (오일러 회로)
• 홀수 차수 정점이 2개 → 한붓그리기 가능, 한 홀수 점에서 출발해 다른 홀수 점에서 끝
• 그 외 → 불가능

쾨니히스베르크는 네 땅이 모두 홀수 차수였습니다. 그래서 불가능. 수백 명이 헛수고하던 문제를 오일러는 세어 보는 것만으로 끝냈습니다.