짝을 찾는 알고리즘⁠(algorithm)⁠

의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 1931년 부다페스트의 두 논문에서 시작해, 냉전의 비밀 철도 보고서를 거쳐 2012년 노벨 경제학상에 이르렀습니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고, 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 점과 선, 표의 칸은 누르거나 끌 수 있고, 알고리즘 아래의 ◀ ▶ 단추와 막대로 단계를 앞뒤로 오갈 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1940년대 미국의 의과대학 4학년생을 떠올려 봅시다. 졸업 뒤 1년 동안 병원에서 수련할 인턴 자리를 구해야 합니다. 병원은 좋은 학생을 먼저 잡으려 했고, 학생은 좋은 병원을 원했습니다. 경쟁이 붙자 병원들은 채용을 점점 앞당겼습니다. 1940년대 중반에는 수련이 시작되기 거의 2년 전에 합격을 통보하는 일까지 있었다고 합니다. 학생이 어떤 의사가 될지 알기도 전에 자리가 정해진 셈입니다.

1945년 의과대학들은 정해진 날짜 전에는 성적표와 추천서를 내주지 않기로 합의했습니다. 날짜는 뒤로 밀렸지만 새 문제가 생겼습니다. 병원들이 답을 기다려 주지 않게 된 것입니다. 합격 통보에 딸린 답변 기한은 1945년에 열흘이던 것이 1950년 무렵에는 12시간 아래로 줄었다고 전합니다. 전화로 합격을 알리면서 끊기 전에 답하라고 하는 일도 있었습니다. 2지망 병원의 전화를 받은 학생은 곤란해집니다. 1지망의 연락을 기다리다 둘 다 놓칠 수도 있고, 지금 받아들이면 나중에 1지망이 불러도 소용이 없습니다. 약속을 어기고 옮기는 학생도, 그 때문에 빈자리를 안게 되는 병원도 생겼습니다.

1952년 미국의 병원과 의과대학들은 다른 길을 택했습니다. 학생은 가고 싶은 병원의 순서를, 병원은 뽑고 싶은 학생의 순서를 적어 한곳에 내고, 한 번의 계산으로 전국의 짝을 정하는 것입니다. 이 '매치'는 70년이 넘은 지금도 해마다 봄에 열립니다. 이 제도가 왜 버티는지가 밝혀진 것은 한참 뒤였습니다. 10년 뒤 이 제도를 전혀 모르던 두 수학자가 같은 계산법을 따로 찾아냈고, 30여 년 뒤 한 경제학자가 두 계산이 같다는 것을 알아챘습니다. 2012년 그 수학자 가운데 한 사람과 그 경제학자가 노벨 경제학상을 함께 받았습니다.

이 글은 그 계산에 이르는 길을 따라갑니다. 질문은 단순합니다. 누구를 누구와 이어야 할까? 먼저 짝을 지을 수 있기는 한지부터 묻고(1–2절), 짝마다 비용이 붙으면 가장 싼 배정을 찾고(3절), 짝 대신 물건이 흐르는 철도망에서 가장 좁은 병목을 찾은 뒤(4절), 마지막으로 짝이 될 양쪽이 저마다 원하는 것이 있을 때 모두가 받아들일 배정을 찾습니다(5–7절).

1 · 누가 무엇을 할 수 있나짝짓기와 증가 경로⁠(augmenting path)⁠

가장 단순한 경우부터 봅시다. 여섯 사람과 여섯 가지 일이 있습니다. 사람마다 할 수 있는 일이 정해져 있고, 한 사람은 한 가지 일만, 한 가지 일은 한 사람만 맡습니다. 모든 사람에게 일을 줄 수 있을까요? 이 절의 물음은 이것이고, 답을 찾는 방법이 무엇이든 '모든 짝짓기를 다 해 보기'보다 훨씬 빨라야 합니다.

사람과 일을 점으로 찍고, '할 수 있다'를 선으로 이으면 그래프가 됩니다. 그래프는 점들과, 점 두 개씩을 잇는 선들로 이루어진 그림입니다. 쾨니히스베르크의 다리 문제에서 그래프가 태어난 이야기는 「일곱 다리의 도시」에 있습니다. 아래 그림에서 가영은 운전과 요리를, 나래는 운전만, 다솜은 요리·번역·회계를, 라희는 번역만, 마루는 회계·수리·간호를, 바다는 수리만 할 수 있습니다.

이 그래프는 특별한 모양입니다. 점이 두 무리(사람과 일)로 나뉘고, 선은 언제나 다른 무리의 점끼리만 잇습니다. 사람과 사람, 일과 일을 잇는 선은 없습니다. 이런 그래프를 이분 그래프라고 합니다.

이제 선 몇 개를 고릅니다. 예를 들어 가영–운전, 다솜–요리, 라희–번역을 고르면 어느 사람도, 어느 일도 두 번 쓰이지 않습니다. 이렇게 어느 점도 두 번 쓰이지 않는 선들의 집합(모임)을 매칭⁠(matching)⁠이라 하고, 고른 선의 수를 매칭의 크기라 합니다. 가영–운전과 나래–운전을 함께 고르면 운전이 두 번 쓰이니 매칭이 아닙니다. 모든 점이 짝을 찾은 매칭, 여기서는 여섯 쌍짜리 매칭을 완전 매칭⁠(perfect matching)⁠이라고 합니다. 완전 매칭은 사람마다 일을 하나씩, 겹치지 않게, 빠짐없이 정해 주는 짝짓기, 곧 사람의 집합⁠(set)⁠에서 일의 집합으로 가는 일대일 대응⁠(one-to-one correspondence)⁠이면서 선이 있는 곳만 쓰는 대응입니다.

아래 그림에서 직접 짝을 지어 보세요. 선 위의 작은 점을 누르면 그 선이 매칭에 들어가고, 다시 누르면 빠집니다. 한 사람이나 한 가지 일에 선 두 개를 쓸 수는 없습니다. 사람에서 일로(또는 일에서 사람으로) 끌면 선을 새로 긋거나 지울 수 있습니다.

욕심쟁이로 짝짓기 ▶ 증가 경로 한 단계 끝까지 짝 모두 풀기 처음 그림으로

매 순간 가장 쉬워 보이는 선택을 하고 되돌아보지 않는 방법을 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이라고 합니다. 여기서는 막힙니다. 가영이 운전과 요리 가운데 운전을 먼저 가져간 것이 나래의 유일한 길을 막았는데, 욕심쟁이는 그 선택을 되돌아보지 않기 때문입니다.

막혔을 때 다시 처음부터 모든 짝짓기를 시험해 볼 수도 있습니다. 사람이 $n$명이고 누구나 무슨 일이든 할 수 있다면, 첫 사람에게 줄 일이 $n$가지, 둘째에게 남은 $n-1$가지, …이니 짝짓는 방법은 $n \times (n-1) \times \cdots \times 1$가지, 줄여서 $n!$가지('$n$ 팩토리얼⁠(factorial)⁠'), 곧 사람들을 한 줄로 세우는 순열⁠(permutation)⁠의 수만큼 있습니다. 여섯 명이면 720가지라 컴퓨터에게는 아무것도 아닙니다. 하지만 $n!$은 $n$이 조금만 커져도 걷잡을 수 없이 커집니다.

미국의 수학자 조지 댄치그는 70명에게 70가지 일을 배정하는 문제를 즐겨 예로 들었습니다. 댄치그는 선형 계획법⁠(linear programming)⁠, 곧 일차식으로 된 여러 제약 조건을 지키면서 일차식으로 된 목표(비용이나 이익)를 가장 작게 또는 크게 만드는 방법을 세운 사람입니다. 그 문제는 짝짓는 방법이 $70! \approx 1.2 \times 10^{100}$가지(1 뒤에 0이 100개쯤 붙은 수)로, 관측 가능한 우주의 입자 수로 흔히 어림하는 $10^{80}$보다 훨씬 많습니다. 이렇게 큰 수를 어림하는 도구가 스털링 공식⁠(Stirling's formula)⁠이고, 세지 않고 세는 방법들은 「세지 않고 세기」에서 다룹니다. 참고로 이 그림의 선들로 만들 수 있는 완전 매칭은 가지뿐입니다.

하나씩 다 해 보는 대신, 막힌 자리에서 조금씩 고치는 방법이 있습니다. 욕심쟁이가 만든 다섯 쌍은 가영–운전, 다솜–요리, 라희–번역, 마루–회계, 바다–수리입니다. 욕심쟁이가 멈춘 뒤 '증가 경로'를 찾으면 그림에 이런 길이 나타납니다.

짝 없는 사람 나래에서 출발해, 짝이 아닌 선(→)과 지금 짝인 선(⇒)을 번갈아 밟아서 짝 없는 일인 간호에 닿는 길입니다. 이런 길을 증가 경로라고 합니다. 이 길 위에서 짝을 모두 뒤집어 봅시다. 노란 선은 새로 짝이 되고, 분홍 점선은 짝에서 빠집니다. 나래는 운전을 얻고, 운전을 내준 가영은 요리로, 요리를 내준 다솜은 회계로, 회계를 내준 마루는 비어 있던 간호로 옮깁니다. 길 위에서 짝 아닌 선이 짝인 선보다 언제나 하나 많으니, 뒤집으면 짝이 정확히 하나 늡니다. 한 사람을 넣으려고 세 사람이 자리를 옮긴 것입니다.

증가 경로가 있으면 매칭을 키울 수 있습니다. 더 중요한 것은 거꾸로도 성립한다는 점입니다. 증가 경로가 없으면, 지금의 매칭이 가장 크다. 흔히 '더 고칠 데가 안 보이면 그게 최선'이라는 말은 믿을 수 없지만(욕심쟁이도 더 고칠 데가 안 보여서 멈췄습니다), 증가 경로라는 특정한 모양이 없다는 것은 최선이라는 증거가 됩니다. 까닭은 이렇습니다.

지금의 매칭 $M$보다 큰 매칭 $M'$이 있다고 해 봅시다($M'$은 '엠 프라임'이라 읽고, $M$과 다른 매칭 하나를 가리킵니다). 두 매칭을 겹쳐 놓고, 둘 다에 속한 선은 지우고 한쪽에만 속한 선만 남깁니다. 한 점에는 $M$의 선이 많아야 하나, $M'$의 선이 많아야 하나 닿으니, 남은 선들은 한 점에서 많아야 두 갈래로만 이어집니다. 그래서 남은 선들은 $M$의 선과 $M'$의 선이 번갈아 나오는 길이나 고리로 나뉩니다.

