Алгоритм Форда-Фалкерсона (макс. поток в транспортной сети)

[new_sergei]

Здравствуйте

Мне необходимо построить максимальный поток и разрез с минимальной пропускной способностью в транспортной сети, приведённой на рисунке, по алгоритму Форда-Фалкерсона.



Беда в том, что толковой литературы под рукой по этому вопросу нет. Интернетные источники (самые популярные на эту тему) я тоже смотрел. Но понять так ничего и не смог.
Подскажите, пожалуйста, толковую книгу в сети по данному вопросу (или (если можно), распишите, пожалуйста, по шагам, что именно надо сделать для решения задачи).

[Maslov]

Вот тут посмотрите: Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: Построение и анализ. (стр. 742)

[new_sergei]

После изучения аналогичных примеров у меня получилось следующее.

Шаг 1. $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGimaaaa!3979! \[ \varphi = 0 \] $

Шаг 2. Рассмотрим путь S-A-B-T. Можем увеличить поток на величину 1,1.
Тогда $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGimaiabgUcaRiaaigdacaGGSaGaaGymaiabg2da9iaaigda % caGGSaGaaGymaaaa!3FAD! \[ \varphi = 0 + 1,1 = 1,1 \] $
Дуга B-T становится насыщенной



Шаг 3. Рассмотрим путь S-D-T. Можем увеличить поток на величину 3,2.
Тогда поток $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGymaiaacYcacaaIXaGaey4kaSIaaG4maiaacYcacaaIYaGa % eyypa0JaaGinaiaacYcacaaIZaaaaa!4121! \[ \varphi = 1,1 + 3,2 = 4,3 \] $
Дуга S-D насыщена



Шаг 4. Рассмотрим путь S-C-T. Можем увеличить поток на величину 2,2.
Тогда поток $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGinaiaacYcacaaIZaGaey4kaSIaaGOmaiaacYcacaaIYaGa % eyypa0JaaGOnaiaacYcacaaI1aaaaa!4129! \[ \varphi = 4,3 + 2,2 = 6,5 \] $
Дуга S-C насыщена


Шаг 5. Рассмотрим путь S-A-B-D-T. Можем увеличить поток на величину $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciyBaiaacM % gacaGGUbWaaeWaaeaacaaI1aGaaiilaiaaikdacqGHsislcaaIXaGa % aiilaiaaigdacaGG7aGaaGynaiaacYcacaaIYaGaeyOeI0IaaGymai % aacYcacaaIXaGaai4oaiaaikdacaGGSaGaaGymaiaacUdacaaI1aGa % aiilaiaaiodacqGHsislcaaIZaGaaiilaiaaikdaaiaawIcacaGLPa % aacqGH9aqpcaaIYaGaaiilaiaaigdaaaa!5197! \[ \min \left( {5,2 - 1,1;5,2 - 1,1;2,1;5,3 - 3,2} \right) = 2,1 \] $
Тогда поток $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGOnaiaacYcacaaI1aGaey4kaSIaaGOmaiaacYcacaaIXaGa % eyypa0JaaGioaiaacYcacaaI2aaaaa!412F! \[ \varphi = 6,5 + 2,1 = 8,6 \] $
Дуги B-D, D-T насыщены


Шаг 6. Рассмотрим путь S-A-C-T. Можем увеличить поток на величину $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaciyBaiaacM % gacaGGUbWaaeWaaeaacaaI1aGaaiilaiaaikdacqGHsislcaaIZaGa % aiilaiaaikdacaGG7aGaaGymaiaacYcacaaIXaGaai4oaiaaiodaca % GGSaGaaGOmaiabgkHiTiaaikdacaGGSaGaaGOmaaGaayjkaiaawMca % aiabg2da9iaaigdacaGGSaGaaGimaaaa!4B96! \[ \min \left( {5,2 - 3,2;1,1;3,2 - 2,2} \right) = 1,0 \] $
Тогда поток $% MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqy1dOMaey % ypa0JaaGioaiaacYcacaaI2aGaey4kaSIaaGymaiaacYcacaaIWaGa % eyypa0JaaGyoaiaacYcacaaI2aaaaa!4131! \[ \varphi = 8,6 + 1,0 = 9,6 \] $
Дуга C-T становится насыщенной.



Т.о., больше не существует путей из S в T.
Значит максимальный поток равен 9,6.

Верны ли мои рассуждения?

В задании сказано, что надо найти ещё разрез с минимальной пропускной способностью. Как найти этот разрез?

[Maslov]

Рассуждения Ваши верные, только алгоритм Форда-Фолкерсона предполагает явное построение на каждом шаге остаточной сети.
Ну а разрез с минимальной пропускной способностью -- это просто разрез, пропускная способность дуг которого даёт в сумме пропускную способность сети.

[new_sergei]

Спасибо за ответ.
Я только не совсем понял про разрез с минимальной пропускной способностью. В данном случае это будут какие дуги?

[Maslov]

Максимальный поток равен 9.6, поэтому минимальный разрез -- это разрез, проходящий через дуги BT, CT, DT.

[Sadovodd]

спасиб вам большое, мне очень помогло то что я нашел на этой странице