 |
|
Приклад розв’язування.
Розглянемо мережу, яка складається з дев’яти населених пунктів (вершин), заданих їхніми декартовими координатами на площині.
| x | |||||||||
| y |
Перший етап. Розрахуємо матрицю відстаней між вершинами, використовуючи формулу (1).
Перш за все врахуємо, що d11 = d22 = d33 = … = d99 = 0. Крім того, слід мати на увазі, що матриця відстаней – симетрична. Отже, нам необхідно вирахувати 9*8/2 = 36 відстаней.
;
;
;
. . . . . . .
.
В результаті виконаних розрахунків отримуємо матрицю відстаней у вигляді:
| 31.4 | 42.0 | 9.1 | 24.2 | 31.3 | 15.2 | 12.2 | 23.3 | ||
| 14.8 | 22.4 | 24.8 | 14.0 | 17.0 | 28.3 | 19.2 | |||
| 33.6 | 26.2 | 28.2 | 26.8 | 41.8 | 22.0 | ||||
| 20.2 | 23.3 | 7.1 | 11.2 | 17.5 | |||||
| 35.0 | 15.1 | 31.4 | 5.7 | ||||||
| 21.9 | 23.0 | 29.5 | |||||||
| 17.5 | 11.2 | ||||||||
| 28.5 | |||||||||
Другий етап.Застосовуємо алгоритм Пріма – Краскала.
1. Вибираємо ще не розглянуте ребро мінімальної довжини. У нашому випадку це ребро d(5,9)= 5,7 . Обводимо кружечком дане число у матриці відстаней (помічаємо розглянуте ребро). Сполучаємо на схемі відповідні вершини
2. Вибираємо ще не розглянуте ребро мінімальної довжини. d(4,7) = 7,1 (цикл не утв.)
3. Вибираємо не розглянуте ребро мінімальної довжини. d(1,4) = 9,1 (цикл не утв.)
4. Далі маємо два ребра мінімальної довжини. d(4,8) = d(7,9) = 11,2 (цикл не утв.)
5. Ребро d(1,8) = 12,2 утв. цикл тому його не розгл.
6. Далі йдуть ребра d(2,6) = 14,0, d(2,3) = 14,8 (цикл не утв.)
7. Ребро d(1,7) = 15,2 утв. Цикл, тому вибираємо Ребро d(2,7) = 17,0.
Оскільки ми з’єднали всі вершини то процедура завершена і ми отримаємо мінімальне покриваюче дерево для розглядуваного графа, або, іншими словами, найдешевшу дорожну мережу для даної системи населених пунктів. Мережа має вигляд, представлений на наступному Рисунку 7.
|
Рис.7. Схема найкоротшої дорожної мережі.
Висновок. Побудована найкоротша дорожна мережа загальною довжиною 90.1 кілометра.