홀의 결혼 정리 (Hall's Marriage Theorem)

그래프 이론 정리

arnold518 2021. 2. 15. 15:00

이분그래프 $G=(L+R, E)$에서, $L$의 부분집합 $S$에 대해 이와 연결된 $R$의 부분집합을 $N(S)$라 하자.

이 이분그래프에서 L의 모든 정점이 참여하는 매칭이 존재할 필요충분조건은 모든 $S$에 대하여 $|S| \leq |N(S)|$ 가 성립하는 것이다.