폴리매스

대45의 소문제 2, 3번에는 결혼 정리라는 강력한 정리가 풀이에 쓰입니다. 모르시는 분들도 꽤 될 것 같아 결혼 정리에 대한 설명과 몇 가지 예제들을 여기에 적어볼까 합니다.

매칭(matching)

일단, 결혼 정리를 이해하기 위해선 매칭이라는 개념을 이해해야 합니다. 매칭이란, 쉽게 말해서 그래프의 여러 선분들을 V자 형태가 생기지 않도록 뽑는 것입니다.

엄밀하게 말하자면, 매칭이란 인 집합 S 중, V(S)의 임의의 원소의 차수가 1인 그래프를 의미합니다.

그림으로 그려보면 여러개의 선분들이 분리되어 있는 형태로 나타나게 됩니다.

또한, 어떤 점들의 집합 가 존재할 때 어떤 매칭 S가 를 만족하며 A의 임의의 두 원소 x, y 사이 선분이 S내에 존재하지 않을경우, 이러한 매칭을 집합 A를 덮는 매칭이라고 부릅니다. (A 내부 선분 존재 여부에 관한 조건은 확실하지가 않네요... 나중에 찾아볼게요)

또, 를 만족하는 매칭 S를 완전매칭이라고 부릅니다.

결혼 정리(Hall's marriage theorem)

이 정리는 이분그래프 G=(A, B)가 주어져 있을 때 (WLOG ), 집합 A를 덮는 매칭이 존재할 필요충분조건에 대한 정리입니다.

일단, 임의의 집합 에 대하여, 집합 N(S)를 다음과 같이 정의합시다.

S의 어떤 원소 x가 존재하여, x가 y와 연결되어 있다면 , S의 임의의 원소와도 연결되어 있지 않다면 N(S)의 원소가 아닙니다.

(쉽게 말해 N(S)는 집합 S와 연결되어 있는 점의 집합을 의미합니다.)

이때, A를 덮는 매칭이 존재할 필요충분조건은 임의의 집합 에 대해 이라는게 결혼 정리입니다.

이에 대한 증명은 좀 길기 때문에 이건 따로 시간이 나면 다른 글로 증명을 올리도록 하겠습니다.

이해하셨다면 다음 예제들을 풀어보는 것을 추천합니다.

예제 1. V(G)={1, 2, 3, 4, 5, 6}, A={1, 2, 3}, B={4, 5, 6}, E(G)={{1, 4}, {2, 4}, {3, 4}, {3, 5}, {3, 6}}이라는 그래프 G=(A, B)가 주어져 있을 때, A를 덮는 매칭과 B를 덮는 매칭 둘 다 존재하지 않음을 보이시오.

예제 2. 모든 점의 차수가 동일한 이분그래프 G=(A, B)는 완전매칭을 포함함을 보이시오.

예제 3. 이분할 그래프 G=(A, B)가 다음 조건을 만족한다면, G가 완전매칭을 포함함을 증명하시오.

조건: , 각 점의 차수는 m/2 이상이다.

예제 1은 결혼 정리를 이해하셨다면 쉽게 푸셔야 하고 예제 2와 3은 조금 어려울 수 있습니다. 결혼정리에 대한 증명과 예제 2, 3에 대한 풀이는 추후에 올리도록 하겠습니다. 또한, 예제 2와 3은 실제로 많이 쓰이는 보조정리이기도 합니다.

댓글로 이해 안 되는 부분 질문이나 예제 풀이 올려주시면 감사하겠습니다. (예제 풀이는 다른 분들도 풀 수 있게 비댓 부탁드립니다)