2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

Изображение

 
 
 
 Re: Нахождение числа остовов графа
Сообщение10.12.2016, 16:41 
Аватара пользователя
Есть. Перечисление остовных деревьев. Эффективные алгоритмы можно найти, например, у Д. Кнута в "Искусство программирования" Т. 4, параграф 7.2.1.6 Остовные деревья.

 
 
 
 Re: Нахождение числа остовов графа
Сообщение10.12.2016, 16:48 
Механизировано в Мэйпле.

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 03:31 
И еще такой вопрос - есть ли разница между остовом и остовным деревом ? Просто много где описываются эти понятия как синонимы.

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 09:55 
Аватара пользователя
Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева". :-)

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:24 
whitefox в сообщении #1175868 писал(а):
Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева". :-)


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

Изображение

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:39 
Аватара пользователя
А мне кажется, что это разные задания:
  1. Подсчитать общее число остовных деревьев.
  2. Построить одно из них (любое).

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

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:48 
whitefox в сообщении #1175894 писал(а):
А мне кажется, что это разные задания:

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


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

 
 
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 14:18 
Аватара пользователя
Voenstal в сообщении #1175897 писал(а):
Честно - не знаю. Но судя по всему - оно так и есть.

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group