Cayley’s Formula
Theorem
완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다.
Proof
$K_n$의 스패닝 트리의 개수를 $T_n$이라고 하자. 이제 더블 카운팅을 이용하여 “방향성을 추가한 간선으로 구성된 스패닝 트리의 개수”를 세볼 것이다. 조금 더 풀어서 설명해보자면 아무것도 없는 그래프에서 방향성이 있는 간선을 하나씩 추가해가면서 스패닝 트리를 구성하는 것이다. 이때 무조건 방향성은 루트 노드에서 멀어지는 방향으로 설정한다. 이는 곧 같은 스패닝 트리라도 방향성이 다르면 다른 스패닝 트리로 취급함을 암시하고 있다.
1번째 방법
일단 방향성이 없는 스패닝 트리를 하나 잡는다. 이후 아무 정점 하나를 루트 노드로 잡고, 각 간선에 차례대로 방향성을 부여해준다. 루트로 잡을 수 있는 노드는 $n$개, 간선에 방향성을 부여해주는 순서는 $(n-1)!$가지이므로 총 $T_nn!$가지이다.
2번째 방법
일단 노드만 존재하는 상태에서 시작한다. 적당한 $k$에 대해 $n-k$개의 간선을 추가했다면 $k$개의 트리로 구성된 forest가 생성된 상태일 것이다. 이후 $k$개의 트리 중 아무 트리를 고르고, 고른 트리에서 또 아무 노드를 골라서 시작점으로 설정한다. 이후 끝점을 다른 $k-1$개의 트리의 노드를 설정하여 연결해준다. 모든 $k(1\leq k\leq n)$에 대해 경우의 수는 $n(k-1)$이므로 모두 곱해주면 $n^{n-1}(n-1)!=n^{n-2}n!$가지의 방법이 존재한다.
1번째 방법과 2번째 방법에 의한 결과가 같아야하므로…! $T_n=n^{n-2}$이다!
Laplacian Matrix
이제 일반적인 그래프로 넘어가기 위해서는 라플라시안 행렬이라는 개념이 필요하다.
$n$개의 노드를 가지는 그래프 $G$에 대해서 $G$의 Laplacian Matrix $L_G$는 다음과 같이 정의되는 $n\times n$ 정사각행렬이다.
\[L_G=D_G-A_G\]이때, $D_G$는 $G$의 차수행렬(Degree Matrix), $A_G$는 $G$의 인접행렬(Adjancency Matrix)이다. 차수행렬은 원소가 각 노드의 차수인 대각행렬을, 인접행렬은 노드가 연결된 경우 1, 아닌 경우 0인 행렬을 말한다. 수식적으로는 다음과 같이 정의된다.
\[\begin{aligned} (D)_{i,j} &= \begin{cases}\deg(v_i) & \text{if $i=j$} \\ 0 & \text{otherwise} \end{cases} \\ (A)_{i,j} &= \begin{cases} 1 & \text{if $v_i$ and $v_j$ are adjacent} \\ 0 & \text{otherwise} \end{cases} \end{aligned}\]Kirchhoff’s Theorem (Matrix-Tree Theorem)
Theorem
그래프 $G$의 스패닝 트리의 개수를 $\tau(G)$라고 하면 임의의 $i$에 대해 다음이 성립한다.
\[\tau(G)=\det(L_G[i])\]행렬 $A$에 대해 $A[i]$는 행렬 $A$에서 $i$번째 행과 열을 제거한 행렬을 말한다.
Proof
수학적 귀납법을 사용하거나, Cauchy-Binet Formula를 사용하여 증명할 수 있다.
Mathematical Induction
먼저 그래프가 정점 2개와 간선 0개로 구성되어 있다면, 라플라시안 행렬은 다음과 같다.
\[L_G = \begin{bmatrix}0&0\\0&0 \end{bmatrix}\]이때, $\det(L_G[1]) = \det(L_G[2]) = \tau(G) = 0$이므로 정리가 성립한다.
이제 주어진 그래프에서 적당한 정점 $i$를 고르고, 이 정점을 포함하는 적당한 간선 $e=(i,j)$를 잡는다. 스패닝 트리의 개수는 $e$를 포함하거나, 포함하지 않을 것임은 자명한 사실이다. 따라서 다음과 같이 정의를 할 수 있겠다.
- 삭제 : 간선 $e$를 제거한 그래프로, $G-e$로 표현한다.
- 병합 : 노드 $i,j$를 하나로 합친 그래프로, $G/e$로 표현한다.
그리고 $\tau(G)$는 다음과 같이 표현된다.
\[\tau(G)=\tau(G-e)+\tau(G/e)\]따라서 이제 $\det(L_G[i]) = \det(L_{G-e}[i]) + \det(L_{G/e}[i])$만 증명하면, 수학적 귀납법에 의해 키르히호프의 정리를 증명할 수 있다.
먼저 삭제한 경우를 살펴보자. 어차피 $L_G[i]$에서 $i$번째 행과 열은 제거되었으므로 노드 $i$는 내버려두고 노드 $j$를 살펴보면 차수가 1 감소했음을 알 수 있다. 따라서 다음이 성립한다.
\[\begin{aligned} \det(L_G[i]) &= \det(L_{G-e}[i] + E_{jj}) \\ &= \det(L_{G-e}[i]) + \det(L_{G-e}[i,j]) \\ &= \det(L_{G-e}[i]) + \det(L_G[i,j]) \end{aligned}\]위 식을 이해하기 위해 간단한 추가설명을 하면 $E_{ii}$는 $(i,i)$의 원소만 1, 나머지는 0인 행렬을 말한다. 이를 바탕으로 임의의 행렬 $A$에 대해 행렬식을 계산해보면
\[\det(A+E_{ii}) = \det(A)+\det(A[i])\]가 성립한다. 그 이유는 순열을 통해 행렬식을 계산하는 방법을 생각해보면 되는데, $A_{ii}$를 1 증가시킴으로써 더해지는 값들은 $(i,i)$를 지나는 순열에 대한 alternating sum과 동치이고, 이는 곧 $\det(A[i])$이다.
위 부분은 LGV lemma와도 꽤나 큰 관련이 있는 것 같은데, 추후 관계를 밝힐 필요가 있다.
이때, $L_G[i,j]$는 $L_{G-e}[i,j]$와 같음은 꽤나 자명하다.
그런데, 병합한 경우를 잘 살펴보자. 노드 $i$를 노드 $j$에 겹치는 것으로 생각한다면 $L_G$에서 $i$번째 행과 열을 제거하고, $j$번째 행과 열의 값을 변경한 것으로 볼 수 있다. 따라서, $L_{G/e}[j]=L_G[i,j]$이므로, 다음이 성립한다.
\[\begin{aligned} \det(L_G[i]) &= \det(L_{G-e}[i]) + \det(L_{G/e}[j]) \\ &= \tau(G-e) + \tau(G/e) = \tau(G) \end{aligned}\]Cauchy-Binet Formula
TMI
그래프의 라플라시안 행렬은 실제로 미적분학의 $\Delta$와 비슷한 역할을 한다. 각 노드의 스무스함을 계산할 수 있다.
위에서 정의한 $\tau(G)=\tau(G-e)+\tau(G/e)$는 deletion-contraction formula라고 부르며, 채색 다항식 Chromatic Polynomial 도 이의 일종이다.
또한 $L_G$에서 $i$번째 행과 열을 지우지 않더라도 $i$번째 행, $j$번재 열을 지운 후 $(-1)^{i+j}$를 곱해주면 결과는 같게 나온다. -> 이것이 의미하는 것 = 스피닝 트리의 개수는 $L_G$의 cofactor(여인수)와 동일!