모던지 / 수학 / 이산수학 2강. 그래프 이론: 점과 선의 세계

이산수학 2강. 그래프 이론: 점과 선의 세계

다리도, 지도도, 인간관계도 점과 선으로 바꾸는 순간 같은 수학이 됩니다. 이 위대한 추상은 산책 문제 하나에서 시작됐습니다.

풀고 시작

문제 1. 18세기 쾨니히스베르크 시민들은 일곱 개의 다리를 각각 정확히 한 번씩만 건너 산책하는 길을 찾으려 했습니다. 오일러의 결론은?

오일러는 경로를 일일이 시험하는 대신 문제를 점과 선으로 추상화해, 홀수 개의 다리가 연결된 육지가 4곳이나 되므로 불가능함을 증명했습니다. 한 번에 통과하는 지점은 들어온 만큼 나가야 하므로 짝수 개의 선이 필요하다는 것이 핵심입니다.

일곱 개의 다리와 하나의 추상

프로이센의 도시 쾨니히스베르크(현재 러시아 칼리닌그라드)는 프레겔 강이 도시를 네 구역으로 나누고, 일곱 개의 다리가 그 구역들을 이었습니다. 시민들의 오락거리였던 질문은 이렇습니다. 모든 다리를 정확히 한 번씩 건너는 산책이 가능한가. 다들 이 길 저 길 걸어 보며 답을 찾았지만, 1736년 오일러는 전혀 다른 한 수를 두었습니다. 육지의 모양, 다리의 길이, 강의 폭을 전부 지워 버린 겁니다. 남은 것은 육지를 나타내는 점 4개와 다리를 나타내는 선 7개뿐이었죠. 문제의 본질과 무관한 정보를 모두 버리는 이 추상화가 그래프 이론(graph theory)의 탄생이고, 위상수학의 씨앗이기도 합니다.

그래프의 언어: 정점, 간선, 차수

그래프는 정점(vertex)의 집합과, 정점 쌍을 잇는 간선(edge)의 집합으로 정의됩니다. 한 정점에 연결된 간선의 개수를 그 정점의 차수(degree)라 하죠. 놀랍게도 이 세 단어만으로 오일러의 논증을 재구성할 수 있습니다. 산책 도중 지나치는 정점은 들어온 횟수만큼 나가야 하므로 차수가 짝수여야 합니다. 홀수 차수 정점이 허용되는 자리는 출발점과 도착점, 최대 2개뿐이죠. 따라서 모든 간선을 한 번씩 지나는 경로(오늘날 오일러 경로라 부릅니다)는 홀수 차수 정점이 0개 또는 2개일 때만 존재합니다. 쾨니히스베르크는 네 육지의 차수가 5, 3, 3, 3으로 모두 홀수였습니다. 그러므로 불가능합니다. 증명 끝.

이 언어의 힘은 범용성입니다. 지하철 노선도, 분자 구조, 웹의 하이퍼링크, 소셜 네트워크의 친구 관계는 전부 정점과 간선으로 표현됩니다. 대상이 무엇이든 연결 구조만 같으면 같은 정리가 적용되죠. 덧붙이면, 모든 정점의 차수를 더한 값은 간선 수의 두 배라는 악수 정리도 여기서 바로 나옵니다. 간선 하나가 양쪽 끝에서 한 번씩 세어지기 때문입니다.

4색 정리와 컴퓨터 증명 논쟁

1852년 프랜시스 구드리는 영국 지도를 색칠하다 추측 하나를 떠올렸습니다. 어떤 지도든 인접한 나라를 다른 색으로 칠하는 데 네 가지 색이면 충분한가. 지도를 그래프로 바꾸면(나라가 정점, 국경 공유가 간선) 이것은 그래프 색칠 문제가 됩니다. 1879년 켐페가 증명을 발표해 11년간 인정받았으나, 1890년 히우드가 치명적 오류를 찾아냈습니다(켐페의 방법을 살려 5색이면 충분하다는 것까지는 증명됐죠). 최종 해결은 1976년, 아펠과 하켄이 문제를 유한한 개수의 배치 검사로 환원한 뒤 컴퓨터로 1천 시간 넘게 계산해 이뤄졌습니다.

