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

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

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

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

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

Проблема: Сказали копать в сторону алгоритма с потоками(Форда - Фалкерсона), но не могу допереть как это сделать. Может кто подскажет?
  #2  
Старый 25.12.2010, 17:41
гocть

 
Сообщений: n/a

двоичным поиском ищеш вес макс ребра, и проверяеш двусвязность
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Граф tewi Реализация, исходники, языки 5 01.11.2010 15:47
Как красиво нарисовать граф? Selmaril Графы 2 08.10.2010 22:45
Платоновый граф helm Графы 3 25.12.2009 01:02
граф в win32 гость Графы 11 08.04.2009 03:07
задача про кубический граф гость Графы 4 22.05.2008 09:42