홀의 정리(Hall's theorem)

사람 다섯이 일자리 다섯 개에 지원합니다. 사람마다 받아들일 수 있는 일이 정해져 있고, 한 사람은 일 하나만, 한 일은 한 사람만 맡을 수 있습니다. 사람과 일을 두 줄의 꼭짓점⁠(vertex)⁠으로, '받아들일 수 있다'를 변으로 그리면 변이 두 무리 사이에만 있는 이분 그래프가 됩니다. 서로 겹치지 않는 변들의 모음이 매칭⁠(matching)⁠이고, 모든 사람이 일을 얻는 매칭은 사람에서 일로 가는 단사⁠(injective)⁠ 함수(서로 다른 사람을 서로 다른 일로 보내는 함수⁠(function)⁠)이면서 각자 원하는 일로만 보내는 것입니다.

누구든 사람 몇 명의 무리 S를 골랐을 때 그들이 원하는 일을 모두 모은 집합⁠(set)⁠을 $N(S)$라 합시다. 모두 일을 얻으려면 당연히 $|N(S)| \ge |S|$여야 합니다. 세 사람이 두 일만 원한다면 비둘기집 원리⁠(pigeonhole principle)⁠에 따라 둘이 같은 일을 맡아야 하니까요. 1935년 필립 홀은 이 당연한 조건이 모든 S에 대해 성립하기만 하면 충분하다는 것을 증명했습니다.

보기: . 사람 하나와 일 하나를 차례로 누르면 그 사이의 변이 생기거나 없어집니다. 사람을 A부터 차례로 한 명씩 짝지어 봅니다. 변을 바꾸면 곧바로 끝까지 처리한 결과가 보입니다.

새 사람이 원하는 일이 모두 차 있으면, 그 일을 가진 사람에게 다른 일로 옮겨 갈 수 있는지 묻습니다. 그 사람의 다른 일도 차 있으면 또 그 주인에게 묻고, 이렇게 가다 빈 일에 닿으면 사슬을 따라 모두 한 칸씩 옮깁니다. 짝이 아닌 변과 짝인 변을 번갈아 지나 빈 곳에 닿는 이 길을 증가 경로라 하고, 길 위의 짝과 짝 아닌 변을 맞바꾸면 짝이 꼭 하나 늘어납니다. '사슬' 보기에서 E를 처리할 때 그 모습이 보입니다. 사람마다 증가 경로⁠(augmenting path)⁠를 한 번씩 찾으면 되니 전체 비용은 사람 수와 변 수의 곱 정도입니다(점근 표기법⁠(asymptotic notation)⁠). 반면 홀 조건을 하나하나 확인하려면 사람들의 모든 부분집합⁠(subset)⁠, 곧 멱집합⁠(power set)⁠의 원소⁠(element)⁠ $2^n$개를 봐야 합니다. 지금 매칭의 크기는 이고, 조건을 어기는 무리는

이 알고리즘⁠(algorithm)⁠은 증명도 줍니다. 어떤 사람 u에게 증가 경로가 없으면, u에서 번갈아 가는 길로 닿는 사람들을 S, 그들이 닿는 일을 N(S)라 할 때 N(S)의 일은 모두 S의 다른 사람이 맡고 있어서 $|N(S)| = |S| - 1$입니다. 그러니 홀 조건이 성립하면 증가 경로는 반드시 있고, 사람마다 짝이 하나씩 늘어 결국 모두 일을 얻습니다. '막힘' 보기의 빨간 고리가 이렇게 찾은 무리입니다. 같은 생각을 흐름으로 옮기면 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 됩니다. 1931년 헝가리의 수학자 쾨니그가 증명한 쾨니그의 정리⁠(Kőnig's theorem)⁠도 여기서 나옵니다. 꼭짓점 몇 개를 골라 모든 변이 고른 점 가운데 적어도 하나에 닿게 하는 것을 꼭짓점 덮개⁠(vertex cover)⁠라고 하는데, 이분 그래프⁠(bipartite graph)⁠에서는 가장 큰 매칭의 크기와 가장 작은 꼭짓점 덮개의 크기가 언제나 같다는 정리입니다.

완전 매칭⁠(perfect matching)⁠의 개수를 세는 것은 전혀 다른 이야기입니다. 모든 사람이 일을 얻는 매칭을 완전 매칭이라 합니다. 사람 i가 일 j를 원하면 (i, j) 성분을 1, 아니면 0으로 적은 행렬⁠(matrix)⁠을 만들면, 완전 매칭의 개수는 이 행렬의 퍼머넌트입니다. 퍼머넌트⁠(permanent)⁠는 행렬식⁠(determinant)⁠을 전개한 식에서 모든 항의 부호를 +로 바꾼 것으로, 각 행에서 서로 다른 열의 성분을 하나씩 골라 곱한 값을 모든 고르는 방법에 대해 더합니다. 부호 하나만 다른데 난이도는 딴판입니다. 행렬식은 가우스 소거법⁠(Gaussian elimination)⁠으로 빠르게 계산되지만, 퍼머넌트를 빠르게 계산하는 방법이 있다면 P 대 NP 문제⁠(P versus NP problem)⁠가 P = NP로 풀려 버린다는 것이 증명되어 있습니다(1979년 영국의 컴퓨터 과학자 레슬리 밸리언트). 그래서 퍼머넌트는 어렵다고 믿어집니다. 모두가 자기 번호의 일만 빼고 다 원할 때, 완전 매칭은 아무도 자기 번호의 일을 맡지 않는 배정, 곧 교란순열⁠(derangement)⁠입니다.

이어지는 곳. 짝마다 비용이 있어 비용의 합을 최소로 하는 배정 문제⁠(assignment problem)⁠는 헝가리안 방법⁠(Hungarian method)⁠으로 풉니다. 1955년 미국의 해럴드 쿤이 쾨니그와 에게르바리 같은 헝가리 수학자들의 생각을 바탕으로 만들어서 붙은 이름입니다. 사람과 일 대신 흙더미와 구덩이처럼 연속적으로 퍼진 양을 가장 싸게 옮기는 문제로 넓히면 최적 수송⁠(optimal transport)⁠이 됩니다. 모두가 상대에게 좋아하는 순서를 매길 때 불만 없는 짝을 찾는 문제는 안정 매칭⁠(stable matching)⁠입니다. 홀의 정리는 원래 여러 모임에서 모임마다 서로 다른 대표 한 명씩을 고를 수 있는가라는 물음(서로 다른 대표 고르기)의 답으로 나왔고, 시간표 짜기 같은 조합 문제의 기본 도구입니다. 예를 들어 n×n 표의 각 행과 각 열에 n개 기호가 한 번씩 들어가는 라틴 방진⁠(Latin square)⁠은, 위에서부터 한 행씩 채울 때 홀의 정리 덕분에 언제나 다음 행을 채울 수 있어서 끝까지 완성됩니다.