← 갤러리
그래프 이론

일곱 다리의 도시

쾨니히스베르크의 일곱 다리를 한 번씩만 건너 산책할 수 있을까요? 오일러는 지도를 지우고 점과 선만 남겨 답했습니다. 그 점과 선이 오늘은 지하철 노선도와 길 찾기, 인간관계, 검색 엔진을 떠받칩니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 다리와 점은 누르거나 끌 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

18세기 초 프로이센의 쾨니히스베르크는 발트해로 흘러드는 프레겔강 하구의 무역 도시였습니다. 강은 시내에서 두 갈래로 갈라졌다가 다시 합쳐졌고, 그 사이에 섬이 둘 있었습니다. 섬과 양쪽 강변은 일곱 개의 다리로 이어져 있었습니다. 이 도시에서는 이런 물음이 돌았다고 전합니다. 일곱 다리를 모두, 한 번씩만 건너서 산책할 수 있을까? 어디서 출발해도 되고, 출발점으로 돌아오지 않아도 됩니다. 그런 길을 찾은 사람은 없었지만, 그런 길이 없다고 증명한 사람도 없었습니다.

쾨니히스베르크는 13세기에 튜튼 기사단이 세운 성에서 시작했습니다. 튜튼 기사단은 십자군 시대에 생긴 독일계 기사 수도회입니다. 도시는 14세기에 북유럽 무역 도시들의 연합인 한자 동맹에 들었고, 1525년부터는 프로이센 공국의 수도였습니다. 이곳에는 1544년 알브레히트 공이 세운 알베르티나 대학이 있었고, 1701년에는 프리드리히 1세가 이곳에서 '프로이센의 왕'으로 즉위했습니다. 가운데 섬 크나이프호프에는 대성당과 대학의 옛 건물이 있었고, 강에는 배가 드나들었습니다. 섬과 강변이 모두 사람과 짐이 오가는 시가지였으니 다리가 일곱이나 필요했던 것입니다.

1 · 직접 걸어 보기일곱 다리를 한 번씩

먼저 손으로 부딪혀 봅시다. 이 절에서 볼 것은 두 가지입니다. 그런 산책이 정말 없는지, 그리고 '해 봤더니 없다'와 '왜 없는지 안다'가 어떻게 다른지입니다.

아래 그림은 18세기 쾨니히스베르크의 강과 다리를 단순하게 그린 것입니다. 북쪽과 남쪽의 강변, 대성당이 있던 크나이프호프섬, 그리고 동쪽의 롬제섬이 있습니다. 노란 점이 여러분입니다. 땅을 누르면 출발점이 바뀌고, 다리를 누르면 건넙니다. 건넌 다리는 회색으로 지워지고 다시 건널 수 없습니다.

강(파랑)과 땅(초록), 일곱 다리(갈색). 지금 있는 땅에 닿은 다리만 건널 수 있습니다. 점선은 지금까지 걸어온 길입니다.

한 걸음 되돌리기 처음부터

모든 경우를 컴퓨터로 따져 볼 수는 있습니다. 네 땅 가운데 하나에서 출발해 더 건널 다리가 없을 때까지 걷는 방법은 모두 가지이고, 그중 가장 긴 산책도 다리 개에서 멈춥니다. 그러니 답은 "안 된다"입니다. 하지만 이것은 확인일 뿐 이유가 아닙니다. 다리가 수십 개인 도시라면 경우의 수⁠(number of cases)⁠가 너무 많아 이렇게는 끝낼 수 없고, 다리를 하나 더 놓거나 허물면 답이 어떻게 바뀌는지도 이 목록은 말해 주지 않습니다.

정리하면, 모든 경우를 따져 보면 쾨니히스베르크의 산책은 불가능합니다. 남은 물음은 왜이고, 다리가 몇 개이든 한눈에 판정하는 방법이 있느냐입니다.

2 · 지도를 지우다점과 선만 남기면

이 절의 물음은 이것입니다. 경우를 하나하나 따지지 않고, 어떤 도시든 그런 산책이 되는지 안 되는지를 한눈에 가릴 기준이 있을까?

답은 이 도시가 아니라 멀리 러시아의 수도에서 나왔습니다. 레온하르트 오일러는 1735년 8월 페테르부르크 과학 아카데미에서 이 문제의 풀이를 발표했습니다. 라틴어 제목은 「위치의 기하학⁠(geometry of position)⁠에 속하는 한 문제의 풀이」였습니다. 논문은 아카데미 논문집 1736년 호로 나왔지만 실제 인쇄는 1741년에야 되었습니다. 이 아카데미는 표트르 대제가 1724년 칙령으로 세웠고, 그가 죽은 뒤인 1725년에 문을 열었습니다. 러시아에는 아직 학자가 드물어 스위스와 독일 등지에서 학자들을 불러 모았고, 스무 살의 오일러도 그렇게 1727년 바젤에서 건너왔습니다. 논문집은 유럽의 학자들이 함께 읽는 라틴어로 나왔습니다. 발트해 연안 도시의 산책 수수께끼가 편지와 논문집을 거쳐 유럽 수학의 문제가 된 셈입니다.

오일러가 쾨니히스베르크에 가 보았다는 기록은 없습니다. 문제는 편지로 오갔습니다. 1736년 봄 단치히의 시장 카를 엘러가 그곳의 수학자 하인리히 퀸을 대신해 오일러에게 이 문제를 묻고 답을 청한 편지가 남아 있습니다. 단치히는 발트해의 또 다른 항구 도시로, 오늘날 폴란드의 그단스크입니다. 오일러의 답장은 뜻밖에 시큰둥했습니다. 이 풀이는 수학과 별 관계가 없고 오직 이성에 기댈 뿐이니 왜 하필 수학자에게 기대하는지 모르겠다는 투였습니다. 같은 무렵 빈의 궁정 수학자 마리노니에게는 조금 다르게 썼습니다.

이 질문은 아주 하찮지만, 기하학도 대수학도 셈의 기술도 이것을 푸는 데 충분하지 않다는 점에서 주목할 만해 보였습니다.— 레온하르트 오일러, 조반니 마리노니에게 보낸 편지(1736)

기하학이 충분하지 않은 까닭은 이 문제에 크기가 없기 때문입니다. 다리가 얼마나 긴지, 섬이 얼마나 큰지, 강이 어느 쪽으로 굽는지는 답과 상관이 없습니다. 오일러는 논문 첫머리에서, 라이프니츠가 처음 언급했지만 거의 알려지지 않은 '위치의 기하학'이라는 분야가 있으며 이 문제가 거기에 속한다고 썼습니다. 라이프니츠는 1679년 네덜란드의 과학자 크리스티안 하위헌스에게 보낸 편지에서 길이와 각도를 재는 대신 위치 관계를 직접 계산하는 기호법을 제안했지만, 그 기호법은 구상으로 끝났습니다.

아래 그림은 1절의 도시를 그대로 옮겨 온 것이고, 걸어온 길도 이어집니다. 지도 지우기를 눌러 보세요. 땅은 점이 되고, 다리는 두 점을 잇는 선이 됩니다. 이렇게 점의 집합(모임)과 그 점들을 둘씩 잇는 선만 남긴 구조를 그래프라고 부릅니다. 점은 꼭짓점⁠(vertex)⁠, 선은 변이라고 하고, 한 꼭짓점에 붙은 변의 개수를 그 점의 차수라고 합니다.

위 그림과 같은 도시, 같은 산책입니다. 점 옆의 분홍 숫자가 차수, 곧 그 땅에 닿은 다리의 수입니다. 단추를 다시 누르면 지도로 돌아갑니다.

이제 이유가 보입니다. 산책 도중에 어떤 땅에 들어갔다가 나오면 그 땅의 다리를 두 개 씁니다. 하나로 들어오고 다른 하나로 나가니까요. 출발점도 도착점도 아닌 땅은 들어오고 나가기만 되풀이하므로, 다리를 모두 한 번씩 건너려면 그 땅의 차수가 짝수여야 합니다.

차수가 5인 크나이프호프섬으로 확인해 봅시다. 이 섬이 출발점도 도착점도 아니라면, 섬에 올 때마다 들어오는 다리 하나와 나가는 다리 하나를 씁니다. 두 번 들르면 다리 네 개를 쓰고, 다섯째 다리는 짝이 없이 남습니다. 세 번 들르려면 다리가 여섯 개 필요한데 다섯뿐입니다. 그러니 이 섬은 출발점(나가기만 하는 다리 하나가 생깁니다)이거나 도착점(들어오기만 하는 다리 하나가 생깁니다)이어야 합니다.

