Пусть граф G=(V,E) имеет множество вершин V={v₁, …, v_p} и множество рёбер Е.

Пусть А есть матрица смежности вершин для G. Пусть М есть матрица, полученная из матрицы А заменой элемента i на главной диагонали на степень вершины v_i, то есть на число рёбер, принадлежащих вершине v_i.

Стягивающее дерево графа G (каркас ля G) есть наименьший по числу рёбер подграф-дерево графа G, соединяющий все вершины в G.

Теорема Кирхгофа: Все алгебраические дополнения матрицы М равны между собой и их общее число равно числу каркасов графа G.

Комментарии запрещены.