2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Нахождение числа остовов графа
Сообщение10.12.2016, 06:50 


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

Изображение

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение10.12.2016, 16:41 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение10.12.2016, 16:48 


11/07/16
801
Механизировано в Мэйпле.

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 03:31 


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

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 09:55 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева". :-)

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:24 


30/11/16
13
whitefox в сообщении #1175868 писал(а):
Имхо, "остов" это слово из студенческого жаргона для обозначение "остовного дерева". :-)


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

Изображение

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:39 
Заслуженный участник
Аватара пользователя


19/12/10
1546
А мне кажется, что это разные задания:
  1. Подсчитать общее число остовных деревьев.
  2. Построить одно из них (любое).

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

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 11:48 


30/11/16
13
whitefox в сообщении #1175894 писал(а):
А мне кажется, что это разные задания:

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


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

 Профиль  
                  
 
 Re: Нахождение числа остовов графа
Сообщение11.12.2016, 14:18 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Voenstal в сообщении #1175897 писал(а):
Честно - не знаю. Но судя по всему - оно так и есть.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group