일반적으로 차수가 홀수인 땅은 출발점이거나 도착점일 수밖에 없습니다. 출발점과 도착점은 합쳐 둘뿐이니, 그런 땅은 많아야 둘입니다. 쾨니히스베르크의 네 땅은 차수가 5(크나이프호프섬), 3, 3, 3으로 모두 홀수입니다. 홀수 땅이 넷이니 어떻게 걸어도 안 됩니다. 다리가 수십 개여도 계산은 똑같이 짧습니다. 차수를 2로 나눈 나머지⁠(remainder)⁠, 곧 짝수인지 홀수인지만 보면 되니까요(나머지 연산).

이 논증은 거꾸로도 성립합니다. 모든 변이 한 덩어리로 이어져 있고 홀수 차수 점이 0개나 2개이면, 모든 변을 한 번씩 지나는 길이 반드시 있습니다. 이런 길을 오일러 경로⁠(Euler path)⁠, 출발점으로 돌아오는 것을 오일러 회로⁠(Euler circuit)⁠라고 합니다. 앞 문단은 '이런 길이 있으면 홀수 점은 0개나 2개'라는 방향이었고, 이 문단은 '홀수 점이 0개나 2개이면 이런 길이 있다'는 반대 방향입니다. 두 방향은 다른 주장이라 따로 증명해야 합니다.

증명의 생각은 단순합니다. 먼저 차수가 모두 짝수인 경우입니다. 아무 점에서 출발해 쓰지 않은 변을 따라 아무렇게나 걷습니다. 출발점이 아닌 점에 들어설 때마다 그 점의 변은 홀수 개(들어온 변까지 쳐서)를 쓴 상태인데 차수는 짝수이니, 나갈 변이 적어도 하나 남아 있습니다. 그래서 막혀 멈추는 곳은 반드시 출발점이고, 지나온 길은 고리가 됩니다. 아직 쓰지 않은 변이 남았으면, 그래프가 연결되어 있으니 지나온 고리 위에 쓰지 않은 변이 닿은 점이 반드시 있습니다. 거기서 같은 방법으로 새 고리를 돌아 원래 고리에 끼워 넣고, 이것을 되풀이하면 모든 변이 한 회로에 꿰어집니다. 홀수 점이 둘이면 그 두 점 사이에 가짜 변을 하나 보태 모든 차수를 짝수로 만든 뒤 회로를 찾고, 마지막에 가짜 변을 빼면 두 홀수 점을 양 끝으로 하는 경로가 남습니다.

오일러는 이 역방향을 당연하게 여기고 증명하지 않았습니다. 증명은 130여 년 뒤 카를스루에 공과대학의 사강사(대학에서 봉급 없이 강의하던 강사) 카를 히어홀처가 남겼습니다. 그는 이 증명을 동료들 앞에서 말로 설명했지만 적어 두지 못한 채 1871년 서른 살로 세상을 떠났습니다. 동료 크리스티안 비너가 그 내용을 정리해 1873년 『수학 연보』에 히어홀처의 이름으로 실었습니다.

홀수 차수 점이 하나뿐인 그래프는 있을까요? 없습니다. 변 하나는 양 끝의 두 점에 차수를 하나씩 보태므로, 모든 차수를 더하면 언제나 변의 수의 두 배입니다. 쾨니히스베르크라면 5 + 3 + 3 + 3 = 14이고, 다리는 7개이니 정확히 두 배입니다. 합이 짝수이니 홀수 차수 점도 짝수 개입니다. 짝수 차수들의 합은 짝수이므로 홀수 차수들의 합도 짝수여야 하는데, 홀수를 홀수 개 더하면 홀수가 되기 때문입니다. 모임에서 각자 악수한 횟수를 모두 더하면 악수 수의 두 배가 된다고 해서 이것을 '악수 정리⁠(handshake lemma)⁠'라고 부릅니다.

정리하면, 연결된 그래프에서 모든 변을 한 번씩 지나는 길이 있는지는 홀수 차수 점의 개수만 세면 압니다. 0개이면 제자리로 돌아오는 회로가, 2개이면 한 홀수 점에서 다른 홀수 점으로 가는 경로가 있고, 그 밖이면 없습니다. 홀수 점이 1개나 3개인 경우는 악수 정리 때문에 애초에 생기지 않습니다.

'그래프'라는 이름은 오일러보다 140년 넘게 늦게, 뜻밖에 화학에서 왔습니다. 오일러 뒤로 점과 선의 문제는 한동안 흩어진 놀이와 퍼즐로 이어졌습니다. 1771년 파리의 방데르몽드는 체스판의 나이트가 모든 칸을 한 번씩 밟는 길을 '위치의 문제'라 부르며 다뤘고, 1847년 가우스의 제자 리스팅은 '위상수학⁠(topology)⁠'이라는 말을 처음 책 제목에 썼습니다. 1857년 영국의 케일리는 미분⁠(differentiation)⁠ 연산(변화의 빠르기를 구하는 계산)을 되풀이하는 계산을 정리하다가 가지를 치는 나무 모양을 세기 시작했습니다. 1870년대에는 같은 방법으로, 탄소 원자가 n개인 탄화수소에 이성질체⁠(isomer)⁠가 몇 가지 있는지를 셌습니다. 이성질체란 분자식은 같지만 결합 모양이 다른 분자입니다. 원자를 점, 결합을 선으로 그린 화학자들의 구조식이 바로 그래프였습니다. 1878년 케일리의 친구 실베스터가 『네이처』에 쓴 글에서 이 '화학 그래프'를 줄여 graph라는 말을 쓴 것이 이름의 시작입니다. 이 흩어진 결과들을 처음 한 권의 책으로 묶은 것은 1936년 부다페스트의 쾨니그 데네시였습니다. 케일리가 나무를 센 공식은 「세지 않고 세기」에 있습니다.

1730년대 다리 문제가 오간 길. 쾨니히스베르크와 단치히는 발트해의 항구였고, 오일러는 페테르부르크에서 편지로 답했습니다. 보라 선은 반세기 전 라이프니츠가 하노버에서 파리의 하위헌스에게 '위치의 기하학'을 제안한 편지, 노란 선은 오일러가 옮겨 다닌 길입니다.

3 · 한 붓 그리기어떤 그림이든

이 절의 물음은 이것입니다. 2절의 기준은 다리가 아닌 다른 그림에도 통할까? 그리고 '모든 변을 한 번씩' 대신 '모든 점을 한 번씩'을 물으면 어떻게 될까?

오일러의 기준은 쾨니히스베르크에만 쓰이는 것이 아닙니다. 종이에서 붓을 떼지 않고, 같은 선을 두 번 긋지 않고 그림을 그리는 '한 붓 그리기'가 바로 같은 문제입니다. 그림을 골라 보세요: . 한 점에서 다른 점으로 끌면 변이 생기고, 변 가운데의 작은 점을 누르면 그 변이 지워집니다. 점 안의 숫자가 차수이고, 홀수 차수 점은 분홍, 짝수 차수 점은 청록입니다.

같은 두 점 사이에는 쾨니히스베르크의 다리처럼 변을 세 개까지 그을 수 있습니다.

▶ 한 붓에 그려 보기 처음 그림으로

변들이 두 덩어리로 떨어져 있으면 차수가 모두 짝수여도 한 붓으로 그릴 수 없습니다. 그래서 오일러의 조건에는 '연결되어 있다'는 말이 붙습니다. "변을 따라 한 점에서 다른 점으로 갈 수 있다"는 관계는 동치관계⁠(equivalence relation)⁠입니다. 어느 점이든 제자리에는 갈 수 있다고 치고, A에서 B로 갈 수 있으면 같은 길을 거꾸로 걸어 B에서 A로도 갈 수 있으며, A에서 B로, B에서 C로 갈 수 있으면 A에서 C로도 갈 수 있으니까요. 그래서 점들은 서로 오갈 수 있는 것끼리 겹치지 않는 무리로 깔끔하게 나뉘고, 그 무리 하나하나를 연결 성분⁠(connected component)⁠이라고 합니다.

