쾨니그 데네시(Dénes Kőnig)

쾨니그 데네시(헝가리식으로 성을 앞에 씁니다)는 1884년 부다페스트에서 태어났습니다. 아버지 쾨니그 줄러는 헝가리 수학을 이끌던 사람이었는데, 1904년 하이델베르크 국제 수학자 대회에서 실수⁠(real number)⁠ 전체를 줄 세울 수 없다는 '증명'을 발표했다가 며칠 만에 체르멜로를 비롯한 사람들에게 오류를 지적받은 일로도 알려져 있습니다(연속체 가설⁠, continuum hypothesis⁠). 1867년 오스트리아와의 타협으로 반쯤 독립⁠(independence)⁠한 헝가리의 수도는 빠르게 커지고 있었고, 1894년 시작된 중고등학생 수학 경시대회와 수학 잡지가 재능 있는 아이들을 일찍 찾아냈습니다(부다페스트의 수학자들). 데네시는 1902년 열여덟 살에 수학 놀이 문제를 모은 책 『수학의 즐거움』을 펴냈습니다. 그가 평생 매달린 그래프, 곧 점과 선으로 이루어진 도형도 그 무렵에는 쾨니히스베르크의 다리 건너기, 해밀턴의 정십이면체 여행 놀이, 지도 칠하기 같은 놀이 문제의 모음에 가까웠습니다.

나이 세 ·

그는 부다페스트와 괴팅겐에서 공부했습니다. 괴팅겐에서 민코프스키가 강의 중에 4색 문제를 직접 풀어 보겠다고 나섰다가 실패한 일이 그의 관심을 그래프로 이끌었다고 전합니다. 1907년 박사 학위를 받은 그는 부다페스트 공과대학에서 1944년까지 가르쳤습니다. 흩어져 있던 그래프의 결과들, 곧 오일러의 한붓그리기, 키르히호프가 전기 회로를 풀며 쓴 나무, 케일리가 화학 분자를 세며 센 나무의 개수 같은 것들이 사실은 한 분야라는 것을 그는 일찍 알아보았습니다. 1906년에는 칸토어의 집합론⁠(set theory)⁠에서 나온 칸토어–베른슈타인 정리⁠(Cantor–Bernstein theorem)⁠, 곧 두 집합⁠(set)⁠이 서로의 일부와 일대일 대응⁠(one-to-one correspondence)⁠하면 두 집합 전체도 일대일 대응한다는 정리에, 두 집합의 원소⁠(element)⁠를 화살표로 이어 생기는 사슬들을 따라가는 그래프식 증명을 주었습니다(기수⁠(cardinal number)⁠).

그의 첫 큰 정리는 1914년 파리에서 발표되어 1916년 『수학 연보』에 실렸습니다. 점들이 두 무리로 나뉘고 선이 언제나 서로 다른 무리의 점을 잇는 그래프를 이분 그래프라 합니다. 한쪽은 교사, 다른 쪽은 학급이고, 선 하나는 그 교사가 그 학급에서 하는 수업 한 시간이라고 생각하면 됩니다. 모든 교사와 모든 학급이 똑같이 $k$시간씩 수업을 한다고 합시다(모든 점의 차수가 $k$). 쾨니그는 이런 그래프의 선을 $k$가지 색으로 칠해, 한 점에 모인 선들이 모두 다른 색이 되게 할 수 있음을 증명했습니다. 색을 교시로 읽으면, $k$교시 안에 어떤 교사도 어떤 학급도 겹치지 않는 시간표가 반드시 있다는 뜻입니다. 한 가지 색의 선들만 모으면 모든 점을 빠짐없이 짝짓는 완전 매칭⁠(perfect matching)⁠이 되니, 이런 그래프에는 완전 매칭이 있다는 것도 함께 나옵니다. 같은 논문에서 그는 차수가 고르지 않아도 가장 큰 차수만큼의 색이면 충분하다는 데까지 이 결과를 넓혔습니다.

