이분 그래프 & 최대 이분 매칭 (Bipartite Graph & Maximum Bipartite Matching)

1. 이분 그래프(Bipartite Graph)란

Example of a bipartite graph without cycles

• "In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets Uand V such that every edge connects a vertex in U to one in V"
• 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프 (그림 상으로 파란색, 초록색으로 인접 노드가 분할이 가능하다)
• 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 의미

위의 세가지 모두 이분 그래프를 설명한다. 쉽게 말해 이웃한 정점끼리는 같은 집합에 속하지 않으면서, 전체 정점을 두 집합으로 나눌 수 있어야 하는 것이다. 

 

Example of a bipartite graph with cycles

참고로, 위의 경우는 사이클이 존재하는 이분 그래프의 예시이다.

 

그렇다면, 그래프가 이분 그래프인지 아닌지를 판단하는 것이 왜 중요한 문제일까?

---

이분 그래프에 적용가능한 대표적인 알고리즘으로 최대 이분매칭(Maximum Bipatite Matching) 이 있다.

2. 최대 이분매칭(Maximum Bipartite Matching)이란

아래의 예시를 보자. 구직자와 직원을 뽑는 회사가 있고 구직자 별로 선호하는 회사 조사하면 왼쪽과 같은 그림이 만들어 진다. 위에서 공부한 이분 그래프 형태로 나타낼 수 있음을 발견했다.

 

이때 고용노동부 입장에선(?) 구직자가 최대한 취업을 하는 방향으로 매칭시키고 싶을 것이다. 

- B회사의 경우 1번 구직자만 선호한다면, C회사는 4번 구직자가 취업할 수 있게 1번 구직자가 양보하는 것이 낫다.

- A회사의 경우 3번 구직자만 선호한다면, D회사는 5번 구직자가 취업할 수 있게 3번 구직자가 양보하는 것이 낫다.

 

따라서, 고용노동부는 이미 알려져 있는 이분 매칭 알고리즘을 적용해서 빠르게 최적 매칭 경우를 계산할 수 있다. 

2.1 최대 이분 매칭 알고리즘의 원리

이분 매칭 알고리즘의 원리는 아래 [4] 링크로 대신한다.

쉽게 표현하면 '굴러온 돌이 박힌 돌을 뺀다'는 것이다

 

조금 쉬운 상황을 만들어 보자.

(1,2,3) 은 구직자, (A, B, C)는 회사, 그리고 구직자 각자가 선호하는 회사는 검은 화살표로 나타내었다.

오른쪽 빨간색으로 매칭되는 것이 취업률을 높이는 매칭일 것이다.

코드로 표현하면 다음과 같다. 

#include <iostream>
#include <vector>
using namespace std;

#define NUM_SEEKER  100 //최대 구직자 수
#define NUM_COMPANY 100 //최대 회사 수 

int num_S, num_C;
bool adjM[NUM_SEEKER][NUM_COMPANY]; //인접 행렬로 표현한 (이분)그래프
vector<bool> visited;
vector<int> SEEKER, COMPANY; //각 정점에 매칭된 상대의 정점 번호 지정

bool dfs(int s)
{
	if (visited[s])
		return false;

	visited[s] = true;

	for (int i = 0; i < num_C; i++) //회사를 확인하여
	{
		if (adjM[s][i]) //구직자가 선호하는 회사라면
		{
			//만약에 매칭되어 있지 않다면 구직자와 회사를 매칭.
			//만약에 매칭되어 있다면, 기존에 매칭된 구직자를 종용(?) 한다.
			if (COMPANY[i] == -1 || dfs(COMPANY[i])){
				SEEKER[s] = i;
				COMPANY[i] = s;
				return true;
			}
		}
	}
	return false;
}

int bipartiteMatch()
{
	//초기화는 아무 정점과도 매칭안된 것을 의미하는 -1. 
	SEEKER = vector<int>(num_S, -1);
	COMPANY = vector<int>(num_C, -1);

	int size = 0;
	for (int start = 0; start < num_S; start++) //구직자 입장에서 출발
	{
		visited = vector<bool>(num_S, false);

		if (dfs(start))
			size++;
	}
	return size;
}

int main()
{
	num_S = 3; // 구직자 수
	num_C = 3; // 회사 수

	// A의 정점i와 B의 정점 j가 연결되어 있으면 1로 표시
	adjM[0][0] = 1; 
	adjM[0][1] = 1;
	adjM[0][2] = 1;
	   
	adjM[1][0] = 1;
	   
	adjM[2][1] = 1;

	cout << bipartiteMatch() << endl;

	return 0;
}

 

코드를 따라가 보면 알겠지만, 결코 쉽지 않다.

 

함께 풀어볼 문제

1707. 이분 그래프

1587. 이분 매칭

2188. 축사배정

11375. 열혈강호

 

[Reference]

[1] https://en.wikipedia.org/wiki/Bipartite_graph

[2] https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[3] https://www.geeksforgeeks.org/maximum-bipartite-matching/

[4] https://www.crocus.co.kr/499