Матрична теорема про дерева

Матрична теорема про дерева або теорема Кірхгофа — дає вираз для кількості кістякових дерев графа через визначник певної матриці.

Довів Густав Кірхгоф 1847 року; мотивуванням цієї теореми стали розрахунки електричних кіл^{[відсутнє в джерелі]}.

Формулювання

Нехай $G$ — зв'язний розмічений граф із матрицею Кірхгофа $M$. Усі алгебричні доповнення матриці Кірхгофа $M$ рівні між собою та їх спільне значення дорівнює кількості кістякових дерев графа $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$, що збігається з кількістю кістяків.

Наслідки

З матричної теореми виводиться:

• Формула Келі — число кістяків повного графа $K_{n}$ дорівнює $n^{n-2}$.
• Число кістяків повного двочасткового графа $K_{m,n}$ дорівнює $m^{n-1}\cdot n^{m-1}$.

Узагальнення

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

Посилання

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