7.3.2. Пример.

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

Рис. 8.9а. Граф из примера 7.3.2.

Рис. 8.9б. Граф из примера 7.3.2.

Путь с наибольшей надежностью в графе показан на на рис. 8.8 жирными линиями. Здесь следовательно, приведенная пропускная способность этого пути равна Удаляя из все дуги с пропускными способностями 10, получим графв, изображенный на рис. 8.9а. Путь с наибольшей надежностью в графе показан на рисунке жирными линиями. Для этого пути значит, приведенная пропускная способность пути равна что больше полученной ранее величины (5,04) и, следовательно, заменяет ее. Удаляя из все дуги с пропускной способностью 14, получаем граф изображенный на рис. 8.96. В этом графе существует только один путь между следовательно, приведенная пропускная способность равна 2,12, что хуже, чем лучшее предыдущее значение этой величины. Удаляя все дуги с пропускной способностью 15 из мы разъединим вершины так что лучший предыдущий ответ, т. е. путь с приведенной пропускной способностью 6,36 будет оптимальным ответом.

8. Задачи

(см. скан)

(кликните для просмотра скана)

(см. скан)

(см. скан)

9. Список литературы

(см. скан)

(см. скан)

(см. скан)