вычисление избыточного потока и переполнение в алгоритме максимального потока

Question

Я читаю алгоритмы push-потока по следующей ссылке.

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel

Отмечено, что Избыточный поток - Определим избыток е потока, как е (и) = F (V, и), чистый поток в и. Вершина u ε V- {s, t} переполнена/активна, если e (u)> 0.

Я ищу пример с простой сетью потока, как мы вычисляем e (u)?

Спасибо за ваше время и помощь.

Answer 1

На приведенной ниже диаграмме имеется узел-источник (S), узел-приемник (T) и внутренний узел (A).

Цифры дают поток (скажем, в литрах в секунду). Есть 3 литров в секунду Ввод, но только 1 литр в секунду, оставляя, таким образом, избыточный поток для А равно 2.

Примечание

1. В алгоритме нажимной переобозначим, избыточный поток для внутренние узлы не могут быть отрицательными. Другими словами, вам не разрешено больше покидать поток, чем поступать.

2. Узел источника является позволило сформировать поток (это не считается как внутренний узел так, примечание 1 не применяется)

3. В ходе алгоритма, избыточный поток не уменьшается до тех пор, в конце концов все вершины имеют избыточный поток

4. Вы можете вычислить избыточный поток, суммируя весь входящий поток и вычитая весь исходящий поток.

5. Однако на практике алгоритм поддерживает массив избыточных потоков и обновляет значение по мере продвижения алгоритма.