Элементы комбинаторики. Правила умножения и сложения (стр. 5 из 5)
- для любой дуги eiвыполнено условие 0≤φ≤с(ei)
т.е. для любой дуги допустимый поток не превышает её пропускной способности.
2. для любой промежуточной величины выполнено условие баланса (условие сохранения потока): сумма потоков, втекающих в вершину, равна сумме вытекающих потоков, т.е. в промежуточных вершинах потоки не создаются и не исчезают.
Величина
называется остаточной пропускной способностью дуги.Дуга ei называется насыщенной, если
(если допустимый поток равен пропускной способностью)Суммарный поток, вытекающий из источника, равен суммарному потоку, втекающему в сток. Этот поток будем называть потоком в сети.
27. Полный и максимальный потоки в сети.
Поток называется полным, если путь из источника в сток содержит хотя бы одну насыщенную дугу.
Поток называется максимальным, если он принимает максимальное значение по сравнению с остальными потоками в сети.