Матрица Кирхгофа

Для работы с остовными деревьями в теории графов графы пряно обозначать в виде матрицы Кирхгофа. Благодаря представлению графа в таком виде, матрица Кирхгофа может использоваться вместе с теоремой Кирхгофа для расчета количества остовных деревьев в графе.

Матрица Кирхгофа это комбинация матрицы степеней вершин и матрицы смежности L=A+B. Матрица степеней вершин. А это матрица размерностью где на главной диагонали расположены степени вершин графа (определение степени вершины графа дано в начале раздела).

Матрица степеней вершин для данного графа будет иметь вид :

Матрица смежности для данного графа будет иметь вид (заметим, что для смежных вершин используется обозначение -1, а не 1 как в классическом варианте матрицы смежности, в этом особенность матрицы Кирхгофа):

Матрица Кирхгофа будет иметь вид:

В общем виде матрица Кирхгофа записывается как:

Теорема:

Пусть — связный помеченный граф с матрицей Кирхгофа . Все алгебраические дополнения матрицы Кирхгофа равны между собой и их общее значение есть число остовных деревьев графа .

Пример. Дан граф , рассчитаем количество остовных деревьев графа:

Матрица Кирхгофа для данного графа будет иметь вид:

Найдём алгебраическое дополнение

На основе данного графа может быть получено 3 остовных дерева: