Задача о многополюсном максимальном потоке

Многие обобщения задачи о максимальном потоке сводятся, по существу, к поиску максимального потока в сети, к легко осуществимому поиску некоторых цепей сети. Примером одной из таких задач является задача о потоке в сети с несколькими источниками и стоками, когда заданы мощности источников и возможности (спрос) стоков. В данной задаче множество всех узлов Vразбивается на подмножества источников S = {s,,s2, промежуточных узлов R = {t,r2, и стоков Т = [}t2,

На рис. 9.3 показано, как преобразование задачи о максимальном потоке в сети с несколькими источниками и несколькими стоками легко сводится к задаче с одним источником и одним стоком. Для этого добавляются фиктивный источник s и ориентированные ребра (s, sf) с пропускной способностью с(5,5, ) = оо для каждого i = 1, 2,..., т. Точно так же создается новый фиктивный сток t и добавляются ориентированные ребра (i,, t) с пропускной способностью c(tj,t) = oo для каждого i = 1, 2, ..., п. Единственный источник s обеспечивает поток любого требуемого объема к источникам 5,, а единственный сток t аналогичным образом потребляет поток любого желаемого объема от множественных стоков tf.

Таким образом, задача о многополюсном максимальном потоке сведена к задаче с одним источником и одним стоком.

Сведение задачи о многополюсном максимальном потоке к задаче с одним источником и одним стоком

Рис. 93. Сведение задачи о многополюсном максимальном потоке к задаче с одним источником и одним стоком

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >