-
queuedq's profile image
queuedq
September 18, 2022
Kirchhoff's Theorem (Matrix-Tree Theorem)
이번 글에서는 그래프의 스패닝 트리의 개수를 세는 두 가지 정리, Cayley’s formula와 Kirchhoff’s theorem에 대해 소개합니다. Cayley’s Formula 일반 그래프의 스패닝 트리의 개수를 세어보기에 앞서, 특수한 경우부터 먼저 살펴봅시다. Theorem 1 (Cayley’s Formula). $n$개의 정점으로 이루어진 완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다. 이 정리를 증명하는 방법으로는 여러 가지가 알려져 있으며, 대표적으로 Prüfer sequence와의 일대일 대응 관계를 찾는 증명이 있습니다. 개인적으로 가장 마음에 드는 증명은 다음과 같은 더블 카운팅을 이용한 증명입니다. 책 “하늘책의 증명” (Proofs from...
-
queuedq's profile image
queuedq
May 15, 2022
Probabilistic Method
그래프 이론과 확률. 왠지 어울리지 않을 것 같은 두 개념을 처음으로 엮은 것은 헝가리의 수학자 폴 에르되시 (Paul Erdős)였습니다. 그는 확률을 이용해서 그래프 이론과 조합론 분야의 정리를 증명하는 “확률론적 방법론” (Probabilistic Method)을 창안했습니다. 이번 글에서는 확률론적 방법론이 어떤 방식의 증명 방법인지 몇 가지 정리를 통해 알아봅시다. $ \renewcommand{\Pr}{\mathbf{Pr}} \newcommand{\Ex}{\mathbf{E}} $ Warm-Up: 2-Colorable Hypergraphs 다음을 증명해 봅시다. Problem. 집합 $S$가 있고, $S$의 부분집합 $m$개가 있다. 이 부분집합들은 모두 크기가 $k$ 이상이다. $m<2^{k-1}$일 때, $S$의 원소들을 빨강이나...
-
queuedq's profile image
queuedq
April 17, 2022
Sum over Subsets (SOS) DP
이번 글에서는 다이나믹 프로그래밍으로 Sum over Subsets (SOS) 문제를 푸는 방법을 대해 소개하겠습니다. SOS DP는 Codeforces에서 중상급 난이도의 문제로 종종 출제되는 흥미로운 테크닉이지만, 지금껏 한국어 자료를 찾아보기 어려웠기 때문에 SOS DP를 소개하는 Codeforces 블로그 글의 구성을 참고해서 한국어 소개글을 작성해 보았습니다. 또한 기존 글에서 한발 나아가서 어떤 직관을 통해 SOS DP를 이해할 수 있는지도 소개하려고 합니다. 이 글에서는 다음과 같은 표기를 사용할 것입니다. 비트마스크를 집합처럼 취급합니다. 예를 들어, $1101_{(2)} = 2^0 + 2^2 + 2^3$은...
-
queuedq's profile image
queuedq
March 20, 2022
라틴 직사각형과 홀의 결혼 정리
라틴 방진과 스도쿠 라틴 방진 (Latin Square)은 서로 다른 $n$가지 기호로 구성되며, 각 행과 열에 $n$가지 기호가 모두 한 번씩 등장하게 만든 $n\times n$ 행렬입니다. 편의를 위해 $n$가지 기호 대신 $1$부터 $n$까지의 수 배열이라고 생각합시다. 라틴 방진을 만드는 방법은 여러 가지가 있는데, 가장 간단하게 생각할 수 있는 방법은 다음과 같습니다. 첫 번째 행에 $1$부터 $n$까지의 수를 순서대로 적는다. $k$번째 행에는 $k-1$번째 행을 왼쪽으로 한 칸 회전한 배열을 적는다. $(2 ≤ k ≤ n)$ 왼쪽으로 한...