[6기 강남 조유석] Network Flow - Bipartite Matching

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 지난 포스팅에 이어 다른 형태의 Network Flow 문제 몇 가지를 소개하고 해결하는 방법에 대해 알아보겠습니다.

복수의 source나 sink가 있는 경우

지난 포스팅에서는 1개의 source와 1개의 sink에 대한 Network Flow 문제의 해결법을 설명했습니다. 이 문제와는 조금 다르게 여러 개의 source와 sink가 존재하고, 각각 최대 유출량, 유입량이 결정돼 있는 경우의 문제가 있을 수 있습니다. 이 경우 새로운 별도의 s와 t를 만들고, s부터 각 source로 최대유출량의 용량을 가진 변을 연결하고, 각 sink로부터 t로 최대유입량의 용량을 가진 변을 연결하면 1개의 source, 1개의 sink가 있는 문제로 변형됩니다.

무방향 그래프의 경우

무방향 그래프의 경우 양방향으로 동시에 흘렀을 경우 그것을 없애버려도 같으므로, 최대흐름을 고려하면 양방향으로 동시에 보낼 필요가 없습니다. 따라서 무방향 그래프에서 용량 c의 간선에 대해서, 양방향으로 각각의 용량 c만큼씩 연결한 방향그래프로 변형하는 것으로 같은 결과를 얻을 수 있습니다.

정점에 용량이 있는 경우

그래프의 간선만이 아니라, 정점에도 용량의 제약이 있을 수 있습니다. 이 경우는 각 정점을 2개로 나누는 것으로 해결할 수 있습니다. 정점을 입정점과 출정점으로 나누고 원래의 정점으로 들어가는 변은 입정점에 연결하고, 원래의 정점에서 나가는 변은 출정점에 연결하고, 입정점에서 출정점으로 정점용량의 간선을 연결하는 것으로, 정점에 대한 제약을 변에 대한 제약으로 변환할 수 있습니다.

Bipartite Matching

매칭(matching): 그래프에 대해서 끝점을 공유하지 않는 간선의 집합을 매칭이라고 합니다. 아래 그림(a)는 올바른 매칭 결과, 그림(b)는 올바른 매칭이 아닙니다.

이분 그래프(Bipartite Graph): 아래 그림과 같이 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프를 말합니다.

이분 그래프는 남자와 여자, 사람과 작업 등 현실 세계에서 직관적인 의미를 가지며 이 이분 그래프에서 최대의 매칭을 찾는 문제를 이분 매칭(Bipartite Matching) 이라고 부릅니다.

이분 매칭 문제는 아래와 같이 Network Flow 문제로 풀 수 있습니다.

- 그룹 A의 왼쪽에 source 추가 후 A의 모든 정점으로 간선을 연결

- 그룹 B의 오른쪽에 sink 추가 후 B의 모든 정점으로 간선을 연결

- 모든 간선의 용량은 1

이 그래프의 최대 유량을 구한 뒤 유량이 흐르는 간선들을 모으면 최대 매칭이 됩니다. 이 경우 최대 유량은 O(|V|) 이므로, BFS는 O(|V|) 번 하게 됩니다. 따라서 이 경우 Ford-Fulkerson Algorithm 의 시간 복잡도는 O(|V||E|) 가 됩니다.

이상으로 다양한 형태의 Network Flow 문제에 대해 알아보았습니다.

감사합니다.

Reference

  - ‘프로그래밍 대회에서 배우는 알고리즘 문제해결 전략’ - 구종만 저

  - ‘프로그래밍 콘테스트 챌린징’ - Takuya Akiba, Yoichi Iwata, Masatoshi Kitagawa 저