Матрична теорема про дерева або теорема Кірхгофа — дає вираз для кількості кістякових дерев графа через визначник певної матриці.
Довів Густав Кірхгоф 1847 року; мотивуванням цієї теореми стали розрахунки електричних кіл .
Формулювання Нехай — зв'язний розмічений граф із матрицею Кірхгофа . Усі алгебричні доповнення матриці Кірхгофа рівні між собою та їх спільне значення дорівнює кількості кістякових дерев графа .
Приклад граф 3 його кістякових дерева Для графа G з матрицею суміжності отримуємо: .
Алгебричне доповнення, наприклад, елемента M1, 2 дорівнює , що збігається з кількістю кістяків.
Наслідки З матричної теореми виводиться:
Формула Келі — число кістяків повного графа дорівнює . Число кістяків повного двочасткового графа дорівнює .
Узагальнення Теорема узагальнюється на випадок мультиграфів і зважених графів. Для зваженого графа алгебричні доповнення елементів матриці Кірхгофа рівні сумі за всіма кістяками добутків ваг усіх їхніх ребер. Частковий випадок виходить, якщо взяти ваги рівними 1: сума добутків ваг кістяків дорівнюватиме кількості кістяків.
Примітки
Література
Посилання Теорема Кірхгофа