Подсчёт числа остовных деревьев с помощью матрицы Кирхгофа

Теорема:

Число остовов в связном неодноэлементном обыкновенном графе [math]G[/math] равно алгебраическому дополнению любого элемента матрицы Кирхгофа [math]B(G)[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]G[/math] - произвольный связный обыкновенный [math](n, m)[/math]-граф, [math]n \ge 2[/math] и [math]I[/math] - матрица инцидентности какой-либо ориентации графа [math]G[/math]. Заметим, что [math]m \ge n - 1[/math] в силу связности графа [math]G[/math]. По лемме выполняется [math]B = B(G) = I * I^T[/math]. Пусть [math]B'[/math] - подматрица матрицы [math]B[/math], полученная удалением последней строки. Тогда имеем [math]B' = J * J^T[/math], где [math]J[/math] - это [math]((n - 1) \times m)[/math] - матрица. Очевидно, [math]B_{nn} = det B'[/math] есть алгебраическое дополнение элемента [math]\beta_{nn}[/math] в матрице Кирхгофа [math]B[/math]. В силу формулы Бине-Коши [math]B_{nn}[/math] равно сумме квадратов всех миноров порядка [math](n - 1)[/math] матрицы [math]J[/math]. Согласно лемме каждый такой минор [math]M[/math] равен [math]\pm 1[/math], если остовный подграф графа [math]G[/math], ребра которого соответствуют столбцам, вошедшим в матрицу минора [math]M[/math], является деревом, и равен [math]0[/math] в другом случае. Следовательно, [math]B_{nn}[/math] равно числу остовов графа [math]G[/math]. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.

[math]\triangleleft[/math]

Источники:
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.