Page 113 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

дороги l , що їх з’єднує. Потрібно побудувати саму дешеву (най-
ij

коротшу) з усіх можливих транспортних мереж.

На перший погляд задача аналогічна попередній, однак сут-

тєвою відмінністю є те, що тут немає потреби у замкнутості

мережі (деревоподібний граф), а отже до міста може вести й

тільки одна дорога. Замість мережі доріг можна розглядати ме-

режу лiнiй електропередач, трубопроводів, комунікаційні мережі

тощо.

Зіставивши у графі, який зображає мережу дорiг, з величи-

ною вартості l довжину ребра d , приходимо до задачі про по-
ij
ij
будову найкоротшого графа – покривного дерева найменшої

довжини. Отже, надалі під вартістю доріг матимемо на увазі до-

вжину ребер графа.

Наприклад, якщо маємо всього три вершини (а, b, с), то достатньо

побудувати один із трьох з’єднуючих ланцюгiв аbс, асb, bас, причому якщо

bс - найдовше ребро, то саме його i потрiбно виключити, побудувавши ла-

нцюг bас.

Для більшої кількості вершин граф найменшої довжини мо-

жна побудувати, за наступним правилом:

16
15
Алгоритм Пріма – Крускала (Краскала)
1) З’єднуємо дві вершини з найбільш коротким ребром u 1.

15
Роберт Прим (англ. Robert Clay Prim, *25 вересня, 1921, Техас) — американський
математик та спеціаліст в галузі комп'ютерних наук.
16
Джозеф Крускал, (англ. Joseph Bernard Kruskal, Jr., *29 січня, 1928 — †19 вересня,
2010) — американський математик, спеціаліст в області статистики та комп'ютерних
наук.

112