3.2. Графы с пропускными способностями дуг и вершин

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

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

Определим граф так, чтобы каждая вершина графа соответствовала двум вершинам в графе причем каждой дуге из инцидентной вершине соответствует дуга из инцидентная вершине и каждой дуге из исходящей из соответствует дуга из исходящая из Кроме того, введем дугу между с пропускной способностью т. е. равной пропускной способности вершины

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

Рис. 11.6. (см. скан) (а) Граф, вершинам и дугам которого приписаны пропускные способности (б) Эквивалентный граф, в котором пропускные способности имеют только дуги.

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