비슷해 보이지만 전혀 다른 문제도 있습니다. 1857년 더블린의 해밀턴은 정오각형 열두 개로 둘러싸인 입체인 정십이면체의 꼭짓점 20개를 도시로 보고, 모서리를 따라 모든 도시를 한 번씩 들러 돌아오는 여행을 찾는 놀이 '이코시안 게임'을 내놓았습니다. 1859년에는 이 게임을 런던의 한 장난감 회사에 25파운드에 팔았다고 합니다. 차이는 무엇을 한 번씩 지나느냐에 있습니다. 모든 변을 한 번씩 지나는 오일러의 문제는 차수만 세면 판정되지만, 모든 꼭짓점을 한 번씩 들르는 해밀턴의 문제에는 그런 간단한 판정법이 알려져 있지 않습니다. 오늘날 이 문제는 컴퓨터 과학에서 'NP 완전⁠(NP-complete)⁠' 문제의 대표입니다. 누가 답이 되는 여행 경로를 내밀면 맞는지 확인하기는 쉽지만, 스스로 찾는 빠른 방법이 있는지는 아직 아무도 모릅니다.

이 물음에는 큰 것이 걸려 있습니다. 답을 확인하기는 쉬운 문제들을 통틀어 NP라고 부르는데, 해밀턴의 문제는 그중 가장 어려운 축에 듭니다. 여기서 '쉽다', '빠르다'는 정확한 뜻이 있습니다. 문제의 크기(도시의 수 같은) n이 커질 때 계산 시간이 n², n³처럼 n의 거듭제곱 정도로만 늘어난다는 뜻입니다. 도시를 하나 늘릴 때마다 시간이 두 배가 되는 식이라면 느리다고 합니다. 모든 순서를 다 시험하는 방법은 그보다도 더 느립니다. 도시가 하나 늘 때마다 시험할 순서의 수가 (도시 수)배로 늘기 때문입니다. NP 완전이라는 말은 이 문제 하나를 빠르게 풀면 NP의 모든 문제를 빠르게 풀 수 있다는 뜻입니다. 그러니 이런 문제를 빠르게 푸는 방법이 발견된다면 큰 수의 소인수분해⁠(prime factorization)⁠도 빨라집니다. 소인수분해 역시 답을 확인하기는 쉬운 문제이기 때문입니다. 누가 인수를 내밀면 곱해 보면 되니까요. 그러면 그 어려움에 기대는 RSA 암호⁠(RSA cryptosystem)⁠가 무너집니다(「나머지로 지키는 비밀」). 간단한 판정법이 있느냐 없느냐가 쉬운 문제와 어려운 문제를 가르는 셈입니다.

정리하면, '모든 변을 한 번씩'은 차수를 세는 것만으로 판정되는 쉬운 문제이고, 말 한 마디만 바꾼 '모든 점을 한 번씩'은 빠른 판정법이 알려지지 않은 어려운 문제입니다. 비슷해 보이는 두 문제가 이렇게 다를 수 있습니다.

한 붓 그리기는 유럽의 퍼즐로만 전해진 것이 아닙니다. 앙골라와 콩고 일대의 초크웨족은 모래 위에 점을 격자로 찍고, 그 사이를 손가락으로 감아 도는 그림 '소나'를 그려 왔습니다. 많은 소나는 손을 떼지 않고 한 줄로 그려 처음 자리로 돌아오는 닫힌 곡선, 곧 오일러 회로입니다. 모잠비크에서 일한 수학자 파울루스 헤르데스는 1990년대에 이 그림들 속의 수학을 책으로 정리했습니다. 격자의 가로세로 점 개수에 따라 한 줄로 끝까지 그려지기도 하고 여러 줄로 나뉘기도 하는데, 그 갈림이 두 수의 최대공약수⁠(greatest common divisor)⁠와 이어진다는 것도 그런 연구에서 다룬 물음입니다. 남인도의 타밀나두 등지에서는 여성들이 날마다 새벽 집 문 앞을 쓸고 쌀가루로 '콜람'을 그립니다. 그 가운데 한 갈래는 점들을 찍은 뒤 한 줄이 점마다 한 번씩 감아 돌고 처음 자리로 돌아오게 그리는 그림이고, 인도의 수학자 기프트 시로모니 등이 그 수학적 성질을 연구했습니다. '손을 떼지 않고 한 줄로'라는 같은 물음이 여러 곳에서 따로 그림의 전통이 된 셈입니다.

4 · 네 가지 색이웃한 나라는 다른 색으로

이 절의 물음은 이것입니다. 이웃한 나라끼리 다른 색이 되게 지도를 칠할 때, 몇 가지 색이면 어떤 지도든 충분할까?

1852년 런던의 젊은 수학도 프랜시스 거스리는 잉글랜드의 주 지도를 칠하다가, 이웃한 주끼리 다른 색이 되게 하는 데 네 가지 색이면 충분해 보인다는 것을 알아챘습니다. 동생 프레더릭이 이 질문을 스승인 런던 유니버시티 칼리지의 수학자 오거스터스 드모르간에게 가져갔고, 드모르간은 그해 10월 더블린의 해밀턴에게 편지를 썼습니다. 이 편지가 이 문제의 첫 기록입니다. 해밀턴의 답장은 짧았습니다.

당신의 '색의 사원수⁠(quaternion)⁠'를 곧 시도할 것 같지는 않습니다.— 윌리엄 로언 해밀턴, 드모르간에게 보낸 답장(1852)

해밀턴이 9년 전 더블린의 운하 다리 위에서 떠올린 사원수, 곧 성분이 네 개인 새로운 수를 빗댄 농담입니다(「곱셈은 회전이다」). 네 가지 색과 사원수의 네 성분을 엮은 말장난이었지만, 해밀턴은 끝내 이 문제로 돌아오지 않았습니다.

지도 칠하기도 그래프 문제입니다. 나라를 점으로 놓고, 국경을 맞댄 두 나라를 변으로 이으면, 이웃한 점끼리 다른 색이 되게 칠하는 문제가 됩니다. 평면 지도에서 나온 그래프는 변이 서로 엇갈리지 않게 그릴 수 있는 평면 그래프입니다. 나라마다 수도에 점을 찍고, 이웃한 두 나라의 수도를 공유한 국경을 한 번 넘는 길로 이으면, 길끼리 엇갈리지 않게 그을 수 있기 때문입니다. 여기에는 두 가지 약속이 깔려 있습니다. 한 점에서만 만나는 나라는 이웃으로 치지 않고, 나라마다 땅이 한 덩어리여야 합니다. 떨어진 영토까지 같은 색으로 칠해야 한다면, 다섯 색 이상이 필요한 지도도 만들 수 있습니다. "평면 그래프⁠(planar graph)⁠는 네 가지 색이면 충분하다"는 주장이 4색 정리⁠(four color theorem)⁠입니다.

아래는 가상의 대륙 지도입니다. 나라를 누르면 색이 파랑 → 노랑 → 초록 → 보라 → 지움 순서로 바뀝니다. 이웃한 두 나라가 같은 색이면 그 경계가 빨갛게 표시됩니다. 네 가지 색만으로 빨간 경계 없이 칠해 보세요. 그다음 세 가지 색으로도 되는지 시험해 보세요.

나라 안의 숫자는 서쪽에서 동쪽으로 매긴 순서입니다. 아래의 두 방법은 모두 이 순서대로 칠합니다.

▶ 욕심쟁이로 칠하기 ▶ 되돌아가며 칠하기 지우기

가장 쉬운 방법은 욕심쟁이 방법⁠(greedy algorithm)⁠입니다. 서쪽 나라부터 차례로, 이웃이 아직 쓰지 않은 색 가운데 첫 번째 색을 고르고, 한 번 고른 색은 다시 보지 않습니다. 이 지도에서 욕심쟁이는 마지막 나라에서 이웃들이 네 색을 다 써 버린 것을 보고 다섯째 색(주황)을 꺼냅니다. 앞에서 한 선택이 나중에 발목을 잡은 것입니다. 흔히 다섯째 색이 나왔으니 이 지도에는 다섯 색이 필요하다고 생각하기 쉽지만, 그것은 칠하는 방법의 탓이지 지도의 탓이 아닙니다.

되돌아가며 칠하기는 막히면 바로 앞 나라로 돌아가 다음 색을 시도하고, 그래도 안 되면 더 앞으로 돌아갑니다. 시간은 더 걸리지만, 칠하는 방법이 있다면 언젠가는 반드시 찾습니다. 가능한 칠하기를 빠짐없이 차례로 훑는 셈이기 때문입니다.

