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

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

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

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

Помогите с алгоритмом Форда-Фалкерсона
Добрый день.
Не могли бы Вы, наиболее доступными средствами, разъяснить доказательство: величина максимального потока равна величине минимального разреза (чисто интуитивно это понятно), но прочитав в разных книгах, соответственно разные математические док-ва на данную тему, то складывается впечатление, что для автора чем ученее (непонятнее, по крайней мере мне), тем лучше.
Еще пара вопросов по данной теме:
-Как доказать, что поток из входного в выходное мн-во, собственно не зависит от выбора этих множеств. (на пальцах это понятно. "что вышло, то и вышло", конечно с учетом прохождения узлов без потерь)
-Как доказать следствие: для любого разреза и любого потока верно неравенство вида: мощность потока < or =
пропускной способности разреза.
Заранее благодарен всем откликнувшимся.
  #2  
Старый 04.04.2010, 18:16
Новичок

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

Доказательства этих фактов уже две недели как есть в википедии. Я написал.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с Волновым алгоритмом. Vasilevs Графы 1 20.04.2009 00:30
Помогите с Волновым алгоритмом. Vasilevs Математические алгоритмы (другое) 0 19.04.2009 22:43
Поиск минимального цикла через алгоритм Форда-Фалкерсона Amber66 Графы 6 20.06.2008 17:48
Помогите с алгоритмом Никто Вычислительная геометрия 2 30.12.2007 22:24
Помогите с алгоритмом гость Графы 4 09.08.2007 19:59