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

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

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

Формулировка[править | править исходный текст]

Пусть G — связный помеченный граф с матрицей Кирхгофа M. Все алгебраические дополнения матрицы Кирхгофа 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}
.

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

Обобщения[править | править исходный текст]

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


Ссылки[править | править исходный текст]