Алгоритм Форда Фулкерсона, увеличивающий поток - PullRequest
Новая
       31

Алгоритм Форда Фулкерсона, увеличивающий поток

0 голосов
/ 08 апреля 2019

Относительно алгоритма Ford Fulkerson с путем s-x-y-z-t мы должны были выяснить, как можно увеличить поток вдоль этого пути.

Проблема в том, чтоЯ не знаю, как получить значения в решении.
Может кто-нибудь объяснить?

enter image description here

1 Ответ

1 голос
/ 08 апреля 2019

Чтобы найти путь расширения в алгоритме Форда-Фулкерсона, нам нужно взглянуть на остаточный граф , который, по сути, позволяет нам

  • продолжайте добавлять поток по ненасыщенным краям или
  • удалить существующий поток с краев.

Похоже, ваш пример состоит из подграфа, поскольку вершины X, Y и Z нарушают сохранение потока (сумма входящих потоков должна быть равна нулю в каждой вершине).

В вашем примере мы можем

  • нажмите еще 7 вдоль края SX;
  • нажмите еще 4 вдоль края XY;
  • удалить 3 единицы с края YZ;
  • подтолкнуть еще 4 единицы вдоль края ZT.

Следовательно, мы можем выдвинуть не более 3 единиц из S в T, не нарушая каких-либо ограничений по емкости. Делая это, мы получаем потоковую сеть, описанную на вашем втором изображении.

...