Page 89 - 2589

Так як для шляху  виконується умова  n  l ( 0 ) то шлях
0

 є найкоротшим.
0
Приклад 4.6: Знаходження найкоротшого шляху
продемонстрований на прикладі карти доріг, представленої у
вигляді графа на рис.4.8.

Рисунок 4.8 – Приклад графа «Карта доріг»
Цифри у ребер вказують час проїзду по кожній з доріг.

Індекси вершин. дають час проїзду від цієї вершини до кінцевої.

5.7.4 Побудова графа найменшої довжини

Практичне застосування має наступне завдання, яке можна
сформулювати у вигляді завдання про проведення доріг. Є
декілька міст a,b,c…, які треба з'єднати між собою мережею

доріг. Для кожної пари міст ( yx , ) відома вартість ( yxl , )
будівництва дороги між ними. Завдання полягає в тому, щоб
побудувати найдешевшу з можливих мереж доріг. Замість мережі

доріг можна розглядати мережу ліній електропередачі, мережу
нафтопроводів і т. п. Називаючи в графі, що зображує мережу

доріг, величину ( yxl , ) довжиною ребра ( yx , ) приходимо до

завдання про побудову графа найменшої довжини. Тому далі
замість вартості доріг розглядатимемо довжину ребер графа.

Якщо є всього три вершини a,b,c, то достатньо побудувати
один із сполучаючих ланцюгів abc, acb, bac, причому якщо bc -
найдовше ребро, то саме його і потрібно виключити,

побудувавши ланцюг bac.
Граф найменшої довжини завжди є деревом, так якщо б він
містив цикл, можна було б видалити одно з ребер цього циклу і
вершини все ще залишились би сполученими. Отже, для

89