그리고 이 지도는 세 가지 색으로는 칠할 수 없습니다. 6번 나라를 보세요. 이웃 다섯 나라 9 → 5 → 2 → 3 → 8이 고리처럼 이어져 6번을 둘러쌉니다. 고리의 나라 수가 홀수이므로, 두 색으로 번갈아 칠하면 다섯째 나라가 첫째 나라와 같은 색이 되어 버립니다. 그래서 고리에만 벌써 세 색이 듭니다. 고리 전체와 이웃한 6번에는 넷째 색이 필요합니다. 그러니 이 지도에 필요한 색의 최소 개수는 정확히 넷입니다.

그렇다면 어떤 평면 지도든 네 가지 색이면 될까요? 1879년 런던의 변호사이자 아마추어 수학자 앨프리드 켐프가 증명을 발표했고, 이 증명은 11년 동안 받아들여졌습니다. 그러다 1890년 더럼 대학의 수학자 퍼시 히우드가 그 안의 구멍을 찾아냈습니다. 히우드는 켐프의 방법을 고쳐 다섯 가지 색이면 충분하다는 것을 증명했고, 도넛 모양의 면 위에 그린 지도에는 일곱 가지 색이 필요할 수도 있다는 것도 보였습니다. 평면에서 넷인지 다섯인지는 그 뒤로 86년 동안 풀리지 않았습니다. 켐프의 증명이 정확히 어느 걸음에서 무너졌는지, 그리고 그가 쓴 '켐프 사슬'이 틀린 증명 속에서도 살아남아 결국 1976년의 증명에 쓰인 이야기는 「틀린 증명이 만든 수학」 4절에 있습니다.

1976년 일리노이 대학 어배너–섐페인의 수학자 케네스 아펠과 볼프강 하켄이 마침내 증명을 발표했습니다. 그들은 '피할 수 없는 배치'를 2천 개 가까이 모았습니다. 어떤 평면 지도든 이 가운데 적어도 하나는 품고 있어야 하는 배치들입니다. 그리고 그 하나하나가 '줄일 수 있다'는 것을 컴퓨터로 확인했습니다. 배치를 줄일 수 있다는 것은, 그 배치를 품은 지도에서 나라 몇 개를 없애거나 합쳐 더 작은 지도를 만들었을 때, 작은 지도를 네 색으로 칠한 방법을 언제나 원래 지도를 네 색으로 칠하는 방법으로 되살릴 수 있다는 뜻입니다.

논증의 뼈대는 이렇습니다. 네 색으로 칠할 수 없는 지도(반례)가 있다고 하고, 그 가운데 나라 수가 가장 적은 것을 골라 봅시다. 그 지도도 피할 수 없는 배치 하나를 품고 있을 테니, 그 배치를 줄여 더 작은 지도를 만듭니다. 이 작은 지도가 네 색으로 칠해진다면 원래 지도도 칠해지니, 작은 지도 역시 네 색으로 칠할 수 없어야 합니다. '가장 작은' 반례보다 더 작은 반례가 생기는 모순이니, 반례는 처음부터 없습니다. 계산에는 컴퓨터로 천 시간 넘게 걸렸습니다.

이 전략에는 앞선 사람이 있었습니다. 독일의 수학자 하인리히 헤슈는 1940년대 말부터 '피할 수 없는 배치'를 찾는 체계적인 방법인 방전법⁠(discharging method)⁠을 다듬으며, 확인할 경우가 만 개쯤일 수도 있다고 내다보았습니다. 1948년 무렵 킬 대학에서 그의 강의를 들은 학생 가운데 한 사람이 하켄이었습니다. 헤슈는 계산을 이어 갈 더 큰 컴퓨터를 구하려 애썼지만, 문제를 끝낸 것은 그 강의를 들었던 학생이었습니다. 일리노이 대학 수학과는 한동안 보내는 우편물에 "네 가지 색이면 충분하다"는 문구를 찍었다고 합니다.

수학자들의 반응은 엇갈렸습니다. 사람이 한 줄씩 따라 읽을 수 없는 증명을 증명이라 할 수 있을까? 1979년 철학자 토머스 티모치코는 이 증명이 수학에 '실험'을 들여왔다고 주장했습니다. 우리는 컴퓨터가 제대로 돌았다는 것을 망원경을 믿듯 경험으로 믿을 뿐이라는 것입니다. 반대쪽의 답은 이랬습니다. 프로그램과 컴퓨터가 틀릴 수 있다는 걱정은 다른 사람이 다른 언어와 다른 기계로 같은 계산을 되풀이하거나, 증명의 단계를 기계가 읽을 수 있는 형태로 적어 따로 만든 검사 프로그램으로 확인하면 줄일 수 있다는 것입니다. 증명을 찾기보다 확인하기가 훨씬 쉬우니까요. 그래도 '사람이 이해하지 못한 증명'이라는 티모치코의 물음까지 이것으로 풀린다고 보지 않는 사람도 있습니다.

정리하면, 평면 지도는 네 가지 색이면 언제나 충분하고, 세 가지로는 모자란 지도가 있습니다. 앞의 사실은 사람이 세운 논증의 뼈대에 컴퓨터가 수많은 경우를 확인해 채운 증명으로 알려졌습니다.

이 물음은 공교롭게도 쾨니히스베르크로 되돌아옵니다. 그 도시에서 평생을 보낸 철학자 칸트는 『순수이성비판』(1781)에서 수학을 경험에 앞서면서도 새로운 지식을 주는 '선험적 종합 판단⁠(synthetic a priori judgment)⁠'의 대표로 꼽았습니다. 컴퓨터 증명은 수학의 확실성이 정말 경험과 무관한지 다시 묻게 했습니다. 칸트의 이 생각이 그보다 한 세기 반쯤 앞서 비유클리드 기하⁠(non-Euclidean geometry)⁠와 부딪힌 이야기는 「평행선의 반란」에 있습니다.

그 뒤 수학자들은 컴퓨터를 버리는 대신 검사할 몫을 줄이는 쪽을 택했습니다. 1996년 닐 로버트슨, 대니얼 샌더스, 폴 시모어, 로빈 토머스는 확인할 배치를 600여 개로 줄이고 검사 프로그램을 공개한, 더 간단한 컴퓨터 증명을 내놓았습니다. 2005년 무렵에는 컴퓨터 과학자 조르주 공티에가 증명 전체를 증명 보조기⁠(proof assistant)⁠ Coq로 옮겼습니다. 증명 보조기는 증명의 모든 단계가 정해진 논리 규칙에 맞는지 컴퓨터가 하나하나 검사하게 하는 프로그램입니다. 이제 믿어야 할 것은 수천 가지 경우의 계산이 아니라 작고 공개된 검사 프로그램 하나입니다. 그 검사기가 무엇을 믿고 무엇을 검사하는지, 그리고 그 뿌리가 러셀의 타입⁠(type)⁠에 있다는 이야기는 「증명은 프로그램이다」에 있습니다.

5 · 가장 짧은 길거리를 버린 지도, 거리를 다시 얹은 그래프

이 절의 물음은 이것입니다. 변마다 길이가 적힌 그래프에서 두 점 사이의 가장 짧은 길을, 모든 길을 다 시험하지 않고 찾을 수 있을까?

그래프는 거리를 버렸기 때문에 강합니다. 1931년 런던 지하철의 제도사 해리 벡은 역 사이의 실제 거리와 방향을 무시하고 노선을 수평·수직·45도 선으로만 그린 도식을 여가에 만들었습니다. 회사는 처음에 망설였다고 하지만 1933년부터 배포된 이 노선도는 곧 승객들의 사랑을 받았고, 오늘날 세계 여러 도시의 노선도가 이 방식을 따릅니다. 승객에게 필요한 것은 어느 역이 어느 역과 이어지고 어디서 갈아타는지, 곧 그래프였습니다. 지리학의 눈으로 보면 틀린 지도이지만, 위상수학의 눈으로 보면 정확한 지도입니다. 위상수학은 늘이고 구부려도 끊지만 않으면 변하지 않는 성질, 곧 연속적인 변형에도 변하지 않는 성질을 다룹니다.

하지만 길을 찾을 때는 거리가 다시 필요합니다. 변마다 길이를 적은 그래프에서 두 점 사이의 최단 경로⁠(shortest path)⁠를 찾는 문제입니다. 1956년 암스테르담의 수학 센터에서 일하던 스물여섯 살의 에츠허르 데이크스트라는 새 컴퓨터 ARMAC을 시연하면서, 수학을 모르는 사람도 알아들을 문제로 "로테르담에서 흐로닝언까지 가장 짧은 길은?"을 골랐습니다. 그는 훗날 인터뷰에서, 약혼녀와 암스테르담에서 장을 보다 지쳐 카페 테라스에서 커피를 마시다가 종이와 연필 없이 20분쯤 만에 이 방법을 설계했다고 회상했습니다. 논문은 1959년에 나왔습니다.

