레이블 그래프의 개수 세기¶
레이블 그래프¶
그래프의 정점 개수를 $n$이라고 합시다. 정점이 $n$개인 레이블 그래프의 개수 $G_n$을 계산해야 합니다(레이블이 있다는 것은 정점에 $1$부터 $n$까지의 번호가 매겨져 있다는 뜻입니다). 그래프의 간선은 무방향으로 간주하며, 루프와 다중 간선은 허용하지 않습니다.
그래프에서 가능한 모든 간선의 집합을 생각해 봅시다. 각 간선 $(i, j)$에 대해 $i < j$라고 가정할 수 있습니다(그래프가 무방향이고 루프가 없기 때문입니다). 따라서 모든 간선 집합의 크기는 $\binom{n}{2}$, 즉 $\frac{n(n-1)}{2}$입니다.
모든 레이블 그래프는 간선에 의해 유일하게 결정되므로, 정점이 $n$개인 레이블 그래프의 개수는 다음과 같습니다:
연결된 레이블 그래프¶
여기서는 그래프가 연결되어 있어야 한다는 제약을 추가로 둡니다.
구하려는 정점 $n$개짜리 연결 그래프의 개수를 $C_n$이라고 표기합시다.
먼저 연결되지 않은 그래프가 몇 개인지 알아보겠습니다. 그러면 연결 그래프의 개수는 $G_n$에서 연결되지 않은 그래프의 개수를 뺀 값이 됩니다. 더 나아가, 연결되지 않은 루트 그래프의 개수를 세겠습니다. 루트 그래프란 정점 하나를 루트로 지정하여 강조한 그래프입니다. 레이블이 붙은 정점 $n$개로 이루어진 그래프에 루트를 정하는 방법은 당연히 $n$가지이므로, 연결되지 않은 그래프의 개수를 얻으려면 마지막에 연결되지 않은 루트 그래프의 개수를 $n$으로 나누어야 합니다.
루트 정점은 크기가 $1, \dots n-1$인 연결 요소 중 하나에 속하게 됩니다. 루트 정점이 정점 $k$개짜리 연결 요소에 속하는 그래프는 $k \binom{n}{k} C_k G_{n-k}$개입니다(연결 요소를 이룰 정점 $k$개를 고르는 방법이 $\binom{n}{k}$가지이고, 이 정점들을 연결하는 방법이 $C_k$가지이며, 루트 정점은 $k$개의 정점 중 어느 것이든 될 수 있고, 나머지 $n-k$개의 정점은 어떤 식으로든 연결되거나 연결되지 않을 수 있으므로 $G_{n-k}$라는 인수가 곱해집니다). 따라서 정점이 $n$개인 연결되지 않은 그래프의 개수는 다음과 같습니다:
그리고 최종적으로 연결 그래프의 개수는 다음과 같습니다:
연결 요소가 $k$개인 레이블 그래프¶
앞 절의 공식을 바탕으로, 정점이 $n$개이고 연결 요소가 $k$개인 레이블 그래프의 개수를 세는 방법을 알아보겠습니다.
이 개수는 동적 계획법으로 계산할 수 있습니다. 각 $i \le n$과 $j \le k$에 대해 $D[i][j]$, 즉 정점이 $i$개이고 연결 요소가 $j$개인 레이블 그래프의 개수를 계산하겠습니다.
이전 값들을 이미 알고 있을 때 다음 원소 $D[n][k]$를 계산하는 방법을 살펴봅시다. 흔히 쓰는 방법대로 마지막 정점(번호 $n$)을 택합니다. 이 정점은 어떤 연결 요소에 속합니다. 이 연결 요소의 크기를 $s$라고 하면, 그러한 정점 집합을 고르는 방법은 $\binom{n-1}{s-1}$가지이고, 이들을 연결하는 방법은 $C_s$가지입니다. 이 연결 요소를 그래프에서 제거하면 $n-s$개의 정점과 $k-1$개의 연결 요소가 남습니다. 따라서 다음과 같은 점화식을 얻습니다: