7.3. Путь с наибольшей приведенной пропускной способностью

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

В этом случае нельзя воспользоваться трехместной операцией так как не удается найти оператора который (для пути от через вершину удовлетворяет условию

Несуществование такого оператора можно обосновать следующим образом:

где запись а применяется как для пути от так и для множества дуг этого пути.

Вводя обозначения

можем записать

Следовательно,

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

Рис. 8.7.

На самом деле нетрудно показать, что оптимальный путь от через не зависит от:

(i) оптимальных путей от и от к х;

(ii) путей наибольшей пропускной способности от и от к х;

(iii) путей наибольшей надежности от и от или любой их комбинации.

В этом можно убедиться, рассматривая рис. 8.7, на котором изображены пути всех трех вышеуказанных типов от от причем оптимальное значение величины которое можно получить с помощью некоторой комбинации этих путей, равно 4,20. На рисунке изображены, кроме того, такие два пути от и от ни один из которых не является оптимальным в любом из трех вышеприведенных смыслах, между их соответствующими конечными вершинами. Однако эти два пути образуют оптимальный путь между вершинами которому отвечает значение величины равное 4,48.