방법은 이렇습니다. 출발점에서 가까운 도시부터 하나씩 거리를 확정합니다. 아직 확정되지 않은 도시 가운데 지금까지 알려진 거리가 가장 짧은 도시를 골라 확정하고, 그 도시를 거쳐 가면 더 짧아지는 이웃이 있으면 이웃의 거리를 고칩니다.

도시 셋으로 따라가 봅시다. A에서 B로 바로 가는 길은 4, A에서 C는 1, C에서 B는 2입니다. A에서 출발하면 처음 알려진 거리는 A 0, C 1, B 4입니다. 미확정 도시 가운데 가장 가까운 C(1)를 확정합니다. C를 거쳐 B로 가면 1 + 2 = 3으로 4보다 짧으니 B의 거리를 3으로 고칩니다. 남은 B(3)를 확정하면 끝입니다. A에서 B까지 가장 짧은 길은 바로 가는 길이 아니라 C를 거치는 길이었습니다.

이 방법이 왜 옳을까요? 길이가 음수인 변이 없다면, 이렇게 고른 도시로 가는 더 짧은 길은 있을 수 없습니다. 다른 길은 확정된 도시들의 무리를 벗어나는 순간 어떤 미확정 도시를 밟는데, 그 도시까지 이미 지금 고른 도시의 거리 이상을 걸었습니다(지금 고른 도시가 미확정 도시 가운데 가장 가까웠으니까요). 남은 구간의 길이는 0 이상이니 줄어들 수 없습니다. 위의 예에서 C를 확정할 때, B를 거쳐 C로 가는 길은 B까지만 이미 4를 걸어야 하니 1보다 짧을 수 없습니다.

이 짧은 논증이 이 알고리즘(정해진 계산 절차) 전체를 떠받칩니다. '확정된 도시의 거리는 모두 참된 최단 거리'처럼 단계마다 지켜지는 조건을 반복 불변식⁠(loop invariant)⁠이라 합니다. 로버트 플로이드와 토니 호어는 이런 조건으로 프로그램이 옳음을 증명하는 규칙을 다듬었고, 이것이 호어 논리⁠(Hoare logic)⁠입니다.

도시가 많을 때 '지금 가장 가까운 도시'를 빨리 꺼내려면 가장 작은 값을 늘 맨 위에 두는 우선순위 큐⁠(priority queue)⁠를 씁니다. 이 큐를 만드는 대표적인 구조가 힙⁠(heap)⁠이고, 힙이 정렬에도 쓰이는 이야기는 「줄 세우기의 한계」 4절에 있습니다.

출발 도시는 , 아프슬라위트데이크 둑은 입니다. 도시를 누르면 그곳이 목적지(분홍 고리)가 됩니다. 아래 ◀ ▶ 단추로 한 단계씩 앞뒤로 움직여 보세요. 단계마다 볼 것은, 아직 확정되지 않은 도시 가운데 이름 옆 숫자가 가장 작은 도시가 확정되고, 그 이웃들의 숫자가 줄어드는지입니다.

네덜란드의 도시 13곳. 변 위의 숫자는 두 도시 사이의 직선거리(km)이고, 도로망은 설명을 위해 단순하게 골랐습니다. 이름 옆 숫자는 지금까지 알려진 가장 짧은 거리, 흰검은 고리는 출발 도시입니다.

청록 선은 확정된 도시로 가는 가장 짧은 길이고, 노란 점선은 아직 바뀔 수 있는 잠정 경로입니다. 모든 도시가 확정되면 청록 선들은 출발 도시에서 뻗어 나간 나무 모양이 되고, 목적지까지의 최단 경로는 그 나무의 한 가지입니다. 한 번의 계산으로 모든 도시까지의 답을 한꺼번에 얻는 것입니다.

가장 짧은 길을 찾는 일은 최적화⁠(optimization)⁠의 한 갈래입니다. 굽은 면 위에서라면 답은 측지선⁠(geodesic)⁠입니다. 지구 위의 비행기 항로가 지도에서 휘어 보이는 것은, 그 항로가 대원⁠(great circle)⁠을 따라가는 구면기하⁠(spherical geometry)⁠의 직선이기 때문입니다(「평행선의 반란」). 데이크스트라의 방법은 그 연속적인 질문을 점과 선의 세계로 옮긴 것입니다. 오늘날의 길 안내 프로그램은 교차로가 수백만 개인 도로 그래프 위에서 이 방법을 더 빠르게 다듬어 씁니다.

정리하면, 데이크스트라의 방법은 '가장 가까운 미확정 도시를 확정하고 이웃을 고친다'를 되풀이해, 길이가 음수인 변이 없는 그래프에서 출발점에서 모든 도시까지의 최단 거리를 한 번에 구합니다.

같은 무렵인 1958년, 샌타모니카의 RAND 연구소에서는 리처드 벨먼이 '동적 계획법⁠(dynamic programming)⁠'이라는 이름으로 다른 최단 경로 계산을 내놓았습니다. 이 방법은 길이가 음수인 변이 있어도, 한 바퀴 돌면 길이가 줄어드는 고리만 없다면 쓸 수 있습니다. 길이를 비용이 아니라 이익처럼 음수로 적는 경우가 있는데, 한 바퀴 돌면 줄어드는 고리가 있으면 돌수록 짧아지니 '가장 짧은 길'이 없습니다. 두 방법이 모두 '더하기 자리에 최솟값, 곱하기 자리에 덧셈'을 넣은 한 가지 계산을 서로 다른 순서로 해 나가는 것이라는 이야기는 「같은 계산, 다른 덧셈」에 있습니다.

변마다 적은 길이에서 출발해 모든 두 도시 사이의 최단 거리를 구하면, 그 거리는 저절로 삼각부등식⁠(triangle inequality)⁠을 지킵니다. 삼각부등식은 A에서 C까지의 거리가 A에서 B를 거쳐 C로 가는 거리보다 길 수 없다는 성질입니다. 최단 거리라면 B를 거치는 길도 후보에 들어 있으니 당연히 성립합니다. A에서 B로 가는 길과 B에서 C로 가는 길을 이어 붙이는 것을 화살표 두 개를 잇는 일로 보고, 삼각부등식을 그 이어 붙이기의 규칙으로 읽는 풍부화된 범주⁠(enriched category)⁠의 눈으로 보면, 이것은 그래프가 자유롭게 생성하는 '거리의 범주⁠(category)⁠'를 계산하는 일입니다. 같은 범주의 언어로 최대공약수와 교집합⁠(intersection)⁠, 연쇄법칙⁠(chain rule)⁠을 한 모양으로 보는 이야기는 「화살표만으로 본 수학」에 있습니다.

1959년의 세 쪽짜리 논문 「그래프와 관련된 두 문제에 관한 노트」의 다른 한 문제는 모든 도시를 가장 짧은 전선의 합으로 잇는 방법, 오늘날의 최소 신장 트리⁠(minimum spanning tree)⁠였습니다. 이 문제는 이미 두 번 풀려 있었습니다. 1925년 체코슬로바키아 브르노의 수학자 오타카르 보루프카는 한 지인에게서 부탁을 받았습니다. 서모라비아 지방에 전기를 보급하던 전력 회사에서 일하던 그 지인은, 마을들을 가장 적은 비용의 송전망으로 잇는 방법을 찾아 달라고 했습니다. 보루프카는 이듬해 체코어로 답을 발표했습니다. 1930년에는 프라하의 보이테흐 야르니크가 다른 방법을 냈습니다. 둘 다 체코어 학술지에 실려 오래 알려지지 않았고, 1950년대 미국에서 크러스컬(1956)과 프림(1957)이, 그리고 데이크스트라가 따로 다시 찾았습니다. 전력망이라는 실용적인 필요가 먼저 물음을 냈고, 컴퓨터가 생기자 같은 물음이 여러 곳에서 동시에 다시 떠오른 것입니다.

6 · 여섯 다리 건너좁은 세상⁠(small world)⁠

이 절의 물음은 이것입니다. 수십억 명이 사는 세상에서 아무 두 사람이 왜 몇 단계 만에 이어질까? 그리고 사람들이 끼리끼리 뭉쳐 사는데도 어떻게 그럴 수 있을까?

