2014 dxdy logo

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

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




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

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 12:54 
Аватара пользователя
useroto в сообщении #391292 писал(а):
Вес максимального тяжелого ребра подграфа минемален.

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

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

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

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 12:56 
Аватара пользователя
paha в сообщении #391296 писал(а):
А начальный граф какой? Если там есть висячие вершины, то решений нет

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:06 
Аватара пользователя
useroto в сообщении #391300 писал(а):
да решения нет

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:09 
Аватара пользователя
Ой, ну это делается очень тупо. Берём все рёбра, сортируем по весам. Проверяем, что исходный граф удовлетворяет (2) - если нет, то всё, если да, то идём дальше. Потом выкидываем самое тяжёлое ребро (или рёбра, если их несколько одинаковых) и проверяем опять. И так до упора.
Полиномиально? - вполне.

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:19 
А как насчет полиномиальности проверки? Пусть, например, граф кубический. Требуемое свойство - почти что гамильтонов цикл. А это NP-полная задача. Так, что могут быть проблемы.

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 13:27 
paha в сообщении #391308 писал(а):
так что, алгоритм сначала должен определить есть ли подграф с заданными свойствами?


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

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

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

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 14:14 
Аватара пользователя
deep blue в сообщении #391354 писал(а):
А мне навскидку кажется, что полиномиальая проверка тоже простая

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

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

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

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 14:50 
2 deep blue. Я поначалу точно так же подумал, а потом придумал контрпример. Квадрат с диагональю. Берем путь в виде буквы Z. Второй путь предъявить уже нельзя. Но граф все таки "хороший". Но, похоже, все нормально. Находим цикл - стягиваем его в одну вершину.
И так, пока есть циклы. Вроде как при этом основное свойство (наличие 2-х путей) - инвариантно. Такая проверка - уж точно полиномиальна.

 
 
 
 Re: Задача. Найти подграф и т.д.
Сообщение25.12.2010, 15:56 
А дальше уж и вовсе просто. Граф обладает свойством (2) (см. условие задачи) если и только если он остается связным после удаления любого ребра. Таким образом алгоритм ИСН - самое то. Только может с целью "оптимизьма"его стоит "развернуть"? Начать добавлять "легкие" ребра понемножку. И, что нибудь типа алгоритма Дейкстры?

 
 
 [ Сообщений: 18 ]  На страницу 1, 2  След.


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