Пропускная способность дуги ограничена для суммы всех видов продуктов через эту дугу
Потоки в сетях.
Варианты задач:
1) Пусть каждой дуге графа приписана не только пропускная способность 
, - верхняя граница потока через дугу ( 
) по так же 
- нижнюю границу потока через дугу Если задать стоимость единицы потока , протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости (от s и t).
2) Ищутся max потоки между каждой паройвершин. Она может быть решена как
« отдельных » от s и t задач, но это трудоёмкий процесс. При нахождении
путей между каждой парой вершин графа не обязательно решать каждую задачу индивидуально .
3)Если вместо 1 источника и 1 стока рассмотреть несколько источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то имеем задачу с многопродуктовым потоком.
Пропускная способность дуги (
) ограничена для суммы всех видов продуктов через эту дугу.
4) Если исходить оттого, что поток на входе = потоку на выходе, то выходит поток дуги
= входному потоку, умноженному на некоторое неотрицательное число, то получим задачу о потоках с «выигрышами». В такой задаче потоки могут и « порождаемые» и «погашаемые» самим графом, а поток, входящий в S и потом покидающий t, могут изменяться совершенно независимо.