1929년 헝가리 작가 카린티 프리제시는 단편 「사슬」에서, 지구 위의 누구든 지인 다섯 명만 거치면 이어진다고 내기하는 인물들을 그렸습니다. 철도와 전신, 라디오로 세계가 좁아진다는 당시의 감각을 담은 이야기였습니다.

소설 속 내기를 실제로 재 본 사람은 40년 가까이 뒤에 나왔습니다. 1967년 하버드 대학의 사회심리학자 스탠리 밀그램은 이 생각을 실험으로 옮겼습니다. 그는 네브래스카주 오마하와 캔자스주 위치토의 사람들에게, 보스턴 근처에 사는 낯선 목표 인물 앞으로 편지를 전하게 했습니다. 목표 인물을 직접 모르면 그를 알 것 같은 지인에게만 넘기는 것이 규칙이었습니다. 도착한 편지는 평균⁠(mean)⁠ 다섯 명 남짓을 거쳤고, 여기서 '여섯 단계의 분리'라는 말이 퍼졌습니다. 다만 출발한 편지의 대부분은 도착하지 못했고, 뒤에 이 결론이 과장되었다는 비판도 나왔습니다. 밀그램이 맨땅에서 시작한 것은 아닙니다. 1950년대에 MIT의 정치학자 이시엘 드 솔라 풀과 IBM의 수학자 맨프레드 코헨은 한 사람이 아는 사람의 수를 어림하고 두 사람 사이에 몇 단계가 필요한지를 계산한 원고를 써서 돌렸습니다. 이 원고는 20년 넘게 출판되지 않은 채 연구자들 사이에서 복사본으로 읽히다가, 1978년에야 학술지 『사회 연결망』 창간호에 실렸습니다. 밀그램의 실험은 그 계산을 편지로 확인해 보려는 시도였습니다.

왜 세상은 이렇게 좁을까요? 친구가 100명이고 그 친구들도 저마다 다른 친구 100명이 있다면, 두 다리만 건너도 만 명, 세 다리면 백만 명에 닿습니다. 한 단계마다 100배씩, 곧 닿는 사람 수가 단계에 따라 지수함수⁠(exponential function)⁠처럼 늘어납니다. 거꾸로 n명에 닿는 데 필요한 단계는 '100을 몇 번 곱해야 n이 되는가'이고, 이 횟수가 n의 로그입니다. 로그는 아주 느리게 늡니다. 100을 다섯 번 곱하면 100억이니, 80억 명에 닿는 데도 다섯 단계면 충분한 셈입니다.

그런데 이 계산은 친구의 친구들이 서로 겹치지 않는다고 가정합니다. 실제로는 내 친구들끼리도 서로 친구인 경우가 많습니다. 이렇게 끼리끼리 뭉친 정도를 군집 계수라고 합니다. 사람마다 자기 친구들 가운데 두 명씩 짝지은 쌍 중에서 서로도 친구인 쌍의 비율을 구하고, 이것을 모든 사람에 대해 평균 낸 값입니다. 예를 들어 친구가 넷이면 두 명씩 짝짓는 쌍은 6개이고, 그중 3쌍이 서로도 친구라면 그 사람의 비율은 3 ÷ 6 = 0.5입니다. "내 친구 두 명을 아무렇게나 골랐을 때 그 둘도 서로 친구일 확률⁠(probability)⁠"의 평균인 셈이고, 0이면 친구들끼리 전혀 모르고 1이면 모두가 서로 압니다. 끼리끼리 뭉친 세상은 좁을 수 없을 것 같습니다. 친구의 친구가 대부분 이미 아는 사람이라면, 한 단계마다 새로 닿는 사람이 100배씩 늘지 않기 때문입니다.

1998년 코넬 대학의 대학원생 덩컨 와츠와 그의 지도교수인 응용수학자 스티븐 스트로가츠는 이 두 성질이 함께 있을 수 있음을 간단한 모형으로 보였습니다. 출발점은 사회학이 아니라 풀벌레였습니다. 와츠는 귀뚜라미 수천 마리가 어떻게 한 박자로 맞춰 우는지를 연구하고 있었습니다. 그는 누가 누구의 소리를 듣느냐, 곧 연결의 모양이 박자 맞추기를 좌우한다는 데 주목했고, 실제 연결망이 어떤 모양인지 따지다가 '여섯 다리' 문제에 닿았습니다.

그들의 모형을 봅시다. 아래 왼쪽 그림은 100명이 원 위에 서서 양옆의 두 사람씩, 곧 네 사람과만 아는 마을입니다. 연결은 한 사람에 넷, 두 사람이 한 연결을 나눠 가지니 모두 100 × 4 ÷ 2 = 200개입니다. 내 친구 네 명 가운데 서로도 아는 쌍은 바로 옆 둘끼리, 왼쪽 둘끼리, 오른쪽 둘끼리의 3쌍이니, 군집 계수⁠(clustering coefficient)⁠는 위의 예와 같은 0.5로 높습니다. 그러나 원의 반대편 사람은 50자리 떨어져 있고 한 단계에 많아야 두 자리씩 가니, 25단계를 거쳐야 합니다. 뭉쳐 살고, 세상은 넓은 마을입니다.

이제 연결 몇 개를 무작위로 골라 한쪽 끝을 아무 사람에게나 옮겨 지름길로 바꿉니다. 지름길 수: 개(전체 연결 가운데 비율 ). 평균 거리는 모든 두 사람 사이의 단계 수를 평균 낸 값입니다. 오른쪽 그림은 지름길이 하나도 없을 때의 평균 거리와 군집 계수를 각각 1로 놓고, 지름길이 늘면 두 값이 어떻게 줄어드는지를 비교합니다. 볼 것은 두 곡선이 떨어지는 빠르기의 차이입니다.

원형 마을과 지름길
지름길 수에 따른 변화 (처음 값을 1로 둔 비율)
왼쪽: 사람을 누르면 그 사람에게서 몇 단계 떨어져 있는지가 색으로 보입니다(흰색검은색 0, 노랑 1, 주황 2, 분홍 3, 보라 4, 파랑 5, 청록 6, 어두운 회색 7 이상). 오른쪽: 무작위로 바꾼 마을 6개의 평균 곡선과, 지금 왼쪽 마을의 값(점).

지금 평균 거리는 단계, 군집 계수는 이고, 고른 사람에게서 가장 먼 사람까지는 단계입니다. 지름길을 전체 연결 200개의 5%인 열 개쯤만 놓아도 평균 거리는 평균적으로 절반쯤으로 떨어지지만 군집 계수는 15%쯤밖에 줄지 않습니다. 까닭은 이렇습니다. 지름길 하나는 그 양 끝 근처에 사는 수많은 사람의 거리를 한꺼번에 줄입니다. 반대편으로 가는 길이 모두 그 지름길을 탈 수 있으니까요. 그러나 군집 계수는 지름길 끝에 선 몇 사람의 값만 조금 바꿉니다. 대부분의 사람은 여전히 이웃끼리 뭉쳐 살고, 드문 지름길 몇 개가 멀리 떨어진 무리들을 잇습니다. 이것이 좁은 세상입니다. 와츠와 스트로가츠는 영화배우들의 공동 출연 관계, 미국 서부의 전력망, 예쁜꼬마선충의 신경망⁠(neural network)⁠이 모두 이런 모양이라는 것을 보였습니다.

좁은 세상이 반가운 일만은 아닙니다. 병은 사람 사이의 연결을 따라 퍼지기 때문입니다. 위 그림에서 한 사람을 누르고 지름길을 늘려 보세요. 만나는 사람마다 반드시 병을 옮긴다고 치면, 색이 퍼지는 단계가 곧 병이 퍼지는 세대입니다. 가장 먼 사람까지의 단계 수가 지름길이 없을 때의 25에서 얼마나 줄어드는지 보세요. 실제 병은 확률적으로 옮으니 이보다 느리고 들쭉날쭉합니다.

1927년 에든버러의 생화학자 윌리엄 커맥과 군의관 출신 역학자 앤더슨 매켄드릭은 감염될 수 있는 사람, 감염된 사람, 회복한 사람의 수가 어떻게 바뀌는지를 미분방정식⁠(differential equation)⁠, 곧 '각 무리의 수가 바뀌는 빠르기를 지금의 수들로 적은 식'으로 적고, 20세기 초 봄베⁠(bombe)⁠이의 페스트 유행 기록에 맞추어 보았습니다. 이 모형은 모든 사람이 모든 사람과 똑같은 확률로 만난다고 가정합니다. 실제 연결망에서는 지름길 몇 개가 먼 지역에 병을 한꺼번에 옮기고, 아는 사람이 아주 많은 몇 사람이 전파를 크게 좌우합니다. 와츠와 스트로가츠의 이듬해인 1999년, 노터데임 대학의 버러바시 얼베르트 라슬로와 얼베르트 레커는 웹과 여러 연결망에 이런 '허브'가 드물지 않다는 데 주목했습니다. 그리고 새로 들어온 점이 이미 연결이 많은 점에 붙기 쉬우면 그런 모양이 저절로 자란다는 모형을 내놓았습니다.

