Доказательство теоремы Форда-Фалкерсона через усиление

leshij76

Оно находится по ссылке.
http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%...
1. Не понимаю, откуда следует утверждение "Значит, существует направление (u,t) из S в T, что f(u,t) < c(u,t)" (когда доказываем 3->2).
2. Доказательств у теоремы несколько, но нужно понять именно это доказательство.
3. Буду благодарен ссылке на учебник или книгу с этим доказательством.

Vadim46

Не понимаю, откуда следует утверждение "Значит, существует направление (u,t) из S в T, что f(u,t) < c(u,t)" (когда доказываем 3->2).
Потому что величина потока равна сумме таких f(u,t)

leshij76

Почему? Ведь величина потока равна разнице суммы прямых потоков (направленных со стороны входного полюса к выходному) и суммы обратных потоков (направленных наоборот).

Vadim46

Ну да, для обратных потоков f(u,t) < 0

griz_a

Ну если его нет, то везде поток равен пропускной способности и предполагаемое неравенство (пропускная способность разреза больше потока по нему) не выполнено

leshij76


набросал на скорую руку. черные числа - кол-во инфрмации, проходящей по каналу, фиолетовые числа в кружочке - пропускная способность, красная кривая - разрез.
на рисунке поток равен 16, пропускная способность разреза - 18. 18>16. из-за того, что есть обратное ребро, по которому с выхода утекает 2, не дает неравенства 18>18 из ложности которого бы следовало, что существует прямое ребро с f(u,t)<c(u,t)
я что-то не так себе представляю?

Vadim46

у тебя есть обратное ребро, поток по которому (слева направо) равен -2, а пропускная способность (слева направо) — 0. В остаточной сети это ребро будет в "прямом" направлении.

Vadim46

короче, 10 + (-2) + 8 < 10 + 0 + 8
слева записаны потоки, справа — пропускные способности.
значит, есть поток, у которого соответствующая пропускная способность меньше
и действительно, -2 < 0 =)

Vadim46

:mad:

Vadim46

, почитай "Алгоритмы: построение и анализ", там, похоже, такое же доказательство.

leshij76

"Алгоритмы: построение и анализ", там, похоже, такое же доказательство
http://torrents.ru/forum/viewtopic.php?t=40367 - Эту?

Damrad

да

svetik5623190

см. книгу А. В. Чашкин "Лекции по дискретной математике".
может там и другое доказательство, но книга всё равно хороша.
Оставить комментарий
Имя или ник:
Комментарий: