0. 이분 그래프란 ? 이분 그래프는 정점을 두 그룹으로 나눴을 때 그룹 내의 각 정점간 간선이 하나도 없도록 나눠진 그래프를 의미한다. 그룹간의 간선은 존재할 수 있다. 1. 이분 매칭이란 ? 이분 매칭은 이분 그래프 ( biperate graph ) 에서 양쪽 그룹에 속하는 정점끼리 1대1로 매칭시키는 알고리즘이다. 이 때, 매칭 수가 해당 그래프에서 최대가 될 경우, 최대 매칭 ( max matching )이라고 한다.