Математика / Дискретная математика

Теорема Кирхгофа: число остовов через лапласиан

Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.

Опубликовано: Обновлено:

Формула

$$\tau(G)=\det L^{(i)},\qquad L=D-A$$
Схема Один из четырёх остовов цикла
1234

Выделены рёбра12,23,34; ребро41удалено. Остальные три остова получаются удалением другого единственного ребра.

Обозначения

$G$
конечный простой неориентированный граф, —
$A$
матрица смежности графа, —
$D$
диагональная матрица степеней вершин, —
$L^{(i)}$
матрица L с удалёнными строкой i и столбцом i, —
$\tau(G)$
число остовных деревьев графа, шт.

Условия применения

Здесь рассматривается простой неориентированный граф без петель с n≥2 вершинами. A симметрична, D содержит степени по диагонали. Удаляют одну строку и одноимённый столбец, получая матрицу порядка n−1. Для несвязного графа остовного дерева нет и определитель равен нулю.

Ограничения

Определитель полной L всегда нулевой и не является числом остовов: нужен минор. Для ориентированных и взвешенных графов используются соответствующие варианты теоремы с иными определениями. Большие целые определители лучше считать точным методом; округление чисел с плавающей точкой может испортить целый ответ.

Подробное объяснение

Остовное дерево содержит все вершины исходного графа, связно и имеет ровно n−1 рёбер. Для связного графа остов обычно не единственный. Матрица L=D−A хранит локальную структуру: степени на диагонали, минус единица для соседних разных вершин и ноль для несоседних. Сумма каждой строки равна нулю.

Почему нужен минор? У полной L есть нулевой собственный вектор из одинаковых единиц, поэтому её определитель обнуляется независимо от числа остовов. Удаление строки и столбца фиксирует одну вершину как опорную. Теорема утверждает, что каждый такой главный минор даёт одно и то же число остовных деревьев.

Идея доказательства использует матрицу инцидентности с произвольно ориентированными рёбрами: L=BBᵀ. После удаления строки формула Коши — Бине раскрывает определитель как сумму квадратов миноров по наборам n−1 рёбер. Минор равен по модулю единице для дерева и нулю для набора с циклом или без связности. Так каждый остов вносит ровно единицу.

На цикле из nвершин остов получается удалением одного ребра, поэтому их n. В полном графе K_nчисло равно n^(n−2). Эти два разных подсчёта дают удобные проверки матричного алгоритма. Матрица здесь считает существующие рёбра; добавление отсутствующего ребра меняет и степени, и смежность, поэтому обновлять только один из двух блоков неверно.

Как пользоваться формулой

  1. Пронумеруйте вершины и составьте симметричную матрицу смежности, проверив отсутствие петель и выбранный список рёбер.
  2. Найдите степени вершин и постройте L=D−A; каждая строка должна суммироваться в ноль до удаления координаты.
  3. Удалите одну строку и столбец с тем же индексом, затем найдите определитель оставшейся квадратной матрицы.
  4. Сравните ответ с другим главным минором или перебором малых наборов рёбер; число остовов должно быть целым и неотрицательным.

Историческая справка

Теорема о числе деревьев связывает исследования электрических сетей с комбинаторикой графов и традиционно носит имя Кирхгофа. Лапласиан возникает и в уравнениях токов, и в подсчёте остовов, но эти применения отвечают на разные вопросы: решение потенциалов и число связных ациклических подграфов.

В книге Ричарда Стэнли Topics in Algebraic Combinatorics, версия 2013 года, матричной теореме о деревьях посвящена отдельная глава. Современные лекционные доказательства используют инцидентность и формулу Коши — Бине, явно показывая, почему циклы дают нулевые слагаемые. Такое изложение объясняет независимость ответа от удалённой вершины и продолжает классическую связь алгебры с сетевой структурой; оно не сводится к вычислительному приёму для одного цикла.

Историческая линия формулы

Используется традиционное название «теорема Кирхгофа», или матричная теорема о деревьях. Здесь проверяется современная формулировка для простого неориентированного графа. Расширения на ориентированные и взвешенные сети требуют своих определений и не смешиваются с данным подсчётом.

Пример

Граф C4 состоит из рёбер 12,23,34,41. Каждая вершина имеет степень 2. Удалим четвёртую строку и столбец лапласиана. Остаётся матрица с рядами(2,−1,0), (−1,2,−1), (0,−1,2). Разложение определителя по первой строке:2·(2·2−(−1)(−1))−(−1)·((−1)·2−0)=2·3−2=4. Поэтому τ(C4)=4. Независимо удалим из цикла одно ребро: получаются четыре различных пути длины 3, каждый соединяет все четыре вершины и не имеет циклов. Любой набор из трёх рёбер C4 получается именно так, значит других остовов нет. Определитель безразмерен, а его целое значение интерпретируется как количество подграфов.

Частая ошибка

Нельзя использовать detLвместо главного минора: detL=0 из-за нулевых сумм строк. Удаление строки iи другого столбца jтребует учёта знака алгебраического дополнения, поэтому здесь выбирают одноимённые индексы. Остовное дерево не обязано быть кратчайшим или минимальным по весу. Изолированная вершина означает отсутствие остова всего графа.

Практика

Задачи с решением

Треугольник

Условие. Найдите число остовов K3 через главный минор.

Решение. После удаления вершины минор имеет ряды(2,−1),(−1,2). Его определитель 4−1=3; каждый остов удаляет одно ребро треугольника.

Ответ. 3 остова.

Полный граф четырёх вершин

Условие. Найдите τ(K4).

Решение. Главный минор имеет 3 на диагонали и−1 в остальных клетках. Его собственные значения 1,4,4, определитель 16. Формула Кэли также даёт 4²=16.

Ответ. 16 остовов.

Дополнительные источники

  • https://math.mit.edu/~rstan/algcomb/algcomb.pdf
  • https://www.ltcc.ac.uk/media/london-taught-course-centre/documents/Notes-for-lecture-on-2-December---10.pdf

Связанные формулы

Математика

Хроматический многочлен графа: правило удаления и стягивания

$P_G(k)=P_{G-e}(k)-P_{G/e}(k)$

Хроматический многочлен P_G(k) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.

Информатика

Алгоритм A*: кратчайший путь по оценке f=g+h

$f(v)=g(v)+h(v)$

Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.

Математика

Код Прюфера: число деревьев с заданными степенями

$N(d_1,\ldots,d_n)=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!},\qquad d_i\ge1,\quad\sum_i d_i=2(n-1)$

В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.

Математика

Формула Кэли: число деревьев с помеченными вершинами

$T_n=n^{n-2},\qquad n\ge2$

Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.