10. 매칭 알고리즘 (Matching Algorithm)

매칭^Matching이란, 어떤 그래프 $G=\{V, E\}$의 부 그래프 중, 모든 노드의 차수가 1인 그래프이다.
우리나라에서는 부합이라고 부르기도 한다.

예를들어, 위 그래프에서 $1, 4, 5, 2$를 뽑아내어 만든 부 그래프는 크기 2인 매칭이다.

그러나, $1,2, 4, 5,6$은 $1$이 2의 차수를 가지므로 매칭이 아니다.

$G$가 $n$개의 노드를 가질 때, $n/2$의 크기의 매칭이 존재한다면 모든 노드가 매칭에 관여한 것이다. 이런 경우를 완벽 매칭^{perfect matching}이라 한다.

매칭의 가중치

그래프의 간선에 가중치가 부여될 수 있다. 이때, 매칭의 가중치는 매칭에 포함된 간선들의 가중치의 합이다.

위 그래프에서, $m_1 = (1,3), (2,4)$ 혹은 $m_2 = (1,4), (2,3)$의 두 가지 매칭이 가능함이 보일 것이다.

이때, $m_1$의 가중치는 $10$, $m_2$의 가중치는 $5$로, $m_2$의 가중치가 더 낮다.

선호를 반영한 매칭

매칭에 선호도가 반영되는 경우가 있다. 좋은 예시가 소개팅이나 결혼 중매다.
다음 그래프를 보자.

2대2 소개팅을 가정해보자. 왼쪽 두 노드는 남자, 오른쪽 두 노드는 여자를 의미하고, 간선의 숫자는 우선순위이다.
즉, 남자 1호는 여자 1호를 제일 좋아하고, 여자 2호는 2순위이다.

불륜 커플의 등장

남자 1호와 여자 1호, 남자 2호와 여자 2호를 맺어주는 것이 합당해보인다. 이 방법을 이용하면 커플마다 적어도 1명은 만족스런 연애를 할 수 있다.

그러나 이 방법에는 문제가 하나 있는데, 바로 불륜 커플의 등장이다.

남자 2호와 여자 1호는 본인의 짝보다 다른 이성을 더 좋아한다. 심지어 서로 그렇다.

남자 2호가 먼저 바람이 났다고 해보자. 여자 2호가 질린 남자 2호는 여자 1호에게 가서 구애했다. 여자 1호는 남자 1호가 있었지만, 원래부터 남자 2호가 더 좋았으니 망설임없이 바람을 필 것이다!

이러한 불륜 커플(서로가 본인의 짝보다 서로를 선호하는 커플)이 있는 매칭은 안정적이지 못하다.

안정적인 매칭

남자 $1,2,3,4,5$와, 여자 $A,B,C,D,E$가 각각 다음 선호도 순위를 가진다고 보고, 안정적인 매칭을 찾아보자.

남자	선호 순위	여자	선호 순위
$1$	$C,B,E,A,D$	$A$	$3,5,2,1,4$
$2$	$A,B,E,C,D$	$B$	$5,2,1,4,3$
$3$	$D,C,B,A,E$	$C$	$4,3,5,1,2$
$4$	$A,C,D,B,E$	$D$	$1,2,3,4,5$
$5$	$A,B,D,E,C$	$E$	$2,3,4,1,5$

탐욕법^{Greedy Algorithm}: 숫자가 낮은 남자에게 맞춰주기.

남자 1호부터 5호까지, 순서대로 나와 짝을 고르는 방법을 시험해보자.

$$(1, C), (2, A), (3, D), (4, B), (5, E)$$

남자 1번부터 3번은 각자 본인이 가장 선호하는 짝을 만나 행복하다. 그들은 바람을 피지 않을 것이다. 그런데 4번과 5번은, 각자 4순위로 좋아하는 짝을 만나고 말았다. 이제 4번과 5번은 바람필 마음이 있는 여성을 찾아내고자 할 것이다.

여자들은 또 어떨까? 위 방법에 여자들의 의견은 전혀 반영되지 않았다. 여자들은 강제로 맺어진 짝보다 자신이 더욱 선호했던 짝을 찾을 것이다.

4번은 본인이 $B$보다 선호하는 $A,C,D$양에게 가서 구애할 것이다. $A$양은 4번보단 1번이 낫다고 생각하니 받아주지 않겠지만, $C$양은 본인의 4순위인 1번보다 1순위인 4번이 고백하면 바로 받아줄 것이다.

한편, 5번도 여자 $A$와 바람필 수 있다.

불륜 커플이 2 커플이나 존재하는 것이다!

전통적인 결혼 알고리즘^{Traditional Marriage Algorithm}

TMA는 전통적인 결혼 알고리즘의 약자로, 말 그대로 남성이 여성을 찾아가 구애하면 여성이 이를 받아주거나 거절하는 과정으로 이루어진다.

1. 아침: 매일 아침, 남성은 본인의 리스트에서 가장 좋아하는 여성에게 방문한다.
2. 낮: 여성은 본인을 찾아온 남성들 중, 본인이 가장 좋아하는 남성에게 내일 다시 오라고 말하고, 나머지에겐 다시는 찾아오지 말라고 한다.
3. 밤: 차인 남성들은 눈물을 머금고 리스트에서 여성의 이름을 지우고, 다음날 다른 여자를 찾아간다.

백문이 불여일견, 이 방법을 실행해보자.

첫째날

각 여성의 집에는 다음과 같은 남자들이 방문한다.

• $A$: $2,4,5$
• $B$: 😭
• $C$: $1$
• $D$: $3$
• $E$: 😭

여성 $A$는 본인을 찾아온 남성 중 가장 좋아하는 5번에게만 내일 다시 와달라 부탁하고, 2번과 4번은 다시는 찾아오지 말라고 차버릴 것이다.

둘째날

$A,C,D$는 이제 본인을 다시 찾아온 남자와, 다른 여자에게 차이고 온 남자들을 맞이한다.

• $A$: $5$
• $B$: $2$
• $C$: $1, 4$
• $D$: $3$
• $E$: 😭

$C$는 어제는 1번밖에 선택지가 없었다. 그런데 이게 왠일인가, 본인이 가장 좋아하는 4번이 찾아왔다!
이제 $C$는 1번을 차고 $4$번에게 다음날 다시 와달라는 부탁을 할 것이다.

셋째날 ~

이제 1번은, $C$에게 차인채 다른 여성을 찾아 방황한다. 다음날 $B$에게 가보았지만 $B$는 이미 2가 마음에 들었고, 다음날 $E$에게 가자 비로소 마을의 모든 남녀가 짝을 찾았다.

매칭 결과

$A$	$B$	$C$	$D$	$E$
5	2	4	3	1

TMA의 좋은 점은 불륜 커플이 발생하지 않는 것이다.

예를들어, 남자 1호가 바람을 피우고 싶어 여자 $E$보다 마음에 드는 여자 $B,C$를 찾아갔다고 생각해보자.

여자 $B$는 1호보다 현재 배우자인 남자 2호가 마음에 들고, 여자 $C$도 남자 4호를 좋아한다. 이런 것이 모든 경우에 성립한다.