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

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

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

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

Нехай ${\displaystyle G}$ — зв'язний розмічений граф із матрицею Кірхгофа ${\displaystyle M}$. Усі алгебричні доповнення матриці Кірхгофа ${\displaystyle M}$ рівні між собою та їх спільне значення дорівнює кількості кістякових дерев графа ${\displaystyle G}$.

Приклад

граф	3 його кістякових дерева
${\displaystyle {\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&-&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\\mid &&\mid \\2&-&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\\mid &\smallsetminus &\mid \\2&&3\end{matrix}}}$	${\displaystyle {\begin{matrix}1&&4\\&\smallsetminus &\mid \\2&-&3\end{matrix}}}$

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

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

Наслідки

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

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

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

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