Мінімальна кістяк (або мінімальне покриває дерево) у зв'язаному, зваженому, неорієнтованому графі - це кістяк цього графа, що має мінімальний можливий вага, де під вагою дерева розуміється сума ваг входять до нього ребер.
Алгоритм побудови мінімального остовного дерева передбачає з'єднання всіх вершин мережі за допомогою шляхів найменшої довжини. Типовою завданням, для вирішення якої необхідний такий алгоритм, є створення (проектування) мережі доріг з твердим покриттям, що з'єднують населені пункти в сільській місцевості, де дороги, що з'єднують два будь-яких пункту, можуть проходити через інші населені пункти. Найбільш економічний проект дорожньої системи повинен мінімізувати загальну довжину доріг з твердим покриттям, при цьому бажаний результат можна отримати за допомогою алгоритму побудови мінімального остовного дерева.
Розглянемо загальну схему роботи алгоритмів побудови мінімального остовного дерева з використанням жадібної стратегії. Отже, нехай дано зв'язний неорієнтований граф G (V; E) c n вершинами і вагова функція w. E → R.
Шуканий остов будується поступово. Алгоритм використовує певний ациклический підграф А вихідного графа G. який називається проміжним остовне лісом. Спочатку G складається з n вершин-компонент, не поєднаних між собою (n дерев з однієї вершини). На кожному кроці в A додається одне нове ребро. Граф A завжди є подграфом деякого мінімального кістяка. Чергове додається ребро e = (u. V) вибирається так, щоб не порушити цієї властивості: A ∪ e> теж має бути подграфом мінімального. Таке ребро називається безпечним.
Опишемо процедуру виконання цього алгоритму. Позначимо через N = безліч вузлів мережі і введемо нові позначення:
Телевізійна компанія планує підключення до своєї кабельної мережі п'яти нових районів. На рис. 6.4 показана структура планованої мережі і відстані (в милях) між районами і телецентром. Необхідно спланувати найбільш економічну кабельну мережу.
Щоб почати виконання алгоритму побудови мінімального остовного дерева, виберемо вузол 1 (або будь-який інший вузол). тоді
Послідовні ітерації виконання алгоритму представлені на рис. 6.5. Тут тонкими лініями показані ребра, що з'єднують вузли, що належать множинам. серед яких шукається ребро з мінімальною вартістю (довжиною). Це знайдене ребро показано пунктирною лінією. Товстими суцільними лініями позначені ребра, що з'єднують вузли безлічі Ск (і які раніше позначалися пунктирними лініями).
Наприклад, на першій ітерації ребро (1,2) має найменшу вартість (тобто найменша відстань між пунктами мережі) серед всіх інших ребер, що з'єднують вузол 1 з вузлами множини. (Відзначимо, що вузол 6 не має ребра, безпосередньо з'єднує його з вузлом 1).
Рішення у вигляді мінімального остовного дерева отримано на 6-й ітерації (рис. 6.5).
Мінімальна довжина кабелю для побудови такої мережі дорівнює 1 + 3 4 4 + + 3 + 5 = 16 миль.
Тема 10. Задача знаходження найкоротшого шляху
Завдання знаходження найкоротшого шляху:
Визначення в транспортній мережі найкоротшого шляху між заданим вихідним пунктом і пунктом призначення. Таку модель можна використовувати для опису різноманітних ситуацій, як показано в наступних прикладах.
Практичні приклади завдання знаходження найкоротшого шляху.
Завдання можна сформулювати як мережеву з п'ятьма вузлами з номерами від 1 до 5,
Вартості дуг рівні вартостям заміни автомобілів. Рішення завдання еквівалентно знаходженню найкоротшого шляху між вузлами 1 і 5.
Приклад 2: Найнадійніший маршрут
М-р Розумник щодня їздить на роботу на автомобілі. Закінчивши свого часу повний курс по теорії дослідження операцій, він легко визначив найкоротший шлях від будинку до роботи. На жаль, даний маршрут посилено патрулюється нарядами поліції, і автомобіль Разумника часто зупиняють за перевищення швидкості (як йому здається, не обгрунтовано). Таким чином, найкоротший шлях виявився не найшвидшим. Тому м-р Розумник планує розробити новий маршрут, на якому він мав би найвищу вірогідність не бути зупиненим поліцією.
Схема мережі доріг, по якій м-р Розумник може дістатися від дому до роботи, показана на рис. 6.10. На цій же схемі наведені імовірності не бути зупиненим для кожного сегмента мережі доріг. Імовірність же не бути зупиненим на всьому шляху проходження автомобіля Разумника дорівнює добутку ймовірностей бути зупиненим на кожному сегменті обраного шляху. Наприклад, вірогідність не бути зупиненим на маршруті
1 »3» 5 »7 дорівнює 0,9 х 0,3 х 0,25 = 0,0675.