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

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

Довів Густав Кірхгоф 1847 року; мотивуванням цієї теореми стали розрахунки електричних кілШаблон:Нема в джерелі.

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

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

Приклад

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

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

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

Наслідки

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

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

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

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

Література

• Шаблон:Cite book

Посилання

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