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

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

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

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

Графы
Помогите пожалуйста! Как найти минимальный разрез в графе, дан именно связный граф, а не сеть.
// Вообще, надо найти минимальное количество вершин, удаление которых делает связный граф несвязным. Может есть другие способы?..
  #2  
Старый 09.12.2010, 22:39
гостъ

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

разрез, разделяющий две вершины s и t находится максимальным потоком в сети со стоком/истоком в s и t.

одну из них, скажем s, фиксируешь произвольно. вторую вершину t перебирашь, считаешь поток, ищещ минимум, это и будет минимальный разрез.

еще есть алгоритм стоера-вагнера.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача на графы.. Katusha...) Задачи 0 12.05.2010 22:36
Задача на графы гость Математические алгоритмы 1 08.05.2010 08:39
графы Юрий85 Реализация, исходники, языки 7 08.01.2010 16:07
Графы гость Задачи 4 23.11.2009 14:32
ГРАФЫ Atij Задачи 3 14.06.2007 21:12