Нахождение числа остовов графа

[Voenstal]

Попалось мне на зачете такое задание - найти число остовов у данного графа. Вроде бы, все ясно - составить матрицу Кирхгофа, а затем найти алгебраическое дополнение
произвольного элемента. Но вот как вычислить это дополнение для матрицы размерности 8х8 - я просто не представляю. Раскладывать по строке - дело долгое и муторное, да и моих серых клеток не хватит для такого. быть может, есть какие-то альтернативные пути решения ?

[whitefox]

Есть. Перечисление остовных деревьев. Эффективные алгоритмы можно найти, например, у Д. Кнута в "Искусство программирования" Т. 4, параграф 7.2.1.6 Остовные деревья.

[Markiyan Hirnyk]

Механизировано в Мэйпле.

[Voenstal]

И еще такой вопрос - есть ли разница между остовом и остовным деревом ? Просто много где описываются эти понятия как синонимы.

[whitefox]

Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева".

[Voenstal]

whitefox в сообщении #1175868 писал(а):

Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева".

Для меня немного странное ИМХО, ибо в задании это - разные понятия, как мне кажется

[whitefox]

А мне кажется, что это разные задания:

1. Подсчитать общее число остовных деревьев.
2. Построить одно из них (любое).

Но если "остов" не синоним "остовного дерева", то что он может обозначать?

[Voenstal]

whitefox в сообщении #1175894 писал(а):

А мне кажется, что это разные задания:

Но если "остов" не синоним "остовного дерева", то что он может обозначать?

Честно - не знаю. Но судя по всему - оно так и есть. Спасибо за помощь)

[Brukvalub]

Voenstal в сообщении #1175897 писал(а):

Честно - не знаю. Но судя по всему - оно так и есть.

Для меня непререкаемым авторитетом в маркизах графах является монография Дистеля. Так вот, в ней никаких "остовов" у графа не определяется, а определяется "остовное дерево" и кое-где считается число "остовных деревьев".