Bipartite Graph
Bipartite Graph(이분 그래프)란 그래프의 전체 노드를 독립적인 2개의 그룹으로 나누는 그래프를 의미한다. 여기서 두 그룹 내에는 edge가 존재하지 않고, 상대 그룹의 node로 이어지는 edge만 존재한다. 거꾸로 말해 그러한 규칙을 갖도록 graph를 구분한 것을 bipartite graph라고 한다.
즉 아래와 같은 그래프를
아래와 같이 만들면 Bipartite graph라 한다. 여기서 빨간색 노드와 파란색 노드 사이에는 edge가 존재하지 않고, 오로지 빨간색 노드와 파란색 노드를 잇는 edge만 존재한다.
직관적으로 보기에도 위의 그래프에 비해 문제가 훨씬 간단해졌다는 것을 알 수 있다. 이분 그래프는 길이가 홀수인 cycle이 존재하지 않으며 모든 cycle은 짝수 길이를 갖는다는 특징이 있다.
만일 같은 규칙으로 그래프의 노드를 3개 이상의 그룹으로 구분할 수 있으면 k-분 graph가 된다.
Bipartite Matching
Bipartite Matching은 Bipartite Graph에서 두 그룹 사이의 최적(또는 최대)의 매칭을 찾는 문제이다. 이를 위해 각 매칭 쌍의 비용을 최소화(또는 이득을 최대화) 하는 방식으로 매칭이 이루어진다.
Bipartite Matching은 매칭 쌍을 최적화하는 문제를 말하며 특정 알고리즘을 의미하지는 않는다. 일반적으로는 비용 행렬을 이용하는 Hungarian Algorithm을 주로 사용한다. 이것은 의 시간 복잡도를 갖는다.
