Матричная теорема о деревьях

Матричная теорема о деревьях (Matrix tree theorem), также известная как Теорема Кирхгофа — теорема теории конечных графов.

Теорема Кирхгофа-Трента

Пусть $G$ — связный помеченный граф с матрицей Кирхгофа $M$. Все алгебраические дополнения матрицы Кирхгофа $M$ равны между собой и их общее значение есть число остовных деревьев графа $G$.
Можно расширить теорему на случай мультиграфов и взвешенных графов. Тогда алгебраические дополнения элементов матрицы Кирхгофа для взвешенного графа будут равны сумме произведений проводимости всех остовов. Частный случай получается, если взять проводимости равными 1: сумма произведений проводимостей остовов будет равна числу остовов.

Доказательство

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Пример

граф G	каркасы (3 шт)
$\begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ \mid & & \mid \\ 2 & - & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & & 3 \end{matrix}$	$\begin{matrix} 1 & & 4\\ & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix}$

Для графа G с матрицей смежности $A=\begin{bmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix}$  получаем: $M=\begin{bmatrix} 2 & -1 & -1 & 0\\ -1 & 2 & -1 & 0\\ -1 & -1 & 3 & -1\\ 0 & 0 & -1 & 1 \end{bmatrix}$.

Алгебраическое дополнение, например, элемента M_{1, 2} есть $(-1)^{(1+2)}\begin{vmatrix} -1 & -1 & 0\\ -1 & 3 & -1\\ 0 & -1 & 1 \end{vmatrix}=3$, что совпадает с количеством каркасов.

Ссылки

• Графы и их применение
• Теорема Кирхгофа