이분 그래프

그래프에 있는 모든 정점들을 두 그룹으로 나눴을 때, 모든 간선이 두 그룹을 서로 잇기만 하는 분할이 존재하는 그래프입니다. 이는 두 대상의 관계를 표현하는 셈입니다. 예를 들어, 보유한 전자 기기와 충전기 사이에 이 충전기에 충전 가능한가? 라는 관계를 둘 사이를 잇는 간선으로써 표현할 수 있습니다.

이분 매칭

보유한 전자 기기와 충전기들로부터 최대 동시 몇 개의 전자 기기를 충전 가능한가? 라는 문제에 대한 해답입니다.

예시 문제

CCRICKET 문제의 경우, 2개짜리 타일을 최대한 많이 사용하는 것이 목표입니다. 격자판의 각 격자를 정점으로 생각해 봅시다. 이를 체스판과 같이 생각하면, 2개짜리 타일 하나는 인접한 검은 타일과 하얀 타일 하나씩을 덮게 됩니다. 따라서 검은 타일들의 정점과 하얀 타일들의 정점, 그리고 그 둘 사이에 인접 여부를 가지고 이분 그래프를 구성할 수 있습니다. 여기서 이분 매칭을 수행하면 서로 겹치지 않는 최대 타일의 수를 셀 수 있습니다.