7 · 링크의 무게무작위로 떠도는 사람이 머무는 곳

이 절의 물음은 이것입니다. 링크로 얽힌 수많은 웹 쪽 가운데 어느 쪽이 중요한지를, 링크의 모양만 보고 매길 수 있을까?

1990년대 후반의 웹은 이미 수천만 쪽으로 불어나 있었고, 검색 엔진은 낱말이 몇 번 나오는지 세는 방법으로는 쓸 만한 쪽을 가려내기 어려웠습니다. 스탠퍼드 대학원생 세르게이 브린과 래리 페이지는 학술 논문의 인용에서 실마리를 얻었습니다. 많이 인용되는 논문이 중요하고, 중요한 논문에 인용되면 더 중요하다. 웹에서는 링크가 인용입니다. 1998년 그들은 이 생각을 페이지랭크⁠(PageRank)⁠라는 이름으로 발표하고, 그해 구글을 세웠습니다.

"중요한 쪽에 인용되면 중요하다"는 정의는 제자리를 맴도는 것 같습니다. 이것을 푸는 한 가지 그림이 무작위 서퍼입니다. 한 사람이 웹을 떠돌며 매번 지금 쪽의 링크 가운데 하나를 무작위로 누릅니다. 다만 확률 1−d1-d로는 싫증이 나서 아무 쪽으로나 순간 이동합니다. 예를 들어 d = 0.85이면 걸음마다 85%의 확률로 링크를 누르고, 15%의 확률로 순간 이동합니다. 아주 오래 떠돌았을 때 이 사람이 각 쪽에 머문 시간의 비율이 그 쪽의 점수입니다. 링크를 많이 받는 쪽, 그리고 자주 들르는 쪽에서 링크를 받는 쪽에 더 자주 가게 되니, 이 비율은 "중요한 쪽에 인용되면 중요하다"를 그대로 따릅니다. 지금 d=d = 입니다.

작은 웹: 여섯 쪽과 링크
점수
한 쪽에서 다른 쪽으로 끌면 그 방향의 링크가 생기고, 같은 방향으로 다시 끌면 사라집니다. 점의 크기와 막대의 높이가 점수입니다.

▶ 무작위 서퍼 3,000걸음을 눌러 보세요. 흰검은 점이 링크를 따라 떠돌고, 흰검은 테두리가 각 쪽에 머문 비율입니다. 걸음이 늘수록 비율은 한 값으로 모입니다. 동전을 많이 던질수록 앞면의 비율이 1/2에 가까워지는 큰 수의 법칙⁠(law of large numbers)⁠과 같은 현상으로, 다음 걸음이 지금 쪽에만 달린 이런 떠돌기(뒤에 나올 마르코프 연쇄⁠(Markov chain)⁠)에서도 성립합니다.

그 값은 흉내 내지 않고 바로 계산할 수도 있습니다. 먼저 모든 쪽에 점수를 1/61/6씩 나눠 줍니다. 그다음 각 쪽이 제 점수의 dd만큼은 자기가 링크한 쪽들에 똑같이 나눠 주고, 나머지 1−d1-d는 모든 쪽에 고루 나눠 주는 일을 되풀이합니다. 서퍼가 한 걸음 옮길 때 '지금 여기 있을 확률'이 어떻게 옮겨 가는지를 그대로 계산하는 것입니다.

쪽이 셋뿐인 작은 웹으로 한 번 해 봅시다. A와 B는 서로를 링크하고, C는 A만 링크하며, C를 링크하는 쪽은 없습니다. d = 0.85이고 처음 점수는 셋 모두 1/3입니다. 순간 이동 몫으로 모든 쪽이 0.15 × 1 ÷ 3 = 0.05씩 받습니다. 링크 몫으로 A는 B와 C에게서 0.85 × 1/3씩 받아 약 0.567을 더 받고, B는 A에게서 0.85 × 1/3 ≈ 0.283을 더 받고, C는 아무것도 더 받지 못합니다. 한 번 나눈 뒤의 점수는 A 약 0.617, B 약 0.333, C 0.05이고, 합은 여전히 1입니다.

이제 그림의 여섯 쪽으로 돌아갑니다. 지금 번 되풀이했습니다. ▶ 40번 되풀이

위 식의 rkr_k('r 케이')는 k번 나눠 준 뒤 A부터 F까지 여섯 쪽의 점수를 괄호 안에 차례로 적은 것입니다. 오른쪽 값은 한 번 더 나눠 줄 때 점수가 모두 합쳐 얼마나 바뀌는지입니다. 쪽마다 바뀐 양의 절댓값(부호를 떼고 크기만 본 값)을 더한 것이고, 두 겹 세로 막대와 아래 첨자 1이 이 더하기 방식을 가리킵니다. 이 값이 0에 가까워지면 점수가 자리를 잡은 것입니다. 순위는 입니다.

몇십 번만 되풀이하면 점수 벡터(여기서는 여섯 점수를 한 줄로 묶은 것)는 더 변하지 않습니다. 한 번 나눠 주기⁠(period)⁠는 행렬⁠(matrix)⁠ GG를 곱하는 일입니다. 행렬은 수를 가로세로로 늘어놓은 표이고, 여기서 GG의 칸에는 '어느 쪽의 점수 가운데 얼마가 어느 쪽으로 가는가'라는 비율이 적혀 있습니다. GG는 링크를 따라가는 몫 dd와 순간 이동하는 몫 1−d1-d를 합친 행렬입니다. 그러니 더는 변하지 않는 점수 rr은 Gr=rGr = r, 곧 'G대로 한 번 더 나눠 줘도 그대로'를 만족합니다. 행렬을 곱해도 방향이 바뀌지 않는 벡터⁠(vector)⁠를 고유벡터⁠(eigenvector)⁠라 하고, 그때 곱해지는 배수⁠(multiple)⁠를 고유값⁠(eigenvalue)⁠이라 하니, r은 고유값 1에 대한 고유벡터입니다. 다음 쪽이 오직 지금 쪽에만 달려 있는 무작위 서퍼는 마르코프 연쇄이고, 페이지랭크는 그 정상 분포⁠(stationary distribution)⁠, 곧 아주 오래 떠돈 뒤 더는 변하지 않는 머무름 비율입니다.

같은 답에 이르는 다른 길과, 왜 빨리 자리를 잡는가

같은 답에 이르는 길은 더 있습니다. 링크만 따라 나눠 주는 부분을 행렬 MM이라 하면, 같은 답을 연립일차방정식⁠(system of linear equations)⁠ (I−dM) r=1−d61(I - dM)\,r = \tfrac{1-d}{6}\mathbf{1}로 풀 수도 있습니다. 여기서 I는 곱해도 아무것도 바꾸지 않는 단위행렬⁠(identity matrix)⁠, 1\mathbf{1}은 여섯 성분이 모두 1인 벡터이고, 위 풀이의 두 식이 바로 이런 연립방정식이었습니다. 또 서퍼가 링크를 kk번 연달아 따라갈 확률이 dkd^k로 줄어드는 것을 이용해 등비급수⁠(geometric series)⁠로 적을 수도 있습니다. 되풀이해 곱하는 방법이 빨리 수렴⁠(convergence)⁠하는 것은 둘째로 큰 고유값의 크기가 dd를 넘지 않기 때문입니다(대각화와 행렬 거듭제곱⁠, diagonalization and matrix powers⁠). 차이를 쪽마다 절댓값⁠(absolute value)⁠으로 재어 더하면 참값과의 차이가 한 번 곱할 때마다 dd배 이하로 줄어드니, d=0.85d = 0.85이면 40번 뒤에는 처음 차이의 0.8540≈0.00150.85^{40} \approx 0.0015배 이하만 남습니다.

정리하면, 페이지랭크는 무작위로 링크를 누르며 떠도는 사람이 오래 떠돈 끝에 각 쪽에 머무는 비율이고, 점수를 되풀이해 나눠 주면 몇십 번 만에 그 값에 닿습니다.

