вершинами і цими дугами, становить у першому випадку 720 +
940 = 1660, у другому випадку 1140 + 770 = 1910 і в третьому
випадку 940 + 660 = 1600. Мінімальна сума із цих трьох −
остання. Її ми і запишемо над проміжною вершиною К і відзна-
чимо дугу БК, яка привела до цієї суми. Третя проміжна верши-
на має три дуги, що заходять у неї, і мінімальною із трьох відпо-
відних сум є 1460, а дугою, що привела до цієї суми, − ЄС.
Верхня кінцева вершина Є має три дуги, що заходять в неї.
Сума чисел, записаних над проміжною вершиною і дугою, що
з'єднує її з кінцевою вершиною Є, становить: 1270 + 1350 =
2620, 1600 + 1210 = 2810 і 1460 + 1300 = 2760. Найменша із цих
сум − перша. Тому над кінцевою вершиною Є запишемо число
2620, відзначимо дугу, що виходить із проміжної вершини ОК і
заходить у кінцеву вершину Є. Нижня кінцева вершина К має
дві дуги, що заходять у неї. Мінімальна сума із двох 1460 + 2350
= 3810 і тому це число записується над кінцевою вершиною К і
відзначається дуга СК.
Точно в такий же спосіб оцінюються за мінімумом три про-
міжні і дві кінцеві вершини і відзначаються дуги в зональному
графі західного крила (рис. 2.20).
Після запису перерахованих сум над початковими верши-
нами об'єднавчого графа оцінимо за мінімумом його кінцеві
вершини і відзначимо дуги (див. рис. 2.21).
Щоб знайти «найкоротший шлях», тобто технологічну
схему підземного транспорту, за умов якої експлуатаційні ви-
трати будуть найменшими, робимо це в такий спосіб: із трьох
сум, записаних над кінцевими вершинами об'єднального графа,
вибираємо найменшу, тобто суму 7790, записану над вершиною
Є. Відзначеною дугою, що заходить у неї, є верхня. Обведемо її
жирною лінією. Ця дуга привела нас до початкової вершини об'-
єднавчого графа Схід. – Є, Захід. – Є, а отже, до кінцевої верши-
ни Є зонального графа східного крила і кінцевій вершині Є зо-
нального графа західного крила.
65