3. Простые варианты задачи о максимальном потоке (от s к t)

Мы дадим теперь ряд задач, связанных с потоками, которые просто сводятся к задаче о максимальном потоке (от рассмотренной выше.

3.1. Графы со многими источниками и стоками

Рассмотрим граф с источниками и стоками и предположим, что поток может идти от любого источника к любому стоку. Задачу нахождения максимального общего потока от всех источников ко всем стокам можно преобразовать в простую задачу о максимальном потоке (от путем добавления нового искусственного источника и нового искусственного стока с добавлением дуг, ведущих от к каждому истинному источнику и от каждого истинного стока к

На рис. 11.5 показано, как множество источников и стоков может быть сведено к единственному источнику и единственному стоку. Пропускные способности дуг, ведущих от к источникам, могут быть выбраны равными бесконечности или в случае, когда производительность источника ограничена, пропускная способность соответствующей дуги может быть выбрана равной этой границе. Точно так же пропускные способности дуг, ведущих

стоков к могут быть ограничены некоторой величиной (зависящей от стоков) или положены равными бесконечности, если такой границы нет.

Если в задаче некоторые стоки должны снабжаться только определенными источниками и наоборот, то она уже не будет простой разновидностью задачи о максимальном потоке (от в становится задачей о многопродуктовом потоке.

Рис. 11.5.

Эта задача упоминалась во введении (см. задачу (III)).