Русская Википедия:Матричная теорема о деревьях

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.

Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.Шаблон:Нет в источнике

Формулировка

Пусть <math>G</math> — связный помеченный граф с матрицей Кирхгофа <math>M</math>. Все алгебраические дополнения матрицы Кирхгофа <math>M</math> равны между собой и их общее значение равно количеству остовных деревьев графа <math>G</math>.

Пример

граф	3 его остовных дерева
<math> \begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix} </math>	<math> \begin{matrix} 1 & & 4\\ \mid & & \mid \\ 2 & - & 3 \end{matrix} </math>	<math> \begin{matrix} 1 & & 4\\ \mid & \smallsetminus & \mid \\ 2 & & 3 \end{matrix} </math>	<math> \begin{matrix} 1 & & 4\\ & \smallsetminus & \mid \\ 2 & - & 3 \end{matrix} </math>

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

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

Следствия

Из матричной теоремы выводится

• Формула Кэли — число остовных деревьев полного графа <math>K_n</math> равно <math>n^{n-2}</math>.
• Число остовных деревьев полного двудольнoгo графа <math>K_{m,n}</math> равно <math>m^{n-1}\cdot n^{m-1}</math>.

Обобщения

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

Ссылки

• Теорема Кирхгофа