2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 На графы, уточнить
Сообщение02.05.2015, 12:16 


20/10/12
235
Вот задачка
"Предприятие, где вы работаете выиграло тендер на постройку сети лунных станций (количество станций оговорено). Вы на другой же день представили руководству готовый топологический план сети. Однако ваш начальник сказал, что решение подобных вопросов не в вашей компетенции, и план сети предстоит выбрать именно ему. В отместку вы решили подготовить полный список всех вариантов организации такой сети. Как профессионал вы, разумеется, в курсе, что в сети не должно быть «лишних» линий коммуникации."

Понятно, что нам нужны все связные графы с N вершинами, но что-то данных маловато. В постановке задачи еще записано, что надо юзнуть какой-нибудь конкретный алгоритм на графах, это сбивает. Я на свой вкус попробовал бы полный перебор с проверкой на связность. Но что-то не хочется, ибо вот последовательность числа всевозможных графов с n вершинами:http://oeis.org/A000088. Может есть что-то поинтересней? Про циклы эйлера, гамильтона думал, они тут ни при чем.

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


01/09/13
4318
shukshin в сообщении #1010304 писал(а):
Про циклы эйлера, гамильтона думал, они тут ни при чем

А откуда вообще возмутся циклы?

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение02.05.2015, 13:53 


20/10/12
235
это к тому, что я совсем отчаялся найти нечто более оптимальное

-- 02.05.2015, 14:49 --

неожиданный поворот в задаче: получается, что надо перечислить все деревья?

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение03.05.2015, 08:49 


01/12/11

1047
shukshin вам не нужны "«лишние» линии коммуникаций"? Тогда одну станцию, соедините с остальными.

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение03.05.2015, 09:03 


20/10/12
235
Skeptic,
"...полный список всех вариантов организации такой сети."
Но, один из вариантов, конечно, будет таким.

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение03.05.2015, 15:04 


01/12/11

1047
Построить полный список не сложно.
Например.
1. Для каждой станции строим соединение звездой.
2. Соединяем две станции. Оставшиеся станции разбиваем на две группы. Первую группу соединяем с первой станцией, вторую группу со второй. Изменяя состав групп, получим все соединения для пары постоянно соединённых станций. Так делаем для всех пар станций.
3. Аналогично строим сеть для троек станций. И т.д.
Только какой смысл во всех вариантах?

shukshin, измените задачу, добавив условие оптимизации.

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


01/09/13
4318
shukshin в сообщении #1010333 писал(а):
неожиданный поворот в задаче: получается, что надо перечислить все деревья?

Получается что да. Причём вершины надо считать помеченными, как кажется....

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение03.05.2015, 21:45 


20/10/12
235
Geen,
если честно, эту задачу я решать не умею.
судя по всему нужно что-то такое:
http://math.stackexchange.com/questions/407562/gallery-of-unlabelled-trees-with-n-vertices
но алгоритма не найти.

-- 03.05.2015, 21:54 --

Geen,
есть совершенно ломовая идея с изоморфными деревьями в результате,
а именно полный перебор по матрице смежности, по n(n-1)/2 элементам с проверкой графа на то, является ли он деревом.

 Профиль  
                  
 
 Re: На графы, уточнить
Сообщение10.05.2015, 22:44 


08/09/13
210
Можно перебирать код Прюфера и каждый раз восстанавливать по нему дерево.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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