-
라틴 직사각형과 홀의 결혼 정리
라틴 방진과 스도쿠 라틴 방진 (Latin Square)은 서로 다른 $n$가지 기호로 구성되며, 각 행과 열에 $n$가지 기호가 모두 한 번씩 등장하게 만든 $n\times n$ 행렬입니다. 편의를 위해 $n$가지 기호 대신 $1$부터 $n$까지의 수 배열이라고 생각합시다. 라틴 방진을 만드는 방법은 여러 가지가 있는데, 가장 간단하게 생각할 수 있는 방법은 다음과 같습니다. 첫 번째 행에 $1$부터 $n$까지의 수를 순서대로 적는다. $k$번째 행에는 $k-1$번째 행을 왼쪽으로 한 칸 회전한 배열을 적는다. $(2 ≤ k ≤ n)$ 왼쪽으로 한...
-
최대 이분 매칭에 관한 몇 가지 정리
이분 그래프(Bipartite Graph)에서의 최대 매칭(Maximum Matching)은 최대 유량(Maximum Flow)과 같습니다. 이 글에서는 위와 같이 최대 유량과 최대 이분 매칭에 관한 기본적인 문제를 해결 할 수 있는 분들을 위해 최대 이분 매칭에 관한 대표적인 정리를 예제와 함께 다룹니다. 구성은 아래와 같습니다. Minimum Vertex Cover - BOJ 1867 돌멩이 제거 Maximum Independent Set - BOJ 11014 컨닝 2 Minimum Path Cover - BOJ 1671 상어의 저녁식사 Maximum Anti-Chain - BOJ 13441 마법의 나무 Minimum Vertex Cover Vertex...