이분 매칭

n개의 정점이 있을때, 두개씩 짝지어 주는 방법론.

각각의 연결된 정점은 끝점을 공유하지 않는다. 

아래의 왼쪽 그림처럼 끝점을 공유하면 안되고, 오른쪽의 녹색 라인처럼 2개씩 짝지어져야함.

ex)

1.  아래와 같은 그래프가 있다. 파란 선은 도달 가능함을 의미한다. A부터 시작해서 하나씩 매칭해보자.

A에서 2로 도달 가능하므로 이어준다.

2. B에서 매칭을 시도하는데 B에서도 2로 가는게 가능하다. A에서 2 대신 5와 매칭이 가능하므로

A-5로 다시 매칭을 해주고 B는 2와 이어준다.

이런식으로 매칭을 시켰을때 가장 많은 쌍을 구하는걸 최대 매칭 문제라고 한다.