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

Материал из Википедии — свободной энциклопедии

Текущая версия (не проверялась)

Матричная теорема о деревьях (Matrix tree theorem) - теорема теории конечных графов.

Содержание

1 Теорема Кирхгофа-Трента
2 Доказательство
3 Пример
4 Ссылки

[править] Теорема Кирхгофа-Трента

Пусть G — связный помеченный граф с матрицей смежности A. M — матрица, полученная из матрицы -A заменой $i$ -го элемента главной диагонали на $deg~v_i$ — степень вершины $i$ . Тогда все алгебраические дополнения матрицы M равны между собой и их общее значение есть число остовов (каркасов) графа G.

[править] Доказательство

[править] Пример

граф 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$ , что совпадает с количеством каркасов.