Задача. Найти подграф и т.д.

[useroto]

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

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

[paha]

useroto в сообщении #391292 писал(а):

Вес максимального тяжелого ребра подграфа минемален.

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

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

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

[useroto]

да, только вес наитяжелейшего.

[paha]

paha в сообщении #391296 писал(а):

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

[useroto]

да решения нет

[paha]

useroto в сообщении #391300 писал(а):

да решения нет

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

[ИСН]

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

[sup]

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

[ИСН]

ох фак
да уж

[useroto]

paha в сообщении #391308 писал(а):

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

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

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

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

[deep blue]

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

[paha]

deep blue в сообщении #391354 писал(а):

А мне навскидку кажется, что полиномиальая проверка тоже простая

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

[deep blue]

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

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

[sup]

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

[sup]

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