Page 114 - 4204

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

2) На кожному з наступних кроків добавляємо саме коротке з ре-

бер u i, якщо при цьому не виходить циклу (рис. 8.3). Якщо трапляється

декілька ребер однакової довжини, то вибираємо будь-яке з них.

Сума довжин ребер такого графа буде найменшою:

Рисунок 8.3 До побудови графа найменшої довжини

Приклад. Задано координати х,у дев’яти населених пунктів (табл.

8.1). Необхідно:

а) розрахувати матрицю відстаней між пунктами мережі за форму-

лою відстані між двома точками по прямій

2
2
d  (x  x )  (y  y ) (8.1)
ij j i j i
(значення відстаней заокруглювати з точністю до десятих);

б) використовуючи матрицю відстаней, згідно з алгоритмом Пріма –

Краскала запроектувати найдешевшу дорожню мережу та побудувати

план дорожньої мережі, вказавши номери населених пунктів і довжини

з’єднуючих їх доріг. Вказати загальну довжину мережі.

Розв’язування. Розглянемо мережу, яка складається з дев’яти насе-

лених пунктів (вершин), заданих координатами на площині.

113