2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача. Найти подграф и т.д.
Сообщение25.12.2010, 12:53 


25/12/10
5
Дано: Неориентированный граф. Всем рёбрам приписаны веса.
Найти: Подграф соответствующий след. свойствам:
1. Содержит все вершины исходного графа.
2. Любые две вершины соединены двумя(и более) непересекающимися(по ребрам) путями.
3. Вес максимального тяжелого ребра подграфа минемален.
Требования: Алгоритм должен быть полиномиальный.

Может кто подскажет, чем это можно сделать?

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


03/02/10
1928
useroto в сообщении #391292 писал(а):
Вес максимального тяжелого ребра подграфа минемален.

т.е. минимизируем не общий вес ребер подграфа, а только вес наитяжелейшего?

-- Сб дек 25, 2010 12:56:22 --

А начальный граф какой? Если там есть висячие вершины, то решений нет

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 12:56 


25/12/10
5
да, только вес наитяжелейшего.

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


03/02/10
1928
paha в сообщении #391296 писал(а):
А начальный граф какой? Если там есть висячие вершины, то решений нет

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 12:58 


25/12/10
5
да решения нет

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


03/02/10
1928
useroto в сообщении #391300 писал(а):
да решения нет

так что, алгоритм сначала должен определить есть ли подграф с заданными свойствами?

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


18/05/06
13437
с Территории
Ой, ну это делается очень тупо. Берём все рёбра, сортируем по весам. Проверяем, что исходный граф удовлетворяет (2) - если нет, то всё, если да, то идём дальше. Потом выкидываем самое тяжёлое ребро (или рёбра, если их несколько одинаковых) и проверяем опять. И так до упора.
Полиномиально? - вполне.

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:19 
Заслуженный участник


22/11/10
1183
А как насчет полиномиальности проверки? Пусть, например, граф кубический. Требуемое свойство - почти что гамильтонов цикл. А это NP-полная задача. Так, что могут быть проблемы.

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


18/05/06
13437
с Территории
ох фак
да уж

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:27 


25/12/10
5
paha в сообщении #391308 писал(а):
так что, алгоритм сначала должен определить есть ли подграф с заданными свойствами?


скорее всего не сначала, а выявить это при работе. Так как условие найти, можно и не найти. Просто не могу подобрать критерий для точного наличия подграфа с заданными свойствами.

-- Сб дек 25, 2010 13:42:22 --

возможно задачу можно свести к нахождению потока(Форда - Фалкерсона), но как?

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 14:08 


23/11/09
173
А мне навскидку кажется, что полиномиальая проверка тоже простая.
Находим путь из вершины а в вершину б, вычеркиваем все ребра этого пути и снова находим путь из а в б. При сущствовании двух разных (по ребрам) путей, такой простой алгоритм всегда приведет к решению вроде.

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


03/02/10
1928
deep blue в сообщении #391354 писал(а):
А мне навскидку кажется, что полиномиальая проверка тоже простая

"проверка" полиномиальна, с этим, вроде, никто не спорит... а вот дальше -- избиение жирных...

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 14:26 


23/11/09
173
А если проверка существования двух разных путей (из а в б) полиномиальна, то как уже писал ИСН и sup общий алгоритм тоже простой и полиномиальный.

PS Кстати к алгоритму нахождения потока красиво сводится другая задача, найти элементарный кратчайший путь из a в b содержащий с (граф с положительными весами). Но в нашей задаче это не нужно)

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 14:50 
Заслуженный участник


22/11/10
1183
2 deep blue. Я поначалу точно так же подумал, а потом придумал контрпример. Квадрат с диагональю. Берем путь в виде буквы Z. Второй путь предъявить уже нельзя. Но граф все таки "хороший". Но, похоже, все нормально. Находим цикл - стягиваем его в одну вершину.
И так, пока есть циклы. Вроде как при этом основное свойство (наличие 2-х путей) - инвариантно. Такая проверка - уж точно полиномиальна.

 Профиль  
                  
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 15:56 
Заслуженный участник


22/11/10
1183
А дальше уж и вовсе просто. Граф обладает свойством (2) (см. условие задачи) если и только если он остается связным после удаления любого ребра. Таким образом алгоритм ИСН - самое то. Только может с целью "оптимизьма"его стоит "развернуть"? Начать добавлять "легкие" ребра понемножку. И, что нибудь типа алгоритма Дейкстры?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

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



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

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


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

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