Bipartite Matching | SISOBUS PS BLOG

Description Bipartite Matching를 알기 위해서는 Bipartite Graph를 먼저 알아야 한다. Bipartite Graph란 이분 그래프로써 그래프에 있는 모든 정점들을 두 그룹으로 나누었을 때, 모든 간선이 서로를 이어주기만 하는 분할이 존재하는 그래프를 말한다. 모든 이분 그래프의 간선의 가 1로 주어졌을 때, 두 그룹의 최대 매칭 수를 구하는 문제가 Bipartite Matcing…