Kirchhoff 정리. 신장 트리의 개수 구하기¶
문제: 인접 행렬로 표현된 연결 무방향 그래프(다중 간선이 있을 수 있음)가 주어집니다. 이 그래프의 서로 다른 신장 트리의 개수를 구하십시오.
다음 공식은 1847년 Kirchhoff가 증명했습니다.
Kirchhoff의 행렬-트리 정리¶
$A$를 그래프의 인접 행렬이라 합시다. $A_{u,v}$는 $u$와 $v$ 사이의 간선 개수입니다. $D$를 그래프의 차수 행렬이라 합시다. $D$는 대각 행렬이며, $D_{u,u}$는 정점 $u$의 차수입니다(다중 간선과 루프, 즉 정점 $u$를 자기 자신과 연결하는 간선도 포함합니다).
그래프의 라플라시안 행렬은 $L = D - A$로 정의됩니다. Kirchhoff 정리에 따르면 이 행렬의 모든 여인수는 서로 같으며, 그 값은 그래프의 신장 트리 개수와 같습니다. 행렬의 $(i,j)$ 여인수는 $i$번째 행과 $j$번째 열을 제거하여 얻은 행렬의 행렬식에 $(-1)^{i + j}$를 곱한 값입니다. 따라서 예를 들어 행렬 $L$의 마지막 행과 마지막 열을 삭제하면, 그 결과로 얻은 행렬의 행렬식의 절댓값이 신장 트리의 개수가 됩니다.
행렬의 행렬식은 가우스 방법을 사용하여 $O(N^3)$에 구할 수 있습니다.
이 정리의 증명은 꽤 어려우므로 여기서는 다루지 않습니다. 증명의 개요와, 다중 간선이 없는 그래프 및 방향 그래프에 대한 정리의 변형은 Wikipedia를 참고하십시오.
Kirchhoff의 회로 법칙과의 관계¶
Kirchhoff의 행렬-트리 정리와 전기 회로에 대한 Kirchhoff의 법칙은 아름다운 방식으로 연관되어 있습니다. (옴의 법칙과 Kirchhoff의 제1법칙을 사용하여) 회로의 두 점 $i$와 $j$ 사이의 저항 $R_{ij}$가 다음과 같음을 보일 수 있습니다.
여기서 행렬 $L$은 역저항 행렬 $A$($A_{i,j}$는 점 $i$와 $j$ 사이 도체의 저항의 역수입니다)로부터 Kirchhoff의 행렬-트리 정리에서 설명한 절차를 사용하여 얻습니다. $T^j$는 행과 열 $j$를 제거한 행렬이고, $T^{(i,j)}$는 두 행과 두 열 $i$와 $j$를 제거한 행렬입니다.
Kirchhoff 정리는 이 공식에 기하학적 의미를 부여합니다.