Bi-Partite Matching

0. 들어가기에 앞서

본 게시글은 복잡한 수학 내용 대신, 개념적으로 가볍게 bi-partite matching이 무엇인지 알아보기 위해 작성한 글입니다.

더욱 자세한 내용을 알고싶다면, 아래의 참고 링크 부분의 링크를 참고 바랍니다.

 

1. 개념

• 모든 경로의 용량이 1이면서, 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프라 함
• 이분 그래프에서 A, B그룹이 있을 때, A에서 각 원소가 B에서 서로 다른 각 원소와 연결 되는 것을 이분 매칭이라 함

 

 

참고 자료

https://www.crocus.co.kr/499