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

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

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

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

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


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





Статистика

Рейтинг@Mail.ru