6. Потоки в графах с выигрышами

До сих пор в этой главе делалось предположение, что поток, выходящий из дуги, является таким же, как и поток, входящий в дугу. Однако в ряде практических ситуаций это допущение не выполняется. Например, в трубопроводе, по которому перекачивается жидкость, или в электрической сети могут быть потери, уменьшающие поток по дуге. В системах транспортировки может происходить порча груза, которая также приводит к уменьшению потока по дуге, представляющей маршрут. В технологических процессах, которые могут быть изображены графами с дугами, соответствующими операциям, ценность материала, покидающего дугу, больше, чем ценность материала, входящего в дугу, так как в дуге имеется выигрыш, получаемый за счет «прибавочной стоимости» операции. В задачах обмена (например, при продаже и покупке валюты) выигрыши дуг представляют обменный курс входного потока (измеряемый в одной валюте) по отношению к выходному потоку (измеряемому в другой валюте).

В этом разделе мы рассмотрим задачу нахождения максимального потока (от s к t) в графе с произвольными неотрицательными выигрышами и пропускными способностями приписанными дугам графа Эта задача аналогична задаче о максимальном потоке (от к обсуждавшейся в разд. 2, хотя теперь входной

и выходной потоки связаны между собой только через «посредство» графа способного как «породить», так и «поглотить» поток.

Если через обозначить поток, входящий в дугу а через — поток, выходящий из этой дуги, то

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

независимо от величины Обозначим чистый входной поток в через а чистый выходной поток а) в через Поток является допустимым, если он удовлетворяет условию непрерывности потока во всех вершинах, т. е.

а также условиям (11.12) и (11.13) для каждой дуги из Введем теперь два определения.

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

Определение. Допустимый поток называется оптимальным, если для любого другого допустимого потока 3

где являются соответственно чистыми потоками в источнике и стоке потока

Эти последние условия согласуются с интуитивным пониманием оптимальности, а именно заданные являются или наибольшими, или наименьшими возможными.

Определение. Допустимый поток называется оптимально-максимальным, если он является как оптимальным, так и максимальным потоком.

Проиллюстрируем введенные понятия на примере. Рассмотрим граф на рис. 11.16 а, где первое число у дуги задает ее пропускную способность, а рторое — выигрыш. Тогда

Рис. 11.16. (см. скан) (а) Граф первая пометка — пропускная способность дуги, вторая — выигрыш дуги, (б) Максимальный поток, (в) Оптимальный поток, (г) Оптимально-максимальный поток.

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

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

поток не является максимальным, но представляет собой максимум, который может быть получен при поток, изображенный на рис. является оптимально-максимальным, имеющим как будет показано ниже, наименьшее возможное значение дающее выходной поток со значением 18, равно 5.