문제. $n$명의 소년과 $m$명의 소녀가 있다고 합시다. 각 소년과 각 소녀에 대해, 누구와 춤을 추어도 괜찮은지가 알려져 있습니다. 짝을 이룬 두 사람이 서로 함께 춤추기를 원하는 쌍을 가능한 한 많이 만들어야 합니다.
소년과 소녀를 이분 그래프의 정점으로 나타내고, 「함께 춤출 수 있다」는 관계를 그 그래프의 간선으로 삼아 이 문제를 형식화합시다. 앞으로 그래프의 왼쪽 부분을 $L$로, 오른쪽 부분을 $R$로 나타내겠습니다.
매칭 $M$은 그래프에서 서로 인접하지 않는 간선들의 집합을 말합니다(다시 말해, 그래프의 모든 정점에 대해 그 정점에 접하는 $M$의 간선은 최대 하나여야 합니다).
매칭에 속한 인접 간선을 가지는 모든 정점(즉, $M$이 이루는 부분 그래프에서 차수가 정확히 1인 정점)을 이 매칭에 의해 포화된 정점이라고 부르겠습니다.
매칭에 속한 간선의 개수를 매칭의 크기라고 부르겠습니다. 주어진 그래프에서 가능한 모든 매칭 중 크기가 가장 큰 매칭을 최대(maximum) 매칭이라고 부르고, 왼쪽 부분의 모든 정점이 그 매칭에 의해 포화된 매칭을 완전 매칭이라고 부르겠습니다.
매칭은 이분 그래프에서만 찾을 수 있는 것은 아니지만, 일반적인 알고리즘은 구현하기 까다롭고 $O(n^3)$에 동작하므로, 이 장에서는 이분 그래프에만 집중하겠습니다.