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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Формулювання[ред. | ред. код]

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

Приклад[ред. | ред. код]

граф 3 його кістякових дерева

Для графа G з матрицею суміжності  отримуємо: .

Алгебричне доповнення, наприклад, елемента M1, 2 дорівнює , що збігається з кількістю кістяків.

Наслідки[ред. | ред. код]

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

Узагальнення[ред. | ред. код]

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

Примітки[ред. | ред. код]

  1. Kirchhoff, Gustav. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird // Annalen der Physik. — 1847. — Bd. 148, Nr. 12 (1 April). — S. 497—508.

Посилання[ред. | ред. код]