마르코프 연쇄의 이름은 페테르부르크의 수학자 안드레이 마르코프에게서 왔습니다. 1913년 그는 푸시킨의 운문 소설 『예브게니 오네긴』의 글자 2만 개를 모음과 자음으로 나누어, 다음 글자가 모음일 확률이 바로 앞 글자에 따라 어떻게 달라지는지 셌습니다. 오일러가 일곱 다리 논문을 발표한 바로 그 아카데미에서였습니다. 이 셈이 오늘날의 언어 모델⁠(language model)⁠로 이어지는 이야기는 「말을 세는 기계」에 있습니다.

링크로 무게를 재자는 생각에도 선배가 있습니다. 1955년 미국의 유진 가필드는 논문마다 그 논문을 인용한 논문들을 거꾸로 찾아볼 수 있는 색인을 제안했고, 1964년 필라델피아의 과학정보연구소에서 『과학 인용 색인⁠(citation index)⁠』을 펴냈습니다. 인용의 연결망이 처음으로 한 권의 자료가 된 것입니다. '중요한 쪽에 인용되면 중요하다'는 되먹임⁠(feedback)⁠ 정의도 먼저 나와 있었습니다. 1953년 사회학자 레오 카츠는 사람의 지위를 그를 고른 사람들의 지위로 매기는 지수를 내놓았고, 1976년 가브리엘 핀스키와 프랜시스 나린은 학술지의 영향력을, 그 학술지를 인용한 학술지들의 영향력으로 가중해 고유벡터로 계산했습니다. 브린과 페이지와 같은 1998년, 컴퓨터 과학자 존 클라인버그도 링크 구조의 고유벡터로 웹 쪽의 권위를 매기는 방법을 발표했습니다. 링크에 값이 매겨지자 링크를 사고파는 시장도 생겼고, 검색 엔진과 순위를 조작하려는 사람들 사이의 싸움도 시작되었습니다.

8 · 다리가 사라진 도시쾨니히스베르크에서 칼리닌그라드로

이 절의 물음은 이것입니다. 일곱 다리의 도시는 그 뒤 어떻게 되었고, 오늘 남은 다리로는 그 산책이 가능할까?

오일러 이후에도 쾨니히스베르크는 이 이야기와 인연이 깊었습니다. 1724년 이 도시에서 태어난 칸트는 평생 쾨니히스베르크 근처를 거의 떠나지 않았지만, 1756년 무렵부터 수십 년 동안 대학에서 자연지리학을 강의했습니다. 그가 날마다 같은 시각에 산책해서 이웃들이 시계를 맞췄다는 이야기는 전설에 가깝습니다. 칸트는 1768년의 짧은 논문에서, 오른손과 왼손처럼 모든 길이와 각도가 같은데도 겹쳐지지 않는 쌍을 들어 공간의 본성을 따졌습니다. 그 글은 라이프니츠가 구상만 하고 끝내 내놓지 못한 '위치 해석⁠(analysis situs)⁠'을 언급하며 시작합니다. 크기가 아닌 모양과 방향의 성질, 곧 나중에 위상수학이 다룰 질문이었습니다.

이 도시는 그래프 이론의 다음 걸음도 낳았습니다. 1824년 이곳에서 태어난 물리학자 구스타프 키르히호프는 알베르티나 대학의 학생이던 1845년에 전기 회로의 법칙을 세웠습니다. 전선이 만나는 점으로 들어온 전류는 모두 나간다는 법칙은, 한 땅에 들어온 만큼 나간다는 오일러의 논증과 같은 모양입니다. 1847년 그는 회로의 방정식을 풀면서 고리 없이 모든 점을 잇는 '나무'를 썼습니다. 회로를 행렬(수를 가로세로로 늘어놓은 표)로 적은 뒤 한 줄과 한 칸을 지우고 행렬식(표의 수들로 정해진 규칙에 따라 계산하는 수 하나)을 구하면 회로 속 나무의 개수가 나옵니다. 오늘날 행렬–트리⁠(tree)⁠ 정리라 부르는 이 결과가 이 논문에서 싹텄습니다. 그 행렬이 뒤에 그래프의 라플라시안⁠(Laplacian)⁠이라는 이름을 얻어 열의 흐름과 무작위 걸음과 사진의 윤곽선까지 이어지는 이야기는 「라플라시안, 가장 많이 재사용된 식」 4절에 있습니다.

한 세기 가까이 뒤, 이 도시는 수학의 한계가 드러난 무대가 되었습니다. 이 도시에서 자라고 공부한 수학자 다비트 힐베르트는 1930년 쾨니히스베르크의 학회에서 "우리는 알아야 한다, 우리는 알게 될 것이다"로 끝나는 연설을 했습니다. 바로 전날 같은 도시의 학술 모임에서 젊은 괴델이 그 희망에 한계가 있음을 보이는 불완전성 정리⁠(incompleteness theorem)⁠를 처음 알렸습니다. 그 이틀의 이야기와 정리가 말하는 한계는 「무한에도 크기가 있다」에 있습니다.

1944년 8월 영국 공군의 폭격으로 크나이프호프섬을 비롯한 옛 시가지가 거의 다 불탔고, 1945년 4월 소련군이 도시를 점령했습니다. 포츠담 회담의 결정으로 동프로이센 북부는 소련 땅이 되었고, 도시는 1946년 소련 정치인 칼리닌의 이름을 따 칼리닌그라드가 되었습니다. 독일계 주민은 곧 추방되었습니다.

오늘의 모습은 이렇습니다. 크나이프호프는 지금 공원이 된 '칸트 섬'이고, 다시 지은 대성당 곁에 칸트의 무덤이 있습니다. 소련이 해체된 뒤 칼리닌그라드는 폴란드와 리투아니아 사이에 끼어 러시아 본토와 맞닿지 않은 땅이 되었습니다. 국경이라는 변이 바뀌자 도시는 나라의 그래프에서 따로 떨어진 점이 된 셈입니다.

일곱 다리 가운데 몇 개는 폭격으로 사라졌고, 몇 개는 전후에 헐리고 새 도로로 바뀌었습니다. 흔히 인용되는 설명에 따르면 옛 다리 자리에 지금 남아 있거나 다시 놓인 다리는 다섯 개이고, 두 섬의 차수는 3, 두 강변의 차수는 2가 되었습니다. 그렇다면 이제는 한 섬에서 출발해 다른 섬에서 끝나는 산책이 가능합니다. 다리를 어떻게 세느냐에 따라 설명이 조금씩 달라서 이 숫자는 대략으로 받아들이는 편이 좋습니다. 어쨌든 오일러의 문제를 결국 전쟁이 '풀어' 버린 셈입니다. 3절의 판에서 쾨니히스베르크의 크나이프호프섬과 북쪽 강변, 섬과 남쪽 강변을 잇는 변을 하나씩 지워 직접 확인해 보세요.

위: 1640년부터 오늘까지. 수학 줄(파랑)의 사건⁠(event)⁠들이 18세기 페테르부르크에서 19세기 런던·더블린, 20세기 부다페스트·암스테르담을 거쳐 미국의 대학들로 옮겨 가는 것을 보세요. 쾨니히스베르크의 점들은 철학·과학 줄과 역사 줄에 흩어져 있습니다. 아래: 편지와 논문이 오간 길. 주황 선은 다리 문제의 편지, 보라 선은 라이프니츠의 '위치 해석' 편지, 파랑 선은 4색 문제의 편지와 논문, 분홍 선은 밀그램의 편지 사슬입니다.

9 · 이어지는 길점과 선이 여는 문

오일러가 지도를 지운 뒤 남은 점과 선은 수학의 거의 모든 분야와 이어집니다.

정리. 그래프는 크기와 모양을 버리고 '무엇이 무엇과 이어져 있는가'만 남긴 그림입니다. 연결된 그래프에서 모든 변을 한 번씩 지나는 길은 홀수 차수 점이 0개나 2개일 때, 그때에만 있습니다.

∑vdeg⁡(v)=2 ∣E∣\sum_{v} \deg(v) = 2\,|E|

위 식은 악수 정리입니다. 모든 점 v의 차수 deg(v)를 더하면(Σ는 '모두 더한다'는 기호입니다) 변의 개수 |E|의 두 배라는 뜻입니다. 버린 것을 다시 얹으면 새 문제가 나옵니다. 색을 얹으면 4색 정리, 길이를 얹으면 최단 경로, 무작위를 얹으면 좁은 세상과 페이지랭크입니다.