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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.12.2007, 16:44
гость

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

Минимальный разрез
Помогите пожалуйста найти минимальный разрез в графе и ребра входящие в него.
  #2  
Старый 09.12.2007, 17:09
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Эта задача тесно связана с максимальным потоком - видимо, среди алгоритмов его нахождения и надо копаться
  #3  
Старый 09.12.2007, 21:54
гость

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

Нахождение минимального s-t разреза: найди максимальный поток в графе, с истоком s, стоком t, найди множество S вершин, достижимых из истока в остаточной сети. (S,V\S) есть минимальный (канонический) разрез. Соответствующие ему ребра - все ребра, начала и концы которых находятся в S и V\S.

Глобальный минимальный разрез неориентированного графа целесообразнее искать алгоритмом Stoer-Wagner. Но можно и свести к потоку - выбери минимальный из всех s-t разрезов, где s - любая фиксированная вершина, а t пробегает V\{s}.
  #4  
Старый 10.12.2007, 03:54
гость

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

А где его можно найти(алгоритм Stoer-Wagner)?
  #5  
Старый 10.12.2007, 04:06
гость

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

http://shygypsy.com/tools/minCut.cpp

Описание/док-во если нужно ищи в гугле
  #6  
Старый 13.12.2007, 06:37
гость

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

Достаточно найти максимальный поток, а потом пустить в остаточной сети dfs из стока. S= {найденые вершины}. Тогда (S, V\S) - минимальный разрез
  #7  
Старый 13.12.2007, 21:25
гость

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

такой еще вопросик. Как сделать из графа st-сеть?
  #8  
Старый 01.06.2010, 19:24
гость

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

Что такое минимаксный разрез для потока и как его найти?
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
разрез минимального среднего веса Sema Задачи 1 02.11.2006 08:29