Показать сообщение отдельно
  #1  
Старый 10.08.2013, 19:33
Новичок

Отправить личное сообщение для haddx Посмотреть профиль Найти все сообщения от haddx
 
Регистрация: 10.08.2013
Сообщений: 2

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

Вот сама задача: дан связный неорграф, нужно найти минимальное число ребер (и, конечно, сами ребра), добавление которых в граф уберет из него все мосты (формулировка на основе задачи о надежности городской компьютерной сети).

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

Моя проблема в том, что не приходит в голову ни одной более менее оптимальной реализации. Прошу ваших идей и предложений (код не нужен, нужны только мысли =) )