고리에는 두 매칭의 선이 똑같이 들어 있고, 길에서는 두 매칭의 선 수가 많아야 하나 차이 납니다. $M'$의 선이 전체로 더 많으려면, $M'$의 선이 하나 더 많은 길이 적어도 하나 있어야 합니다. 그 길은 $M'$의 선으로 시작하고 끝납니다. 길의 양 끝 점에는 $M$의 선이 닿지 않으니($M$에만 있는 선이 닿았다면 길이 거기서 이어졌을 것이고, 두 매칭에 모두 있는 선이 닿았다면 그 점에 $M'$의 선이 둘 닿게 됩니다), 양 끝이 $M$에서 짝이 없는 점입니다. 곧 이 길은 $M$의 증가 경로입니다. 따라서 더 큰 매칭이 있으면 증가 경로가 있고, 같은 말로 증가 경로가 없으면 더 큰 매칭이 없습니다.

그래서 가장 큰 매칭을 찾는 알고리즘은 간단합니다. 증가 경로를 찾아 뒤집기를, 더는 찾을 수 없을 때까지 되풀이합니다. 이분 그래프⁠(bipartite graph)⁠에서는 증가 경로를 한 번 찾는 데 선의 수에 비례하는 시간이 들고, 짝은 많아야 $n$번 늘어나니 전체 걸음 수는 $n$과 선의 수의 곱에 비례하는 정도입니다. 선은 많아야 $n \times n$개이니 걸음 수는 많아야 $n^3$에 비례합니다. 70명이면 $70^3 = 343{,}000$ 정도로, $10^{100}$과는 비교가 되지 않습니다. 걸음 수가 $n!$이 아니라 다항식⁠(polynomial)⁠인 것입니다. 이렇게 걸음 수가 $n^2$, $n^3$처럼 $n$의 거듭제곱 정도로 자라는 것을 다항식 시간이라 합니다(점근 표기법⁠, asymptotic notation⁠). 이분 그래프가 아니면 증가 경로를 찾기가 훨씬 까다로워서, 7절에 나오는 에드먼즈의 1965년 알고리즘이 필요합니다.

이분 그래프에서는 1930년대에 이미 부다페스트의 수학자 쾨니그 데네시가 이 사실을 쓰고 있었고, 모든 그래프로 넓혀 깔끔하게 적은 사람은 1957년 파리의 수학자 클로드 베르주입니다. 정리하면, 가장 큰 매칭은 모든 짝짓기를 시험하지 않고 '증가 경로를 찾아 뒤집기'만 되풀이해서 찾을 수 있고, 증가 경로가 더 없다는 것이 곧 최대라는 증거입니다.

증가 경로의 모양은 뒤에서 세 번 더 나옵니다. 3절의 헝가리안 방법⁠(Hungarian method)⁠, 4절의 흐름을 늘리는 경로, 그리고 5절에서 한 사람이 밀려나면 다음 사람에게 차례가 넘어가는 연쇄입니다. 모두 '막힌 곳에서 한 칸씩 밀어내 자리를 만든다'는 같은 생각입니다.

2 · 짝이 모자랄 때홀의 결혼 정리와 쾨니그의 덮개⁠(cover)⁠

증가 경로가 끝내 없으면 완전 매칭은 없습니다. 그런데 "없다"는 답을 사람에게 어떻게 납득시킬까요? "알고리즘을 돌렸더니 안 되더라"는 믿으라는 말일 뿐입니다. 좋은 답은 이유를 보여 줍니다. 이 절의 물음은 이것입니다. 완전 매칭이 없을 때, 누구나 손으로 확인할 수 있는 짧은 이유가 늘 있을까?

아래 그림은 선이 조금 다른 새 판입니다. 이번에는 사람을 누르면 그 사람이 모둠 $S$에 들어가고(분홍), $S$의 사람들이 할 수 있는 일들, 곧 그들의 선이 닿는 일들의 합집합(어느 한 사람이라도 할 수 있는 일을 모두 모은 것) $N(S)$가 함께 분홍으로 칠해집니다. $N(S)$는 '$S$의 이웃'이라는 뜻으로 읽습니다. 1절처럼 끌어서 선을 긋거나 지울 수도 있습니다.

▶ 범인 찾기 모둠 비우기 처음 그림으로

세 사람이 두 가지 일을 나눠 가질 수 없다는 것은 비둘기집 원리(비둘기가 비둘기집보다 많으면 어느 집엔가 둘이 들어간다)입니다. 완전 매칭이 있다면 가영, 나래, 라희는 서로 다른 일 셋을 받아야 하는데, 그 셋은 모두 세 사람이 할 수 있는 일, 곧 $N(S)$에 들어 있어야 합니다. 그러니 완전 매칭이 있으려면 적어도 다음 조건이 필요합니다. 어떤 사람들 $S$를 골라도 그들이 할 수 있는 일이 $S$의 사람 수 이상이어야 합니다.

식을 말로 읽으면 '사람들 가운데 어떤 모둠 $S$를 골라도($\subseteq$는 '의 일부분이다'라는 뜻입니다), $N(S)$에 든 일의 수가 $S$에 든 사람의 수보다 작지 않다'입니다. 세로 막대 $|\;|$는 모임에 든 것의 개수를 뜻합니다. 앞의 예에서는 $|S| = 3$, $|N(S)| = 2$라서 조건이 깨졌습니다.

