Теорема Кірхгофа. Знаходження кількості кістякових дерев

Задача: задано зв'язний неорієнтований граф (з можливими кратними ребрами), поданий матрицею суміжності. Знайдіть кількість різних кістякових дерев цього графа.

Наведену нижче формулу довів Кірхгоф у 1847 році.

Коли підходить цей підхід?

• Потрібно порахувати кількість різних кістякових дерев графа, а не побудувати одне? (якщо потрібне мінімальне кістякове дерево → Крускал / Прим)
• Кількість вершин невелика, щоб обчислити визначник матриці Лапласа за $O(N^3)$ методом Гаусса?
• Граф неорієнтований (кратні ребра дозволені); для орієнтованих графів і варіацій потрібна відповідна версія теореми?

Матрична теорема Кірхгофа про дерева

Нехай $A$ — матриця суміжності графа: $A_{u,v}$ — це кількість ребер між $u$ та $v$. Нехай $D$ — матриця степенів графа: діагональна матриця, у якій $D_{u,u}$ дорівнює степеню вершини $u$ (з урахуванням кратних ребер і петель — ребер, що з'єднують вершину $u$ саму з собою).

Матриця Лапласа (лапласіан) графа визначається як $L = D - A$. Згідно з теоремою Кірхгофа, усі алгебраїчні доповнення цієї матриці рівні між собою, і вони дорівнюють кількості кістякових дерев графа. Алгебраїчне доповнення $(i,j)$ матриці — це добуток $(-1)^{i + j}$ на визначник матриці, яку ми отримуємо після викреслювання $i$-го рядка та $j$-го стовпця. Отже, можна, наприклад, викреслити останній рядок і останній стовпець матриці $L$, і абсолютне значення визначника отриманої матриці дасть нам кількість кістякових дерев.

Визначник матриці можна знайти за $O(N^3)$ за допомогою методу Гаусса.

Доведення цієї теореми досить складне і тут не наводиться; з нарисом доведення та варіаціями теореми для графів без кратних ребер і для орієнтованих графів можна ознайомитися у Вікіпедії.

Зв'язок із законами Кірхгофа для електричних кіл

Матрична теорема Кірхгофа про дерева та закони Кірхгофа для електричних кіл пов'язані напрочуд красивим чином. Можна показати (за допомогою закону Ома та першого закону Кірхгофа), що опір $R_{ij}$ між двома точками кола $i$ та $j$ дорівнює

$$R_{ij} = \frac{ \left| L^{(i,j)} \right| }{ | L^j | }.$$

Тут матриця $L$ отримується з матриці обернених опорів $A$ ($A_{i,j}$ — це величина, обернена до опору провідника між точками $i$ та $j$) за процедурою, описаною в матричній теоремі Кірхгофа про дерева. $T^j$ — це матриця з викресленими рядком і стовпцем $j$, а $T^{(i,j)}$ — це матриця з викресленими двома рядками та двома стовпцями $i$ і $j$.

Теорема Кірхгофа надає цій формулі геометричного змісту.

Задачі для практики

• CODECHEF: Roads in Stars
• SPOJ: Maze
• CODECHEF: Complement Spanning Trees

Відеоматеріали