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

Особую роль в приложениях играют о стовные деревья графа – древесные подграфы, в которые входят все вершины графа. Известна (Кирхгоф) процедура, позволяющая по матрице смежности найти полное число древесных остовов.

Матрицей Кирхгофа графа G(V,E) называется матрица K_n´n, элементы которой определяются следующим образом:

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

Теорема Кирхгофа. Число остовных деревьев в связном графе G порядка n³2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G).

Задача: найдите все остовные деревья графа А.