이 조건은 필요조건입니다. 완전 매칭이 있으면 반드시 성립한다는 뜻입니다. 1935년 케임브리지의 필립 홀은 뻔해 보이는 이 필요조건⁠(necessary condition)⁠이 충분하기도 하다는 것을 증명했습니다. 곧 사람과 일의 수가 같을 때, 모든 모둠이 이 조건을 지키기만 하면 완전 매칭이 반드시 있습니다. 이것이 홀의 정리⁠(Hall's theorem)⁠입니다. 뒤집어 말하면, 완전 매칭이 없을 때는 언제나 '이 사람들은 할 수 있는 일이 사람 수보다 적다'는 모둠이 있고, 그 모둠이 바로 짧은 이유가 됩니다.

그러나 그 모둠을 어떻게 찾을까요? 홀의 조건을 그대로 검사하려면 모든 모둠, 곧 사람들의 멱집합(모든 부분집합⁠(subset)⁠의 모임)을 봐야 합니다. 사람마다 넣을지 뺄지 두 갈래이니 $n$명이면 $2^n$개로, 여섯 명이면 64개, 서른 명이면 10억 개가 넘게 지수함수⁠(exponential function)⁠처럼 불어납니다.

'범인 찾기'는 모든 모둠을 보지 않습니다. 순서는 이렇습니다.

1. 1절의 방법으로 가장 큰 매칭을 구합니다. 증가 경로가 더는 없습니다.
2. 짝 없는 사람 하나에서 출발해, 그 사람이 할 수 있는 일로 가고, 그 일의 지금 짝인 사람으로 가고, 다시 그 사람이 할 수 있는 일로 가기를 되풀이합니다. 증가 경로를 찾던 것과 같은 걸음입니다. 이렇게 닿는 사람과 일을 모두 모읍니다.
3. 모은 일에는 모두 이미 짝이 있습니다. 짝 없는 일에 닿았다면 그 길이 증가 경로였을 텐데, 증가 경로는 없기 때문입니다. 그리고 모은 일의 짝은 2단계에서 모두 모은 사람 안에 들어왔습니다.
4. 그러니 모은 사람은 '모은 일 하나마다 그 짝 한 명'에 출발한 짝 없는 사람까지 더해, 모은 일보다 적어도 한 명 많습니다. 또 모은 사람들이 할 수 있는 일은 모두 2단계에서 모은 일 안에 있습니다. 이 모둠이 홀의 조건을 깹니다.

조건을 깨는 모둠이 알고리즘의 부산물로 저절로 나오는 것입니다.

같은 계산이 또 하나의 증거를 줍니다. 모든 선이 적어도 한쪽 끝에서 닿는 점들의 모임, 곧 덮개를 생각해 봅시다. 이 판에서는 예를 들어 운전, 번역, 다솜, 수리, 간호 다섯 점이 덮개입니다. 가영·나래·라희의 선은 모두 운전이나 번역에 닿고, 다솜의 선은 다솜에, 마루의 선은 번역이나 수리에, 바다의 선은 수리나 간호에 닿기 때문입니다.

매칭의 선들은 끝점을 공유하지 않으니, 덮개에는 매칭의 선마다 그 선의 끝점이 적어도 하나씩, 서로 다른 점으로 들어 있어야 합니다. 그러니 언제나 (매칭의 크기) ≤ (덮개의 크기)입니다. 1931년 쾨니그는 이분 그래프에서는 가장 큰 매칭의 크기와 가장 작은 덮개의 크기가 언제나 같다는 것을 보였습니다.

'범인 찾기'를 누르면 흰검은 고리로 그런 덮개가 표시됩니다. 매칭 5쌍과 점 5개. 누군가 "이 그래프의 매칭은 5쌍이 최대입니다"라고 주장하면, 5쌍짜리 매칭과 5개짜리 덮개를 함께 내밀면 됩니다. 매칭은 5쌍이 가능하다는 증거이고, 덮개는 6쌍이 불가능하다는 증거입니다. 둘 다 손으로 금방 확인할 수 있습니다. 매칭이 정말 매칭인지(어느 점도 두 번 쓰이지 않는지)와 덮개가 정말 덮개인지(모든 선이 흰검은 고리에 닿는지)만 보면 됩니다.

이것은 사소한 일이 아닙니다. 1965년 미국의 수학자 잭 에드먼즈는 "그렇다"와 "아니다"에 모두 짧게 확인할 수 있는 증거가 있는 문제를 '좋은 특성화⁠(good characterization)⁠'가 있는 문제라 부르고, 그런 문제에는 빠른 알고리즘이 있으리라 기대했습니다. 매칭은 그 대표였습니다. 반대로 모든 점을 한 번씩만 지나 제자리로 돌아오는 길을 찾는 해밀턴 회로⁠(Hamiltonian cycle)⁠처럼 "있다"의 증거는 쉽지만 "없다"의 짧은 증거는 알려지지 않은 문제들도 있습니다. 이 차이가 「기계가 풀 수 없는 문제」의 P 대 NP 문제와 맞닿아 있습니다.

정리하면, 완전 매칭이 없을 때는 '할 수 있는 일이 사람 수보다 적은 모둠'이, 매칭이 더 커질 수 없을 때는 '같은 크기의 덮개'가 짧은 이유가 되고, 둘 다 증가 경로 알고리즘이 덤으로 찾아 줍니다.

홀이 쓴 말은 짝짓기가 아니라 '부분집합들의 대표'였습니다. 집합이 여러 개 있을 때 집합마다 원소⁠(element)⁠ 하나씩을 서로 겹치지 않게 대표로 뽑을 수 있느냐는 물음이었습니다. 사람마다 '할 수 있는 일의 집합'이 있고 거기서 일 하나씩을 겹치지 않게 뽑는 것이니 같은 물음입니다. 1950년 시카고 대학에 있던 폴 핼모스는 허버트 본과 함께 이 정리를 수학적 귀납법⁠(mathematical induction)⁠으로 짧게 다시 증명하면서, 저마다 아는 사람들 가운데서 결혼 상대를 찾는 이야기로 설명했습니다. 그 뒤로 이 정리는 '결혼 정리'라고도 불립니다.

쾨니그의 정리⁠(Kőnig's theorem)⁠에는 앞선 사연이 있습니다. 1927년 빈의 수학자 카를 멩거는, 그래프에서 두 점 무리를 잇는 서로 겹치지 않는 길의 최대 개수가 두 무리를 떼어 놓으려고 지워야 하는 점의 최소 개수와 같다는 정리를 발표했습니다. 그런데 그 증명은 이분 그래프의 경우를 증명 없이 가정하고 있었고, 쾨니그의 1931년 논문이 바로 그 빈틈을 채웠습니다. '가장 큰 것 = 가장 작은 것'이라는 모양으로 적힌 조합의 정리로는 멩거의 것이 첫 예로 꼽힙니다.

완전 매칭이 반드시 있다는 가장 이른 정리는 1891년 코펜하겐의 율리우스 페테르센에게서 나왔습니다. 모든 점에 선이 세 개씩 붙어 있고, 끊으면 그래프가 둘로 갈라지는 선이 하나도 없다면 완전 매칭이 반드시 있다는 것입니다. 이 물음은 그래프가 아니라 대수에서 왔습니다. 당시 수학의 큰 주제였던 불변식 이론(변수를 바꾸어 적어도 값이 변하지 않는 식을 찾는 이론)에서는 식을 점과 선의 그림으로 나타내곤 했습니다. 그러면 식을 더 작은 식들의 곱으로 쪼개는 문제가, 그림을 선이 몇 개씩 붙은 부분 그래프들로 쪼개는 문제가 됩니다. 페테르센은 1889–91년 이 문제를 두고 실베스터, 힐베르트, 클라인과 편지를 주고받았습니다. 짝짓기는 처음부터 다른 수학의 도구로 태어난 셈입니다.

완전 매칭은 무한 집합에서도 뜻이 있습니다. 칸토어는 두 집합 사이에 빠짐없는 짝짓기, 곧 일대일 대응이 있으면 두 집합의 크기⁠(cardinality)⁠가 같다고 정의했습니다(집합의 크기, 「무한에도 크기가 있다」). 다만 무한히 많은 사람이 있으면 홀의 조건만으로는 모자랄 수 있습니다. 사람도 일도 1번, 2번, 3번, …처럼 끝없이 있고, k번 사람은 k번 일만 할 수 있다고 합시다. 여기에 모든 일을 할 수 있는 0번 사람을 더하면, 어떤 유한 모둠도 조건을 지키지만 모두에게 일을 줄 수는 없습니다. 1번부터의 사람들이 일을 하나씩 모두 가져가 0번 사람의 몫이 남지 않기 때문입니다. 사람마다 할 수 있는 일이 유한 개라면 이런 일은 생기지 않아서, 무한에서도 홀의 조건으로 충분하다는 것이 알려져 있습니다. 쾨니그의 1936년 교과서 제목이 『유한 및 무한 그래프의 이론』인 데서 보듯, 무한 그래프는 처음부터 이 분야의 관심사였습니다.

3 · 부다페스트에서 온 이름배정 문제⁠(assignment problem)⁠와 헝가리안 방법

이제 선마다 수가 붙습니다. 누구나 무슨 일이든 할 수 있지만, 걸리는 시간이 사람마다 다릅니다. 다섯 사람에게 다섯 가지 일을 하나씩 나눠 줄 때 걸리는 시간의 합을 가장 작게 하려면 어떻게 해야 할까요? 이것을 배정 문제라고 합니다. 이 절의 물음은 이것입니다. 가능한 배정을 모두 따져 보지 않고 가장 좋은 배정을 찾을 수 있을까? 그리고 찾은 답이 가장 좋다는 것을 어떻게 보일까? 표로 쓰면 $5 \times 5$ 행렬(수를 가로 5줄, 세로 5줄의 표로 늘어놓은 것. 가로줄을 행, 세로줄을 열이라 합니다)에서 행마다 하나, 열마다 하나씩 칸 다섯 개를 골라 합을 가장 작게 하는 문제입니다.

고른 칸 지우기

이제 기계적인 방법을 한 단계씩 봅시다. 아래 단계 막대를 앞으로 넘기면 표의 수가 줄어들며 0(초록)이 늘어납니다. 보라 띠가 몇 줄 필요한지, 그리고 언제 멈추는지를 보세요. 칸에 마우스를 올리면 그 수가 원래 시간에서 무엇을 빼서 나왔는지 보입니다. 새 문제 처음 문제

생각은 둘입니다. 첫째, 한 행 전체에서 같은 수를 빼도 가장 좋은 배정은 바뀌지 않습니다. 처음 문제의 가영 행은 5, 9, 2, 8, 8입니다. 여기서 가장 작은 2를 모두 빼면 3, 7, 0, 6, 6이 됩니다. 가영은 어떤 배정에서든 정확히 한 가지 일을 맡으니, 모든 배정의 합이 똑같이 2씩 줄어듭니다. 순위가 그대로이니 가장 좋은 배정도 그대로입니다. 일마다 한 사람이 맡으니 열에서 빼도 마찬가지입니다.

그래서 행과 열에서 적당히 빼서 0을 만들어 갑니다. 모든 칸이 0 이상인 채로 서로 다른 행과 열의 0 다섯 개를 고를 수 있게 되면, 그 배정이 가장 좋습니다. 고친 표에서 그 배정의 합은 0이고, 모든 칸이 0 이상이니 0보다 작은 합은 없기 때문입니다.

둘째, 서로 다른 행과 열의 0을 몇 개까지 고를 수 있는지는 1절의 매칭 문제입니다. 0이 있는 칸을 '할 수 있다'는 선으로 보면 됩니다. 2절의 쾨니그 정리에 따르면 그 최대 개수는 0을 모두 덮는 가장 적은 선(행이나 열)의 수와 같습니다. 선이 4개로 충분하면 0 다섯 개는 불가능하다는 뜻이고, 그 선들이 어디를 고칠지 알려 줍니다. 처음 문제에서 행마다, 열마다 가장 작은 수를 빼고 나면 가영과 나래의 0이 둘 다 번역 열에만 있습니다. 두 사람이 한 열의 0을 나눠 가질 수 없으니 0은 많아야 넷까지 고를 수 있고, 실제로 선 4개로 모든 0이 덮입니다. 행에서 뺀 값과 열에서 뺀 값을 조정해 덮이지 않은 곳에 새 0을 만들고, 다시 덮어 봅니다. 선이 다섯 개 필요해지면 끝입니다.

끝까지 돌리면 뜻밖의 답이 나옵니다. 가영 번역(2), 나래 요리(3), 다솜 수리(9), 라희 운전(3), 마루 회계(4)로 합이 21시간입니다. 다솜에게 가장 오래 걸리는 수리(9시간)가 돌아갑니다. 다솜이 7시간에 할 수 있는 운전, 요리, 번역은 다른 사람들이 훨씬 빨리 하니까요. 흔히 '각자에게 가장 좋은 선택을 모으면 모두에게 가장 좋다'고 생각하지만, 각자의 최선을 모은 것이 모두에게 가장 좋은 배정은 아닙니다.

끝났을 때 행과 열에서 뺀 값을 모두 더하면 가장 좋은 배정의 합과 정확히 같습니다. 이 값들은 일종의 '가격'입니다. 사람 $i$에게 매긴 값을 $u_i$, 일 $j$에 매긴 값을 $v_j$, 사람 $i$가 일 $j$를 하는 데 걸리는 시간을 $c_{ij}$라 합시다. 모든 칸에서 $u_i + v_j \le c_{ij}$(사람의 값과 일의 값을 더해도 그 칸의 시간을 넘지 않는다)가 지켜지면, 어떤 배정의 합도 $\sum u_i + \sum v_j$(모든 사람의 값과 모든 일의 값을 더한 것, Σ는 '모두 더하라'는 기호)보다 작을 수 없습니다.

까닭은 한 줄입니다. 배정은 행과 열을 하나씩 다 쓰니, 배정한 다섯 칸의 $c_{ij}$를 더하면 칸마다 $u_i + v_j$ 이상이고, 그 $u_i + v_j$ 다섯 개를 더하면 모든 $u_i$와 모든 $v_j$를 한 번씩 더한 것이 됩니다. 그러니 가격표는 "이보다 더 잘할 수는 없다"는 증거가 됩니다. 2절에서 덮개가 매칭의 상한⁠(upper bound)⁠을 증명했던 것과 같은 모양이고, 여기서는 덮개가 가격이 된 셈입니다. 이렇게 한 문제의 최댓값과 짝이 되는 다른 문제의 최솟값이 만나는 현상을 쌍대성⁠(duality)⁠이라고 부르며, 최적화⁠(optimization)⁠의 한가운데에 있는 생각입니다.

이 방법의 이름은 1955년 미국 해군 연구청의 학술지에 실린 논문에서 나왔습니다. 당시 필라델피아 근교 브린마 칼리지에 있던 수학자 해럴드 쿤은 쾨니그의 1936년 책에서 헝가리 수학자 에게르바리 예뇌의 1931년 논문을 알게 되었습니다. 쾨니그의 정리를 수가 적힌 행렬⁠(matrix)⁠로 넓힌 논문이었는데, 헝가리어로 되어 있었습니다. 쿤의 회고에 따르면 그는 1953년 헝가리어 문법책과 큰 사전을 들고 스스로 헝가리어를 익혀 그 논문을 번역했고, 그 안의 생각으로 배정 문제를 푸는 방법을 만들었습니다. 그는 이것을 두 헝가리 수학자를 기려 헝가리안 방법이라고 불렀습니다. 1957년 미국의 수학자 제임스 멍크리스는 이 방법이 사람 수의 다항식 걸음 안에 끝난다는 것을 보였습니다. 헝가리어 사전을 펼치기 조금 전, 쿤은 프린스턴에서 앨버트 터커, 데이비드 게일과 함께 한 가지 사실을 증명해 1951년에 발표했습니다. 선형 계획의 쌍대성이 폰 노이만의 게임 이론⁠(game theory)⁠, 곧 두 사람이 동시에 두는 게임의 최소최대 정리⁠(minimax theorem)⁠와 같은 내용이라는 것입니다. 최소최대 정리는 한쪽이 스스로 지킬 수 있는 가장 좋은 몫과 상대가 그 이상은 못 주게 막을 수 있는 몫이 같다는 정리입니다. 배정 문제의 '가격'과 게임의 섞은 전략(여러 수를 정해 둔 확률⁠(probability)⁠로 섞어 두는 전략)이 한 뿌리라는 이야기는 「이기는 쪽이 존재한다」 5절에 있습니다.

짝짓기가 하필 부다페스트에서 자란 데에는 까닭이 있습니다. 1894년 헝가리에서는 고등학생을 위한 수학 잡지와 전국 경시대회가 함께 시작되었고, 문제를 받아 오래 붙잡고 풀이를 글로 적는 습관이 온 나라 학생들에게 퍼졌습니다(부다페스트의 수학자들). 그 경시대회에 나온 파티 문제 하나가 어떻게 한 이론의 입구가 되었는지는 「완전한 무질서는 없다」에 있습니다. 쾨니그는 그 첫 세대였습니다. 열다섯 살이 되기 전인 1899년에 첫 논문을 냈고, 1902년 졸업하던 해에 경시대회에서 1등을 하고 61쪽짜리 『수학 놀이』를 펴냈습니다. 그다음 그는 괴팅겐에서 다섯 학기를 공부하며 1904–05년 민코프스키의 위상수학⁠(topology)⁠ 강의를 들었습니다. 당시 이 분야는 오일러가 다리 문제를 넣었던 바로 그 이름, '위치 해석⁠(analysis situs)⁠'으로 불렸습니다. 같은 무렵 그는 힐베르트와 고르단의 불변식 이론⁠(invariant theory)⁠ 논문을 읽다가, 그 논문들이 인용한 페테르센의 그래프 논문(2절)을 만났다고 합니다. 놀이와 위상수학과 대수가 한 사람 안에서 만난 것입니다. 부다페스트로 돌아와 공과대학에서 가르친 그의 그래프 이론 강의에는 뒷날 1학년생 에르되시가 갈라이 티보르와 함께 앉았고, 에르되시는 고등학생 때 그 수학 잡지에 실린 쾨니그의 글을 읽고 그래프에 관심을 가졌다고 회고했습니다.

이야기에는 뒤늦은 반전이 있습니다. 2000년대에 들어 프랑스의 수학자 프랑수아 올리비에는 19세기 독일 수학자 카를 구스타프 야코프 야코비의 유고에서, 사실상 헝가리안 방법과 같은 절차를 찾아냈습니다. 쾨니히스베르크와 베를린에서 일한 야코비가 1851년 세상을 떠난 뒤 1890년에 라틴어로 출판된 글이었습니다. 쿤은 말년에 이 발견을 직접 소개했습니다. 좋은 생각이 한 세기 동안 잠들어 있었던 것입니다. 한편 레닌그라드의 수학자이자 경제학자 레오니트 칸토로비치는 1939년 합판 공장의 기계 배정 문제에서 선형 계획법의 뼈대를 세우며 그 '가격'에 경제적인 뜻을 주었습니다. 그의 이야기는 최적 수송⁠(optimal transport)⁠과 함께 「까마귀와 택시」에 있습니다.

생각이 건너간 길. 1931년 부다페스트의 논문이 1953년 브린마에서 번역되어 헝가리안 방법이 되었고(주황), 1935년 케임브리지의 홀의 정리는 1950년 시카고에서 '결혼 문제'라는 이름을 얻었습니다(파랑). 노란 선은 사람의 이동으로, 쾨니히스베르크에서 베를린으로 옮긴 야코비와 괴팅겐에서 위상수학 강의를 들은 쾨니그의 길입니다. 보라 선은 1927년 빈의 멩거 정리에 남은 빈틈을 1931년 부다페스트의 쾨니그가 채운 길입니다.

배정 문제와 매칭은 다른 곳에서도 행렬과 이어집니다. 1917년 무렵 베를린의 수학자 게오르크 프로베니우스는 이런 행렬을 따졌습니다. 어떤 칸은 0으로 정해져 있고, 나머지 칸에는 저마다 다른 변수가 들어 있습니다. 이 행렬의 행렬식⁠(determinant)⁠이 변수에 무엇을 넣어도 늘 0이 되는 것은 언제일까요? 답은 0이 아닌 칸만으로 행마다 하나, 열마다 하나씩 칸을 고를 수 없을 때, 그리고 그때뿐입니다. 0이 아닌 칸을 '할 수 있다'는 선으로 보면 완전 매칭이 없을 조건과 같은 내용입니다. 행렬식은 $n!$개의 항, 곧 행과 열을 하나씩 고르는 모든 방법의 곱을 부호를 붙여 더한 것이니, 완전 매칭들을 모두 늘어놓은 식이기도 합니다. 가장 작은 예로 2 × 2 행렬의 행렬식은 $ad - bc$입니다(첫 행이 $a, b$, 둘째 행이 $c, d$). 항 $ad$는 1행 1열과 2행 2열을, $bc$는 1행 2열과 2행 1열을 고른 것입니다. $b$와 $d$가 0으로 정해져 있으면 0 아닌 칸 $a$, $c$가 모두 1열에 있어 행과 열을 하나씩 고를 수 없고, 실제로 행렬식은 $a \cdot 0 - 0 \cdot c = 0$입니다. 쾨니그가 1916년 논문의 제목에 '행렬식 이론에의 응용'을 넣은 것도 그 때문입니다.

4 · 철도를 끊는 법최대 흐름⁠(maximum flow)⁠과 최소 절단⁠(cut)⁠

이 절의 물음은 이것입니다. 선마다 나를 수 있는 양에 한계가 있는 망에서, 한 곳에서 다른 곳으로 가장 많이 보낼 수 있는 양은 얼마일까? 그리고 그것이 가장 많다는 것은 무엇으로 보일까? 짝짓기는 이 물음의 특별한 경우라는 것이 곧 드러납니다.

1950년대 초 캘리포니아 샌타모니카의 RAND 연구소는 미 공군을 위해 일하는 싱크탱크였습니다. 그곳의 수학자 테드 해리스는 유럽에서 육군 수송 부대를 이끌었던 퇴역 장군 프랭크 로스와 함께 철도망을 연구하고 있었습니다. 물음은 이랬습니다. 소련 서부에서 동유럽으로 철도로 하루에 얼마나 많은 물자를 보낼 수 있을까? 그리고 그 흐름을 끊으려면 어디를 쳐야 할까?

두 사람은 철도 노선이 만나는 역 하나하나 대신 철도 관리 구역을 점으로, 이웃한 구역 사이의 하루 수송 능력을 선의 용량으로 삼았습니다. 1955년 10월 공군에 낸 비밀 보고서 「철도망 용량⁠(capacity)⁠ 평가 방법의 기초⁠(basics)⁠」에서 그들은 소련 서부와 동유럽의 철도를 점 44개와 연결 105개의 망으로 줄였습니다. 계산 결과 소련에서 폴란드, 체코슬로바키아, 동독 같은 '위성국'으로 보낼 수 있는 흐름은 16만 3천 톤이었고, 보고서는 용량의 합이 똑같이 16만 3천 톤인 연결들의 묶음을 '병목'이라는 이름으로 지도에 그렸습니다.

공군력은 적의 철도망을 차단하는 효과적인 수단이며, 그런 쓰임은 이 군의 논리적이고 중요한 임무다.— 해리스와 로스, 「철도망 용량 평가 방법의 기초」(1955)

보고서는 기밀로 묻혀 있다가 네덜란드의 수학자 알렉산더르 스레이버르의 요청으로 1999년 5월에야 기밀에서 풀렸고, 2002년 그의 논문을 통해 널리 알려졌습니다. 같은 소련 철도망은 한 세대 전에 이미 수학의 대상이었습니다. 1930년 소련 교통 인민위원부가 낸 책에서 수송 전문가 A. N. 톨스토이는 소금과 시멘트 같은 화물을 철도로 옮기는 총 거리를 줄이는 방법을 다루고, 공급지 10곳과 수요지 68곳의 문제를 풀었습니다. 한쪽은 철도를 가장 잘 쓰는 법을, 다른 쪽은 가장 잘 끊는 법을 계산한 셈입니다.

아래 그림은 그런 망을 흉내 낸 작은 모형입니다. 오른쪽(동쪽)의 S에서 왼쪽(서쪽)의 T로 물자를 보냅니다. 선마다 적힌 $f/c$는 지금 보내는 양 $f$와 용량 $c$입니다(분수가 아니라 '$c$ 가운데 $f$'라고 읽으면 됩니다). 예를 들어 S에서 c로 가는 선의 용량은 9입니다. 점과 연결의 이름, 용량은 설명을 위해 지어낸 것입니다.

최소 절단 보기 처음 용량으로

규칙은 두 가지입니다. 어느 선도 화살표를 거슬러 나르거나 용량보다 많이 나를 수 없고, S와 T가 아닌 점은 받은 만큼 내보내야 합니다. 쌓아 둘 곳이 없는 중간역입니다. 예를 들어 a가 S에게서 4를 받았다면, a에서 나가는 선들로 모두 합해 정확히 4를 내보내야 합니다. 이 두 번째 규칙은 독일의 물리학자 구스타프 키르히호프의 법칙, 곧 전기 회로의 한 점에 들어온 전류는 모두 나간다는 법칙과 같은 모양입니다. 그러면 S에서 T로 보낼 수 있는 가장 큰 양, 곧 최대 흐름은 얼마일까요?

1954년 무렵 해리스에게서 이 문제를 들은 RAND의 수학자 레스터 포드와 레이 풀커슨은 1절과 같은 방법으로 답했습니다. S에서 T까지 아직 여유가 있는 경로를 찾아 그 여유만큼 더 보내고, 더는 찾을 수 없을 때까지 되풀이합니다. 경로의 여유는 경로 위의 선들 가운데 가장 여유가 적은 선이 정합니다. 용량 5짜리 선과 용량 1짜리 선을 차례로 지나는 경로로는 1만 더 보낼 수 있습니다. 위의 단계 막대를 넘기며 노란 경로가 하나씩 더해지는 것을 보세요.

핵심은 경로가 선을 거꾸로 지나가도 된다는 것입니다. 이미 흐름이 있는 선을 거꾸로 지나가는 것은 그 흐름을 되돌린다는 뜻입니다. 여섯 번째 경로 S→c→e→b→d→T를 보세요. c에서 온 3이 e로 들어가 b가 e로 보내던 몫 3을 대신하고, 그만큼 손이 빈 b는 그 3을 b→d로 돌립니다. 먼저 한 선택을 다시 거두어 자리를 만드는 것, 1절에서 가영이 운전을 내주고 요리로 옮긴 것과 같은 수입니다. 흔히 '한 번 보낸 흐름은 확정'이라고 생각하기 쉽지만, 되돌리기를 허락하지 않으면 먼저 고른 경로가 길을 막아 최대에 못 미친 채 멈출 수 있습니다. 1절의 욕심쟁이가 멈춘 것과 같습니다.

실제로 1절의 매칭은 흐름의 특별한 경우입니다. S에서 모든 사람으로, 사람에서 할 수 있는 일로, 모든 일에서 T로 용량 1짜리 선을 그으면 최대 흐름이 곧 최대 매칭입니다.

이제 그림의 a–f를 눌러 S와 함께 묶을 점들을 골라 보세요. 고른 모둠에서 나머지로 나가는 선들을 모두 끊으면 S와 T가 갈라집니다. 이런 선들의 묶음을 절단이라 하고, 그 용량의 합을 절단의 용량이라고 합니다. 모둠 쪽으로 들어오는 선은 세지 않습니다. 끊지 않아도 모둠에서 T로 가는 길을 여는 선이 아니기 때문입니다. 예를 들어 S만 고르면 S에서 나가는 세 선 7 + 5 + 9 = 21이 절단의 용량입니다.

포드와 풀커슨이 1956년 발표한 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 이것입니다. 보낼 수 있는 최대 흐름은 가장 좁은 절단의 용량과 같다. 이 그림의 처음 용량으로는 최대 흐름이 17이고, S와 a, c, f를 묶은 절단이 S→b(5), a→d(1), a→e(3), c→e(3), f→T(5)를 끊어 용량이 정확히 5 + 1 + 3 + 3 + 5 = 17입니다.

'어떤 절단도 흐름보다 작을 수 없다'는 쪽은 직접 해 보기에서 본 대로 쉽습니다. 어려운 쪽은 흐름과 같은 절단이 늘 있다는 것이고, 증명은 알고리즘이 멈춘 자리에 있습니다. 더는 경로가 없을 때, S에서 여유 있는 선(또는 되돌릴 수 있는 선)만 밟아 닿을 수 있는 점들을 모읍니다. T는 여기에 들지 않습니다(들었다면 경로가 있었을 것입니다). 이 모둠에서 나가는 선은 모두 꽉 차 있습니다. 여유가 있었다면 그 끝점도 모둠에 들어왔을 테니까요. 같은 까닭으로 모둠으로 들어오는 선은 모두 비어 있습니다. 흐름이 있었다면 되돌릴 수 있어 그 시작점도 모둠에 들어왔을 것입니다.

이제 모둠에서 밖으로 나가는 양을 셉니다. 중간역은 받은 만큼 내보내므로, S가 내보낸 흐름은 결국 모둠 밖으로 나가는 선들을 지나야 하고, 모둠으로 되돌아오는 양만큼은 빼야 합니다. 곧 (흐름) = (나가는 선의 흐름 합) − (들어오는 선의 흐름 합)입니다. 나가는 선은 꽉 차 있으니 첫 항은 절단의 용량이고, 들어오는 선은 비어 있으니 둘째 항은 0입니다. 그러니 이 절단의 용량이 바로 지금 흐름이고, 흐름은 최대, 절단은 최소입니다. 같은 해 MIT의 정보 이론 연구자 피터 일라이어스, 에이미엘 파인스타인, 그리고 클로드 섀넌도 통신망의 관점에서 같은 정리를 발표했습니다. 쾨니그의 '매칭 = 덮개', 3절의 '배정 = 가격'과 같은 쌍대성이 여기서는 '흐름 = 절단'이 되었습니다.

해리스와 로스가 정말 알고 싶었던 것은 흐름보다 절단이었습니다. 폭격할 곳을 고르는 일이니까요. 같은 정리가 계획하는 쪽에는 수송 능력을, 공격하는 쪽에는 표적을 줍니다. 보고서에는 RAND의 다른 연구자가 만든 '범람법'이라는 어림 계산이 쓰였는데, 그 연구자는 이 방법이 "열 살 아이에게 몇 분이면 가르칠 수 있는 간단한 놀이"라고 자랑했다고 합니다. 최적을 보장하는 포드–풀커슨의 방법은 해리스–로스 보고서가 나온 그해 말에 RAND 보고서로 나왔습니다.

포드–풀커슨 방법은 용량이 정수⁠(integer)⁠이면 흐름이 매번 1 이상 늘어나니 반드시 끝나고, 최대 흐름도 정수로 나옵니다. 매칭의 짝이 반쪽으로 쪼개지지 않는 이유입니다. 그런데 용량에 무리수⁠(irrational number)⁠가 섞이면 경로를 고르는 순서에 따라 흐름이 한없이 조금씩만 늘면서 끝나지 않을 수도 있고, 심지어 최대 흐름이 아닌 값으로 다가갈 수도 있다는 예가 알려져 있습니다. 1972년 에드먼즈와 컴퓨터 과학자 리처드 카프는 이 그림처럼 늘 선의 개수가 가장 적은 경로를 고르면 용량이 무엇이든 다항식 걸음 안에 끝난다는 것을 보였습니다. 그런 경로는 S에서 한 걸음에 닿는 점, 두 걸음에 닿는 점, …처럼 가까운 점부터 넓혀 가며 찾는 너비 우선 탐색⁠(breadth-first search)⁠으로 찾습니다. 최단 경로⁠(shortest path)⁠ 찾기와 같은 방식입니다.

5 · 떠나지 않는 짝안정 매칭⁠(stable matching)⁠과 게일–섀플리

다시 병원과 학생으로 돌아갑시다. 지금까지의 문제에는 한쪽만 있었습니다. 사람은 아무 일이나 받아들였고, 비용은 한 사람이 정했습니다. 인턴 시장은 다릅니다. 학생도 병원도 저마다 원하는 순서가 있고, 아무도 억지로 짝을 받아들이게 할 수 없습니다. 이런 시장에서 좋은 배정이란 무엇일까요? 이 절의 물음은 이것이고, 답은 '가장 행복한 배정'이 아니라 '아무도 몰래 빠져나갈 이유가 없는 배정'입니다.

1962년 브라운 대학의 수학자 데이비드 게일과 RAND 연구소의 수학자 로이드 섀플리는 『미국 수학 월보』에 「대학 입학과 결혼의 안정성⁠(stability)⁠」이라는 짧은 논문을 실었습니다. 게일의 회고에 따르면 계기는 1960년 9월 잡지 『뉴요커』에 실린 한 기사였습니다. 학생들이 여러 대학에 한꺼번에 지원하니, 예일 대학의 입학 담당자들은 합격시킨 학생 가운데 누가 정말 올지 알 수 없어 곤란을 겪는다는 이야기였습니다. 1940년대의 병원들이 겪은 것과 같은 곤란입니다. 그들의 답은 이렇습니다. 학생 $s$와 병원 $h$가 짝이 아닌데, $s$는 지금 자리보다 $h$를 더 원하고 $h$도 지금 뽑은 학생보다 $s$를 더 원한다면, 둘은 배정을 무시하고 따로 손잡을 이유가 있습니다. 이런 쌍을 막는 쌍⁠(blocking pair)⁠이라고 합니다. 예를 들어 학생 가가 병원 B에, 학생 다가 병원 A에 배정되었는데 가는 B보다 A를 원하고 A도 다보다 가를 원한다면, 가와 A가 막는 쌍입니다. 한쪽만 원하는 것으로는 막는 쌍이 되지 않습니다. 가가 A를 원해도 A가 다를 더 원하면, A는 가와 손잡을 이유가 없습니다. 막는 쌍이 하나도 없는 배정이 안정 매칭입니다. 1940년대의 혼란은 바로 막는 쌍들이 저마다 따로 손잡으려 한 결과였습니다.

안정 매칭은 언제나 있을까요? 게일과 섀플리는 있다는 것을, 그것을 찾는 방법으로 보였습니다. 방법의 이름은 수용 유보⁠(deferred acceptance)⁠, 곧 받아들이기를 미룬다는 뜻입니다.

1. 짝 없는 학생은 아직 거절당하지 않은 병원 가운데 가장 가고 싶은 곳에 지원합니다.
2. 병원은 지금까지 받은 지원자 가운데 가장 마음에 드는 한 명만 일단 붙잡아 두고 나머지는 거절합니다. 더 나은 지원자가 오면 붙잡아 두던 학생을 놓아줍니다.
3. 거절당하거나 놓인 학생은 다음 순위 병원에 지원합니다. 아무도 더 지원하지 않으면 붙잡아 둔 짝이 최종 배정입니다.

핵심은 병원이 '예'를 바로 확정하지 않고 끝까지 미룬다는 데 있습니다. 1940년대의 병원들이 12시간 안에 답하라고 몰아붙인 것과 정반대입니다. 아래 그림에서 학생 가–마와 병원 A–E의 순위 목록으로 직접 돌려 보세요. 지금은 쪽이 움직입니다.

새 선호 목록 처음 목록

이 방법이 반드시 끝나고 결과가 안정하다는 증명은 짧습니다. 학생은 목록을 아래로만 내려가므로, 지원은 모두 합쳐도 학생 수 × 병원 수 번을 넘지 않습니다. 병원이 붙잡은 학생은 시간이 갈수록 좋아지기만 합니다. 이제 끝난 뒤에 학생 $s$와 병원 $h$가 막는 쌍이라고 해 봅시다. $s$가 지금 자리보다 $h$를 더 원한다면 $s$는 그 전에 $h$에 지원했다가 거절당했거나 놓여났을 것입니다. 그렇다면 $h$는 그때 $s$보다 나은 학생을 붙잡았고, 그 뒤로는 더 좋아지기만 했으니 지금도 $s$를 원할 리 없습니다. '$h$가 $s$를 더 원한다'는 가정과 부딪히므로(모순), 막는 쌍은 없습니다. 정리하면, 병원이 '예'를 미루기 때문에 한 번 거절한 학생보다 나쁜 학생으로 되돌아가는 일이 없고, 그래서 끝난 뒤에 몰래 손잡을 쌍이 남지 않습니다.

게일과 섀플리는 이 논문을 대학 입학 문제로 시작했지만, 자신들의 방법이 이미 10년째 쓰이고 있다는 것은 몰랐습니다. 1984년 피츠버그 대학의 경제학자 앨빈 로스는 1952년부터 쓰인 미국 인턴 배정 알고리즘을 뜯어보고, 그것이 병원이 제안하는 쪽의 수용 유보와 같다는 것을 보였습니다. 의사들은 수학자보다 10년 먼저, 시행착오로 안정 매칭에 이른 것입니다. 1951년 하버드 의대생들은 처음 발표된 알고리즘이 1지망에 떨어진 학생에게 불리하다고 반발했고, 알고리즘은 시행 직전에 고쳐졌다고 전합니다. 그 고친 결과가 안정한 알고리즘이었습니다.

안정성이 정말 시장을 지키는 힘일까요? 로스는 1990년대 초 영국의 사례에서 증거를 찾았습니다. 1960–70년대 영국의 여러 지역은 저마다 인턴 배정 제도를 따로 만들었습니다. 에든버러와 카디프는 안정한 알고리즘을 썼고, 버밍엄과 뉴캐슬은 학생과 병원의 순위를 섞어 우선순위를 매기는 방식을 썼는데, 이 방식은 안정하지 않은 결과를 낼 수 있습니다. 안정한 두 제도는 살아남았고, 불안정한 방식들은 대부분 버려졌습니다. 다만 케임브리지와 런던 병원처럼 규모가 작은 곳에서는 불안정한 방식도 한동안 유지되었습니다. 조건만 다른 쌍둥이를 견주는 이런 '자연 실험⁠(natural experiment)⁠'의 논리는 「담배와 폐암」의 역학자들이 쓴 것과 같습니다.

안정 매칭은 양쪽이 나뉘어 있을 때만 늘 존재합니다. 게일과 섀플리는 같은 논문에서, 한 무리 안에서 둘씩 방을 나누는 '룸메이트 문제⁠(stable roommates problem)⁠'에서는 안정한 배정이 없을 수도 있음을 네 사람의 예로 보였습니다. 1976년 컴퓨터 과학자 도널드 크누스는 몬트리올 강의를 『안정된 결혼』이라는 프랑스어 책으로 묶어 이 문제를 알고리즘 분석⁠(analysis of algorithms)⁠의 교과서적인 예로 만들었습니다.

6 · 누가 이득을 보나청혼하는 쪽과 거짓말

이 절의 물음은 둘입니다. 안정 매칭이 여럿이면 누구에게 유리한 것이 뽑힐까? 그리고 사람들은 목록을 정직하게 적을 이유가 있을까? 안정 매칭은 하나뿐이 아닐 수 있습니다. 앞 그림에서 움직이는 쪽을 으로 바꾸고 끝까지 돌려 보세요. 지금 목록으로 학생이 지원하면 학생들이 받은 자리의 평균⁠(mean)⁠ 지망은 , 병원들이 받은 학생의 평균 지망은 입니다. 병원이 제안하면 이것이 뒤집혀, 학생 쪽이 , 병원 쪽이 입니다. 두 결과 모두 안정합니다.

게일과 섀플리는 이것이 우연이 아님을 증명했습니다. 움직이는 쪽은 모든 안정 매칭 가운데 가장 좋은 짝을 얻습니다. 학생 한 사람 한 사람이, 어떤 안정 매칭에서 얻을 수 있는 짝 가운데 가장 좋은 짝을 얻는다는 뜻입니다. 증명의 핵심은 이것입니다. 알고리즘이 도는 동안 움직이는 쪽의 누구도, 자기와 짝이 되는 안정 매칭이 하나라도 있는 상대에게서는 거절당하지 않습니다. 움직이는 쪽은 목록을 위에서부터 내려가니, 그런 상대 가운데 가장 좋은 곳에 먼저 닿고 거기서 밀려나지 않습니다.

동시에 기다리는 쪽은 모든 안정 매칭 가운데 가장 나쁜 짝을 얻는다는 것도 곧 밝혀졌습니다. 선호가 무작위라면 그 차이는 큽니다. 1980년대 말 수학자 보리스 피텔의 분석에 따르면 양쪽이 $n$명일 때, 움직이는 쪽이 받는 짝의 평균 순위는 대략 $\ln n$이고 기다리는 쪽은 대략 $n / \ln n$입니다(로그, 확률). $\ln n$('엘엔 n', 자연로그⁠(natural logarithm)⁠)은 약 2.718인 수 e를 몇 번 곱해야 $n$이 되는지를 나타내는 수로, $n$이 10배가 될 때마다 약 2.3씩만 늘어나는 아주 느리게 자라는 수입니다. $\ln 1000 \approx 6.9$입니다. $n$이 클 때의 어림으로, 천 명씩이면 약 7지망 대 약 145지망($1000 / 6.9 \approx 145$)입니다. 1952년의 인턴 매칭은 병원이 제안하는 쪽이었습니다.

두 번째 문제는 정직입니다. 사람들은 목록을 진짜 선호대로 적을까요? 1981년 버클리의 수학자 레스터 듀빈스와 통계학자 데이비드 프리드먼, 그리고 1982년 로스는 움직이는 쪽에게는 거짓말이 결코 이득이 되지 않는다는 것을 보였습니다. 학생이 지원하는 방식이라면, 다른 사람들이 무엇을 적든 학생에게 진짜 순서보다 나은 거짓 목록은 없습니다. 그런데 로스는 같은 논문에서, 결과가 늘 안정하면서 양쪽 모두에게 거짓말이 이득이 되지 않는 방법은 없다는 것도 증명했습니다. 당연해 보이는 조건 몇 개를 한꺼번에 지키는 규칙이 없다는 이런 정리에는 가까운 친척이 있습니다. 공정한 투표 규칙은 없다는, 케네스 애로가 증명한 애로의 정리입니다(「불가능의 증명」 8절). 누군가는 거짓말의 유혹을 받습니다.

A가 나를 지우면 A는 5지망 대신 3지망 라를 얻고, 병원 C와 E도 덩달아 더 나은 학생을 얻습니다. 라와 마까지 지우면 A는 1지망 다를 얻고, 결과는 병원이 제안했을 때와 똑같아집니다. 병원들이 이득을 보는 만큼 학생들 가운데 여럿은 더 나쁜 자리로 밀립니다. 물론 이런 거짓말은 위험합니다. 다른 사람들의 목록을 잘못 짐작하면 A는 아무도 받지 못할 수 있습니다. 실제로 수천 명이 참가하는 시장에서는 남의 목록을 알 수 없고, 안정 매칭이 몇 개 없는 경우가 많아 이런 조작으로 얻을 것이 적다는 연구가 뒤따랐습니다.

1990년대에 이 문제가 현실의 논쟁이 되었습니다. 학생 단체들은 병원이 제안하는 알고리즘이 병원에 유리하게 짜여 있다고 비판했습니다. 부부 의사도 늘었습니다. 두 사람이 같은 도시에서 자리를 얻어야 하니, 부부는 병원 하나가 아니라 병원 쌍에 순위를 매깁니다. 로스는 1984년 이미 부부가 끼면 안정 매칭이 아예 없을 수도 있음을 보인 바 있습니다. 1995년 전국 매칭 위원회의 의뢰로 로스와 경제학자 엘리엇 퍼랜슨은 알고리즘을 다시 설계했습니다. 학생(지원자)이 지원하는 수용 유보를 뼈대로 부부의 지원을 하나씩 끼워 넣는 방법이었고, 1997년 5월 채택되어 1998년 봄의 매치부터 쓰였습니다. 옛 알고리즘과 새 알고리즘을 같은 목록에 돌려 보니 결과가 달라지는 지원자는 1,000명에 1명꼴로 아주 적었다고 보고되었습니다. 이론상 크게 벌어질 수 있는 차이가 실제 시장에서는 작았던 것입니다. 로스–퍼랜슨 방식은 그 뒤 여러 전문직 노동 시장으로 퍼졌습니다.

순위 목록은 결국 줄 세우기입니다. 다섯 병원을 세우는 방법은 $5! = 120$가지이고, 학생 다섯과 병원 다섯의 목록 전체는 $120^{10}$가지로 불어납니다. 줄 세우기의 개수가 비교 몇 번으로 순서를 정할 수 있는지의 한계를 정한다는 이야기는 「줄 세우기의 한계」에 있습니다.

7 · 시장을 설계하다학교 선택과 신장 교환⁠(kidney exchange)⁠

돈이 가격을 정하는 보통의 시장에서는 값을 올리고 내리는 것만으로 수요와 공급이 맞춰집니다. 하지만 어떤 시장에서는 가격을 쓸 수 없거나 쓰지 않기로 합니다. 공립학교의 자리는 팔지 않고, 장기는 사고팔 수 없습니다. 그런 곳에서는 누가 무엇을 받을지를 규칙이 정해야 하고, 그 규칙이 잘못되면 사람들은 규칙을 우회합니다. 1940년대의 인턴 시장이 그랬습니다. 게일–섀플리 이후의 경제학자들은 이런 규칙을 기계처럼 설계하기 시작했고, 이 분야를 시장 설계라고 부릅니다. 이 절에서는 앞의 정리들이 학교와 병원의 실제 규칙이 되면서 무엇이 달라졌는지, 그리고 수학이 어디서 멈추는지를 봅니다.

학교 선택. 2003년 경제학자 아틸라 압둘카디로글루와 타이푼 쇤메즈는 학교 배정을 매칭 문제로 다룬 논문을 냈습니다. 학교마다 형제가 다니는지, 집이 가까운지 같은 우선순위가 있고 학생마다 선호가 있으니 인턴 시장과 같은 구조입니다. 당시 여러 도시가 쓰던 이른바 '보스턴 방식'은 1지망을 쓴 학생부터 자리를 확정했습니다. 인기 학교를 1지망으로 썼다가 떨어지면 2지망 학교도 이미 1지망 학생들로 차 버리니, 부모들은 진짜 원하는 학교 대신 붙을 만한 학교를 1지망에 써야 했습니다. 정보가 많은 가정일수록 이 셈을 잘했습니다.

뉴욕시는 2003년, 고등학교 배정에 학생이 지원하는 수용 유보를 도입했습니다. 옛 제도에서는 해마다 많은 학생이 아무 지망에도 배정되지 못해 행정적으로 학교가 정해졌다고 합니다. 보스턴은 2005년 보스턴 방식을 버리고 같은 방식으로 바꾸었습니다. 6절에서 본 대로 이 방식에서는 학생에게 진짜 순서보다 나은 거짓 목록이 없으니, 교육청은 부모들에게 전략을 짜지 말고 진짜 원하는 순서대로 적으라고 안내할 수 있게 되었습니다. 한국의 고교 배정처럼 추첨을 섞는 제도도 결국 같은 질문, 곧 어떤 규칙이 정직하게 적을 이유를 주는가를 피할 수 없습니다.

보스턴 앞에 놓인 후보는 하나가 아니었고, 둘 사이의 선택은 철학의 물음이었습니다. 압둘카디로글루와 쇤메즈는 2003년 논문에서, 이 절 뒤의 신장 교환에서 다시 나올 '최상위 교환 고리⁠(top trading cycles)⁠'를 학교에 옮긴 방식도 함께 내놓았습니다. 학생이 지원하는 수용 유보의 결과는 안정합니다. 학교 선택의 말로 옮기면 '정당한 시샘'이 없다는 뜻입니다. 내가 더 원한 학교에 나보다 우선순위가 낮은 학생이 들어가 있는 일이 없다는 것으로, 안정성이 공정함의 한 형태가 된 것입니다. 대신 두 학생이 서로의 학교를 더 원하는데도 바꾸지 못한 채 끝나는 일이 생길 수 있습니다. 교환 고리 방식은 그런 맞교환을 허락해, 아무도 나빠지지 않으면서 누군가는 나아질 여지를 남기지 않습니다. 그 대가로, 교환에 끼지 못한 학생이 자기보다 우선순위가 낮은 학생에게 자리를 빼앗기는 일이 생길 수 있습니다.

설계를 도운 경제학자들은 어느 쪽을 고를지 가르는 물음으로 이것을 꼽았습니다. 우리 아이가 우선권을 가진 학교를 당신 아이가 원하고, 당신 아이가 우선권을 가진 학교를 우리 아이가 원한다면, 두 아이가 우선권을 맞바꾸는 것을 누가 문제 삼겠는가? 2005년 교육감의 메모는 형제가 다니는 학교에 주는 우선권처럼 그 학생에게만 붙은 권리는 남과 맞바꿀 것이 아니라고 보았고, 맞바꾸기가 부모들에게 설명하기 어렵다는 점도 들었습니다. 보스턴은 수용 유보를 택했습니다. 우선권이 서로 바꿀 수 있는 몫인지 그 사람에게 붙은 권리인지, 효율과 공정 가운데 무엇을 앞세울지는 정리가 아니라 공동체가 정한 것입니다.

이 제도에는 뜻밖의 부산물도 있었습니다. 인기 학교의 마지막 자리는 동점자 사이의 추첨으로 갈립니다. 추첨에 붙은 학생과 떨어진 학생은 운 말고는 다를 것이 없으니, 두 무리의 이후 성적을 견주면 그 학교의 효과를 무작위 대조 시험⁠(randomized controlled trial)⁠처럼 잴 수 있습니다. 학교를 고른 가정의 특성이라는 교란 변수⁠(confounding variable)⁠를 추첨이 지워 주는 것입니다. 경제학자들은 보스턴과 뉴욕의 추첨 자료로 차터 스쿨(공적 자금으로 운영되지만 운영 방식은 자율적인 미국의 학교) 같은 학교들의 효과를 추정했습니다. 무작위 대조 시험이 왜 교란 변수를 지우는지는 「담배와 폐암」에서 다룹니다.

신장 교환. 신장이 망가진 환자에게 가족이 신장 하나를 떼어 주려 해도, 혈액형이나 조직이 맞지 않으면 이식할 수 없습니다. 맞아야 하는 까닭은 이식의 첫 성공이 보여 줍니다. 1954년 12월 보스턴의 피터 벤트 브리검 병원에서 외과의 조지프 머리가 해낸 첫 신장 이식은 일란성 쌍둥이 형제 사이였습니다. 유전자가 같으니, 몸의 면역계가 남의 장기를 적으로 알고 공격하는 거부 반응이 일어나지 않았습니다. 1962년 머리는 면역을 누르는 약을 써서 숨진 사람의 신장을 남에게 옮기는 데 성공했고, 1990년 노벨 생리의학상을 받았습니다. 그 뒤로 남의 신장을 받을 수 있게 되었지만, 혈액형과 조직이 맞는지는 지금도 이식의 첫 조건입니다. 미국에서는 1984년 장기 이식법이 장기를 사고파는 것을 금지했습니다. 돈을 쓸 수 없는 시장입니다. 그렇다면 맞지 않는 두 쌍이 기증자를 서로 바꾸면 어떨까요? 1쌍의 기증자가 2쌍의 환자에게, 2쌍의 기증자가 1쌍의 환자에게 주는 것입니다. 이 생각은 1986년 미국의 이식 외과의 펠릭스 라파포트가 처음 제안했고, 이런 교환 이식은 1991년 무렵 한국에서 처음 시행된 것으로 알려져 있습니다. 2004년 로스와 쇤메즈, 경제학자 우트쿠 윈버는 이 교환을 많은 쌍 사이의 매칭 문제로 설계하는 방법을 제안했고, 이는 뉴잉글랜드 지역의 신장 교환 프로그램으로 이어졌습니다.

아래 그림의 원 둘레에 놓인 열 개의 점은 서로 맞지 않는 환자–기증자 쌍입니다. 점 안의 글자는 환자의 혈액형, 바깥의 글자는 그 쌍의 기증자의 혈액형입니다(7, 8, 9번은 혈액형은 맞지만 조직 검사에서 맞지 않는 쌍입니다). 회색 선은 한 쌍의 기증자가 다른 쌍의 환자에게 줄 수 있는 관계입니다. O형 기증자는 누구에게나, A형은 A형과 AB형에게, B형은 B형과 AB형에게, AB형은 AB형에게만 줄 수 있습니다. 교환 고리의 크기는 , 대가 없이 기증하는 사람은 입니다.

새 환자들 처음 환자들

고리가 커질수록 이식이 늘지만 한계가 있습니다. 한 고리의 수술은 모두 동시에 해야 합니다. 먼저 이식받은 쌍의 기증자가 마음을 바꾸면 다른 환자는 기증자도 잃고 신장도 받지 못하기 때문입니다. 두 쌍이면 수술실 넷, 세 쌍이면 여섯이 한꺼번에 필요합니다.

수학적으로도 차이가 큽니다. 두 쌍끼리의 교환만 허용하면 이 문제는 이분 그래프가 아닌 일반 그래프의 최대 매칭⁠(maximum matching)⁠이고, 에드먼즈가 1965년 논문 「경로, 나무, 꽃」에서 만든 알고리즘으로 빠르게 풀립니다. 에드먼즈는 이 논문에서 걸음 수가 입력 크기의 다항식인 알고리즘을 '좋은' 알고리즘이라 부르자고 제안했습니다. 그런데 세 쌍짜리 고리를 허용하면, 이식 수를 가장 크게 하는 문제는 NP-난해⁠(NP-hard)⁠로 바뀝니다. NP-난해란 답이 주어지면 맞는지 확인하기는 쉬운 문제들(NP)을 모두 그 문제로 빠르게 바꿔 적을 수 있다는 뜻, 곧 적어도 NP에서 가장 어려운 문제만큼 어렵다는 뜻입니다. 그래서 크기가 커져도 빨리 푸는 방법은 알려져 있지 않습니다. 다행히 실제 규모에서는 정수 계획법⁠(integer programming)⁠, 곧 변수가 정수여야 한다는 조건을 붙인 선형 계획법 같은 방법으로 답을 구할 수 있습니다.

이타적 기증자가 만드는 사슬은 이 한계를 비껴갑니다. 대가 없이 신장을 내놓은 사람에게서 시작해 한 쌍의 환자가 이식받으면, 그 쌍의 기증자가 다음 쌍에게 주는 식으로 이어지고, 마지막 기증자는 대기자 명단의 환자에게 줍니다. 사슬은 동시에 수술하지 않아도 됩니다. 중간에 누가 약속을 어겨도, 신장을 내주고 아무것도 받지 못하는 쌍은 생기지 않기 때문입니다. 2009년 미국 오하이오주 톨레도의 외과의 마이클 리스와 동료들은 이렇게 동시에 하지 않는 사슬로 열 건의 이식을 이어 간 사례를 보고했습니다. 이 생각의 뿌리는 1974년 섀플리와 경제학자 허버트 스카프의 논문에 있습니다. 그들은 저마다 집이 한 채씩 있는 사람들이 더 좋아하는 집을 찾아 서로 바꾸는 문제를 다루면서, '최상위 교환 고리'라는 방법을 게일의 착상으로 소개했습니다. 원하는 집을 가리키는 화살표의 고리를 찾아 한꺼번에 바꾸는 방법입니다.

이 그림은 윤리의 질문도 드러냅니다. 교환은 이식 수를 늘리지만, O형 환자는 O형 기증자에게서만 받을 수 있어서 교환에서도 불리합니다. 이식 수를 가장 크게 하는 답이 여럿일 때 누구를 먼저 챙길지, 오래 기다린 사람과 조직이 잘 맞는 사람 가운데 누구에게 무게를 둘지는 수학이 정해 주지 않습니다. 로스는 2007년 「시장의 제약으로서의 혐오」라는 글에서, 많은 사람이 거래 자체를 꺼리는 영역이 있고 그 감정이 시장이 할 수 있는 일의 경계를 정한다고 썼습니다. 신장을 돈으로 사고팔게 하자는 주장 앞에서 교환은 하나의 대안입니다. 돈 없이도 시장처럼 짝을 찾아 주니까요.

안정된 배분의 이론과 시장 설계⁠(market design)⁠의 실천에 대하여.— 스웨덴 왕립과학원, 2012년 노벨 경제학상 수상 이유

2012년 10월 노벨 경제학상은 로스와 섀플리에게 돌아갔습니다. 여든아홉의 섀플리는 스스로를 경제학자가 아니라 수학자라고 여겼다고 전합니다. 게일은 2008년에 세상을 떠나 상을 함께 받지 못했습니다. 1975년 칸토로비치와 네덜란드 출신의 미국 경제학자 찰링 쿠프만스가 자원 배분의 이론으로 이 상을 받은 지 37년 만에, 부다페스트의 매칭에서 시작된 줄기가 다시 스톡홀름에 닿은 셈입니다.

위: 1840년부터 오늘까지. 수학 줄(파랑)이 쾨니히스베르크의 야코비와 20세기 초 부다페스트에서 1950년대 미국의 연구소와 대학(RAND, 브린마, 워싱턴)으로 옮겨 가고, 역사 줄(분홍)에서는 냉전의 철도 보고서가 1990년대 이후 학교와 병원의 제도로 바뀌는 것을 보세요. 아래: 생각이 오간 길. 분홍 선은 해리스–로스 보고서가 분석한 철도망의 방향, 주황 선은 번역과 수상, 노란 선은 사람의 이동, 파랑과 보라 선은 정리가 건너간 길입니다.

8 · 이어지는 길짝짓기가 닿는 곳

누구를 누구와 잇는 문제는 수학의 여러 갈래와 만납니다.

• 세기로: 완전 매칭의 수는 '퍼머넌트⁠(permanent)⁠'로 셉니다. 퍼머넌트는 행렬식의 공식에서 항마다 붙는 부호(+ 또는 −)를 모두 +로 바꾼 것입니다. 행렬의 행렬식은 가우스 소거법⁠(Gaussian elimination)⁠으로 빨리 계산되지만, 1979년 영국의 컴퓨터 과학자 레슬리 밸리언트는 퍼머넌트를 계산하는 일이 NP-완전⁠(NP-complete)⁠ 문제들보다도 어렵다고 여겨지는 부류(#P-완전)에 속한다는 것을 보였습니다. 짝이 있는지 묻기는 쉬운데 몇 개인지 세기는 어려운 것입니다. 퍼머넌트의 공식에서 곱셈을 덧셈으로, 덧셈을 '더 작은 쪽 고르기'로 바꾸어 계산하면 퍼머넌트는 3절의 배정 문제, 곧 행과 열을 하나씩 골라 합을 가장 작게 하는 문제가 됩니다. 연산의 뜻만 바꾸는 이런 계산은 「같은 계산, 다른 덧셈」 8절의 열대 기하⁠(geometry)⁠로 이어집니다. 한편 1961년 네덜란드의 물리학자 피터르 카스텔레인은 평면 위의 그래프에서는 완전 매칭을 행렬식 비슷한 계산으로 셀 수 있음을 보여, 바둑판을 도미노로 덮는 방법의 수를 구했습니다. 목록을 만들지 않고 세는 여러 요령은 「세지 않고 세기」에 있습니다.
• 제비뽑기로: 모임에서 선물 받을 사람을 제비로 뽑을 때 아무도 자기 이름을 뽑지 않는 경우는 자기 자신과는 이어지지 않는 완전 매칭, 곧 교란순열⁠(derangement)⁠입니다. 사람이 많으면 그 확률은 $1/e \approx 0.37$에 가까워지고, 포함배제 원리⁠(inclusion–exclusion principle)⁠로 셉니다(「세지 않고 세기」 7절).
• 그래프로: 모든 점을 가장 싸게 잇는 최소 신장 트리⁠(minimum spanning tree)⁠는 욕심쟁이로 풀리고, 가장 큰 매칭은 증가 경로가 필요합니다. 유한하지만 엄청나게 많은 후보 가운데 가장 좋은 것을 찾는 문제들을 다루는 분야를 조합 최적화라 하고, 비슷해 보이는 문제의 어려움이 왜 다른지를 따지는 것도 그 분야의 일입니다. 쾨니히스베르크에서 시작한 점과 선의 이야기는 「일곱 다리의 도시」에 있습니다.
• 연속으로: 흙더미를 옮기는 몽주의 문제와 칸토로비치의 수송 문제는 배정 문제를 연속으로 넓힌 것입니다. 사람과 일이 흙 알갱이와 구덩이가 되고, 가격은 쌍대 문제⁠(dual problem)⁠의 해, 곧 제약마다 붙는 라그랑주 승수⁠(Lagrange multiplier)⁠가 됩니다(최적 수송, 「까마귀와 택시」).
• 질서로: 부다페스트의 조합론 전통은 에르되시 팔의 램지 이론⁠(Ramsey theory)⁠으로 이어졌습니다. 충분히 큰 구조에는 반드시 질서가 숨어 있다는 이야기는 「완전한 무질서는 없다」에서 이어집니다.
• 게임으로: 2절의 '매칭 = 덮개', 3절의 '배정 = 가격', 4절의 '흐름 = 절단'은 모두 선형 계획법의 쌍대성이고, 이것은 두 사람이 동시에 두는 게임의 최소최대 정리와 같은 내용입니다. 게일과 쿤, 섀플리가 두 이야기 모두에 이름을 남긴 것은 우연이 아닙니다. 1950년 무렵 RAND와 프린스턴에서 게임 이론과 선형 계획, 짝짓기가 같은 사람들 사이에서 자랐습니다. 그 무렵 나온 내시 균형⁠(Nash equilibrium)⁠과 죄수의 딜레마⁠(prisoner's dilemma)⁠ 이야기는 「이기는 쪽이 존재한다」에 있습니다.
• 계산의 경계로: 매칭은 다항 시간⁠(polynomial time)⁠에 풀리는 문제의 본보기이고, 세 쌍 고리의 신장 교환은 NP-난해입니다. 그 경계를 둘러싼 큰 물음은 「기계가 풀 수 없는 문제」와 「줄 세우기의 한계」에 있습니다.