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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.05.2010, 20:12
Пользователь

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

максимальный поток в ориентированном графе
мне нужно придумать алгоритм который находит максимальный поток в графе (не в графе потока а в простом графе).
за О(|V|) а не за O(|V^2|) (проверка каждой пары)
  #2  
Старый 22.05.2010, 23:15
гость

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

невозможно. ребер ведь может быть V^2
  #3  
Старый 23.05.2010, 01:02
Пользователь

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

думаю что надо уточнить
поток определяют как N=(G=(V,E),c,s,t)
G - ориентированный граф
c - пропускная способность
s - источник
t - сток
в моей задаче дан граф G' с пропускной способностью,не поток.
чтобы построить из него поток надо добавить к графу источник и сток и соединить их ребрами к вершине/нам графа G' с какой либо пропускной способностью (может бесконечность , не знаю если подойдет).
---
в задаче просят узнать минимальный разрез графа G'
1.наивный метод это взять все пары вершин графа и найти максимальный поток (равно минимальному разрезу).
но вызывание алгоритма о максимальном потоке будет стоить для всех пар вершин в графе O(|v^2|)
2.просять выполнить задачу чтоб получилось O(|V|) вызовов
----
буду рад подсказке
спасибо!
  #4  
Старый 23.05.2010, 02:08
гость

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

у вас какая-то сильно нестандартная терминология. сами что ль придумали?

Сообщение от Parabol Посмотреть сообщение
думаю что надо уточнить
поток определяют как N=(G=(V,E),c,s,t)
это вы дали определение сети (flow network). поток (flow) - функция от ребер графа, вписывающаяся в ограничения по пропускным способностям.

Ну и надо говорить что O(V) - это число задач нахождения максимального потока к которым вы хотите сведите, а не сложность

Цитата:
2.просять выполнить задачу чтоб получилось O(|V|) вызовов
А вы выше написали что хотите сложность O(V)? Не операций, а вызовов оказывается? Ну так и прямо и сразу бы написали, а то никто вас не поймет.

Можно свести к O(V) задачам о макс. потоке. Зафиксируйте любую верщину x, перебирайте все остальные вершины y и решите по задачу о макс. потоке от x к y и от y к x. Минимум по всем y даст искомое число.
  #5  
Старый 23.05.2010, 02:16
Пользователь

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

спасибо!
но по моему это не верно... к примеру

Последний раз редактировалось Parabol, 23.05.2010 в 02:29.
  #6  
Старый 23.05.2010, 02:43
Пользователь

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

к примеру граф:
х1--->х2 (вес 100)
х1--->х3 (вес 100)
х3--->х4(вес 100)
х2--->х3(вес 1)
х2--->х4(вес 100)
(надеюсь понятно)
максимальный поток 200 -> минимальный разрез (S={x1} T={x2,x3,x4})
а если зафиксирован будет x3 так максимальный поток получится 101 и минимальный разрез (S={x3}, T={x1,x2,x3})
  #7  
Старый 24.05.2010, 01:57
Пользователь

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

ответ правилен , спасибо!
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Максимальный поток гость Графы 8 22.07.2009 11:28
максимальный поток гость Графы 7 29.04.2009 11:22
Максимальный поток гость Графы 1 31.08.2008 06:45
максимальный поток в графе с использованием параллельных вычислений kernel1987 Графы 0 19.04.2008 21:22
Максимальный поток MrFandorin Графы 3 14.04.2008 13:53