Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 10.08.2013, 19:33
Новичок

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

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

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

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

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

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

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск мостов в графе Masha Реализация, исходники, языки 1 24.12.2009 20:34