그리고 논쟁이 시작됐습니다. 어떤 인간도 그 계산 전체를 손으로 검증할 수 없다면, 이것은 증명일까요. 철학자 타이모츠코는 1979년 논문에서 4색 정리의 "증명"이 수학적 증명의 개념 자체를 바꿔 놓았다고 주장했고, 수학자들 사이에서도 통찰 없는 증명에 대한 불만이 이어졌습니다. 2005년 곤티에가 증명 검증 프로그램 Coq로 전체 증명을 형식화하면서 오류 가능성 논란은 사실상 정리됐지만, "이해 없는 확실성"을 둘러싼 철학적 질문은 여전히 열려 있습니다. 오늘날 AI가 만드는 증명을 생각하면 이 논쟁은 오히려 더 현재적이죠.

좁은 세상: 여섯 다리 건너면 누구든

1967년 심리학자 밀그램은 네브래스카의 무작위 주민들에게 편지를 주고, 아는 사람을 통해서만 보스턴의 한 증권 중개인에게 전달하게 했습니다. 도착한 편지들이 거친 중간 단계는 평균 여섯 명 안팎이었죠. "6단계 분리"라는 통념의 출처입니다. 1998년 와츠와 스트로가츠는 이 현상을 수학적으로 해명했습니다. 규칙적인 연결망에 소수의 무작위 지름길만 섞여도, 뭉침성은 유지되면서 임의의 두 정점 사이 거리가 급격히 짧아지는 좁은 세상 네트워크(small-world network)가 됩니다. 이 모형은 전염병 확산 예측, 소셜 미디어의 정보 전파, 뇌 신경망 분석, 검색 엔진의 링크 분석까지 현대 네트워크 과학의 기반이 됐습니다. 오일러의 산책 문제에서 출발한 점과 선의 언어가, 연결된 세계 전체를 읽는 언어가 된 것이죠.

인출 문제

문제 1. 오일러가 쾨니히스베르크 문제에서 수행한 결정적 추상화는 무엇일까요?

오일러는 모양, 거리, 크기 같은 기하학적 정보를 전부 버리고 무엇이 무엇과 이어져 있는가라는 구조만 남겼습니다. 경로를 나열하는 대신 구조의 성질(차수의 홀짝)로 불가능성을 증명한 것이 그래프 이론의 출발입니다.

문제 2. 모든 간선을 정확히 한 번씩 지나는 오일러 경로가 존재하기 위한 조건은?

중간에 지나치는 정점은 들어온 만큼 나가야 하므로 짝수 차수가 필요하고, 홀수 차수가 허용되는 자리는 출발점과 도착점뿐입니다. 쾨니히스베르크는 홀수 차수 정점이 4개라 조건을 어겼죠. 정점이나 간선의 개수 자체는 기준이 아닙니다.

문제 3. 4색 정리의 1976년 증명이 촉발한 논쟁의 핵심은?

아펠과 하켄의 증명은 방대한 경우 검사를 컴퓨터에 맡겼고, 어떤 수학자도 그 전체를 손으로 확인할 수 없었습니다. 반례가 나온 적은 없으며, 2005년 Coq 형식 검증으로 오류 우려는 정리됐지만 이해 없는 확실성이라는 철학적 쟁점은 남았습니다.

문제 4. 와츠와 스트로가츠가 밝힌 좁은 세상 네트워크의 발생 원리는?

완전 연결도 완전 무작위도 아닌 중간이 핵심입니다. 이웃끼리 뭉쳐 있는 규칙적 구조에 먼 곳을 잇는 지름길이 조금만 추가되면, 뭉침성을 유지한 채 임의의 두 점 사이 거리가 크게 줄어듭니다. 밀그램의 6단계 실험이 보여 준 현상의 수학적 해명이죠.

생각해볼 질문 (정답 없음)

컴퓨터가 검증하고 인간은 이해하지 못하는 증명을 받아들인다면, 수학에서 "안다"는 것의 의미는 무엇이 될까요.

이전: 1강 조합론 · 다음: 3강 수학적 귀납법과 재귀

이 문서를 언급함

← 알고리즘과 자료구조 3강. 데이터를 어떻게 담을 것인가 ← 컴퓨터과학 ← 이산수학 1강. 조합론: 세는 법의 과학 ← 이산수학 3강. 수학적 귀납법과 재귀 ← 수학

모던지 · 궁금하면 모던지 GitHub · 2026-09-10