논문 제목에는 '행렬식⁠(determinant)⁠ 이론과 집합론에의 응용'이 붙어 있었습니다. 음이 아닌 수로 채운 정사각 행렬⁠(matrix)⁠에서 모든 행과 모든 열의 합이 같은 양수라고 합시다. 행을 한쪽, 열을 다른 쪽 점으로 두고 0이 아닌 칸마다 선을 그으면 이분 그래프가 됩니다. 그러면 그의 정리에서, 각 행과 각 열에서 하나씩 0이 아닌 칸을 고를 수 있다는 것이 나옵니다. 행렬식을 전개할 때 나오는 항, 곧 행마다 열을 하나씩 겹치지 않게 고르는 순열⁠(permutation)⁠ 가운데 0이 아닌 것이 반드시 있다는 뜻입니다. 같은 무렵 이 문제를 행렬의 언어로 다루던 베를린의 게오르크 프로베니우스는 1917년 논문에서 그래프를 쓰는 방법이 행렬식 이론에 별 쓸모가 없다고 깎아내렸다고 전합니다. 오늘날 이 결과는 두 사람의 이름을 함께 붙여 프로베니우스–쾨니그 정리라 부릅니다.

1927년에는 무한에 관한 짧고 강력한 보조정리를 발표했습니다. 뿌리에서 시작해 가지가 갈라지는 나무가 있는데, 점은 무한히 많지만 각 점에서 갈라지는 가지는 유한 개라고 합시다. 그러면 뿌리에서 출발해 끝없이 내려가는 길이 반드시 하나 있습니다. 증명은 비둘기집 원리⁠(pigeonhole principle)⁠ 하나입니다. 뿌리 아래의 무한히 많은 점이 유한 개의 가지로 나뉘니, 적어도 한 가지 아래에는 무한히 많은 점이 있습니다. 그 가지로 내려가 같은 논리를 되풀이하면 끝나지 않는 길이 나옵니다. 가족으로 말하면, 후손이 무한히 많고 사람마다 자녀가 유한 명인 집안에는 대대로 끊기지 않는 한 줄기가 있다는 것입니다. 가지가 무한히 갈라지면 이 결론은 무너집니다. 뿌리에서 길이가 1, 2, 3, …인 길이 하나씩 뻗은 나무는 점이 무한히 많지만 끝없는 길은 없습니다. 이 쾨니그 보조정리⁠(Kőnig's lemma)⁠는 '유한한 부분마다 되면 전체도 된다'는 논증의 표준 도구가 되었습니다. 예를 들어 점이 셀 수 있는 개수만큼 있는 무한 그래프가 $k$가지 색으로 칠해지는지는, 그 유한한 부분 그래프들이 모두 칠해지는지로 판정됩니다. 점이 셀 수 없이 많은 경우까지는 1951년 더브라윈과 에르되시가 넓혔습니다(무한을 다루는 법).

1931년 그는 가장 유명한 정리를 발표했습니다. 이분 그래프에서 끝점을 공유하지 않는 선을 가장 많이 고른 수(최대 매칭⁠(maximum matching)⁠, $\nu$)와, 모든 선의 적어도 한쪽 끝을 덮는 가장 적은 점의 수(최소 덮개⁠(minimum vertex cover)⁠, $\tau$)가 같다는 것입니다(위의 식). 한쪽 부등식은 어느 그래프에서나 쉽습니다. 매칭의 선들은 끝점을 공유하지 않으니 선마다 서로 다른 점이 하나씩 있어야 덮을 수 있고, 따라서 매칭 ≤ 덮개입니다. 쾨니그는 이분 그래프에서는 이것이 반드시 등식이 된다는 것을 보였습니다. 이 등식은 실용적으로도 뜻이 있습니다. 매칭을 하나 찾고 같은 크기의 덮개를 하나 찾으면, 그 매칭이 가장 크다는 증명서가 됩니다. 같은 해 공과대학의 동료 에게르바리 예뇌는 이 정리를 수가 적힌 행렬로 넓혔습니다. 1935년 케임브리지의 필립 홀이 따로 증명한 홀의 정리⁠(Hall's theorem)⁠, 그 뒤 미국에서 나온 선형 계획법⁠(linear programming)⁠의 쌍대 정리(1940년대 말)와 최대 흐름 최소 절단 정리(1956)가 모두 같은 가족이며, 최대화 문제와 최소화 문제가 같은 답에서 만나는 쌍대성⁠(duality)⁠의 가장 이른 예 가운데 하나입니다.

1936년 그는 라이프치히에서 『유한 및 무한 그래프의 이론』을 펴냈습니다. 그래프만을 다룬 세계 최초의 교과서였습니다. 흩어진 결과들을 한 체계로 정리하고 용어를 가다듬었으며, 제목에서 보듯 무한 그래프를 처음부터 함께 다루었습니다. 이 책으로 그래프 이론은 놀이 문제의 모음이 아니라 수학의 한 분야가 되었습니다. 그의 제자 갈라이 티보르는 에르되시의 가까운 동료로 헝가리 조합론⁠(combinatorics)⁠의 중심 인물이 되었고, 에르되시, 투란 팔 같은 다음 세대의 부다페스트 조합론은 그가 닦은 바탕 위에서 자랐습니다. 1953년 미국의 해럴드 쿤은 이 책에서 에게르바리의 헝가리어 논문을 알게 되어, 사전을 들고 스스로 번역한 끝에 배정 문제⁠(assignment problem)⁠를 푸는 방법을 만들고 두 헝가리 수학자를 기려 '헝가리안 방법⁠(Hungarian method)⁠'이라 불렀습니다.

그의 마지막 몇 해는 헝가리 유대인들의 비극과 겹쳤습니다. 1938년부터 헝가리는 유대인의 직업과 교육을 제한하는 법을 잇달아 만들었고, 그의 집안은 유대계였습니다. 그는 헝가리 수학 물리학회에서 일하며 박해받는 동료 수학자들을 도우려 애썼다고 전합니다. 1944년 3월 독일군이 헝가리를 점령하자 수십만 명의 유대인이 수용소로 끌려갔고, 10월 15일 극우 화살십자당이 권력을 잡자 부다페스트에 남은 유대인들도 학살과 강제 노동에 내몰렸습니다. 그 며칠 뒤인 10월 19일, 쾨니그는 박해를 피해 스스로 목숨을 끊었습니다.

그의 정리들은 오늘날 조합 최적화⁠(combinatorial optimization)⁠의 기초⁠(basics)⁠ 문법입니다. 매칭 = 덮개라는 등식은 선형 계획법의 쌍대성이 정수⁠(integer)⁠에서도 그대로 성립하는 특별한 경우로 이해되고, 이분 그래프의 선 칠하기는 1964년 바딤 비징이 모든 그래프로 넓혔습니다(가장 큰 차수만큼, 또는 하나 더 많은 색이면 충분합니다). 쾨니그 보조정리는 논리학에서 '유한에서 무한으로' 건너가는 추론의 원형이 되었고, 컴퓨터 과학에서는 무한히 돌 수 있는 프로그램의 성질을 따지는 데 쓰입니다. 오늘날 학교 시간표 짜기, 병원의 수술실 배정, 신장 교환⁠(kidney exchange)⁠ 같은 짝짓기 문제의 알고리즘⁠(algorithm)⁠은 모두 그의 이분 그래프에서 출발합니다(안정 매칭⁠(stable matching)⁠).

이어지는 곳. 매칭과 덮개의 등식은 홀의 정리와 최대 흐름⁠(maximum flow)⁠ 최소 절단⁠(cut)⁠에서, 행과 열에 가격을 매기는 헝가리안 방법은 선형 계획법과 해럴드 쿤에서 이어집니다. 무한 보조정리는 나무와 무한을 다루는 법에, 그래프 이론 전체의 지도는 그래프에 있습니다. 그가 살았던 도시의 이야기는 부다페스트의 수학자들에서, 쌍대성이라는 큰 흐름은 쌍대성에서 이어집니다.

관계.

• 영향을 받음 헤르만 민코프스키 — 괴팅겐에서 공부하던 시절 민코프스키의 강의에서 4색 문제를 들은 것이 그래프에 관심을 갖게 된 계기였다고 전합니다.
• 영향을 줌 해럴드 쿤 — 쿤은 1953년 그의 교과서에서 에게르바리의 헝가리어 논문을 알게 되어 번역했고, 두 사람의 생각으로 배정 문제를 푸는 방법을 만들어 '헝가리안 방법'이라 불렀습니다.
• 영향을 받음 게오르크 칸토어 — 칸토어의 집합론에서 나온 칸토어–베른슈타인 정리에, 원소들을 사슬로 잇는 그래프식 증명(1906)을 주었습니다.

연표.

• 1902년 수학 놀이 문제를 모은 책 『수학의 즐거움』을 펴내다
• 1907년 부다페스트에서 박사 학위를 받고 공과대학에서 가르치다
• 1914년 파리의 학회에서 이분 그래프의 정리를 발표하다
• 1916년 이분 그래프와 행렬식에 관한 논문을 『수학 연보』에 싣다
• 1927년 무한한 나무에 끝없는 길이 있다는 보조정리를 발표하다
• 1931년 이분 그래프에서 최대 매칭과 최소 덮개가 같다는 정리를 발표하다
• 1935년 부다페스트 공과대학의 정교수가 되다
• 1936년 첫 그래프 이론 교과서 『유한 및 무한 그래프의 이론』을 라이프치히에서 펴내다