Остовы графа

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

Определение. Полученное дерево называется остовом, т. е. остовом называется связный частичный граф данного связного графа , содержащий все вершины графа , но не содержащий циклов.

Пример.Рассмотрим, например, граф, изображенный на рисунке 6.71. Удалим из него ребра и и получим остов. Если удалить ребра и , то получим другой остов.

Рисунок 6.71

Два остова в считаются различными, если они отличаются хотя бы одним ребром.

Для того чтобы имел более одного остова, необходимо и достаточно существование хотя бы одного цикла в .

Для полного (простого) графа перечисление остовов есть перечисление всех помеченных деревьев с вершинами графа , так что число остовов равно .

В общем случае число остовов получил Кирхгоф.

Определение. Матрицей Кирхгофа простого графа называется -матрица с элементами, которые определяются так:

Сумма элементов в каждой строке и каждом столбце матрицы равна нулю.

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