lign="justify"> Структура мережі, оптимізована за критерієм довжини ліній, називається кратчайшесвязной мережею. У цьому випадку вважається заданим число кінцевих пунктів, їх місце розташування і відстань між ними. Потрібен з'єднати ці пункти таким чином, щоб сумарна довжина ліній була мінімальною. p align="justify"> Для побудови кратчайшесвязной мережі і розрахунку загальної довжини мережі складемо матрицю відстаней L, побудуємо за алгоритмом Прима кратчайшесвязную мережу і знайдемо її довжину шляхом додавання довжин між вузлами.
Таблиця 1.2 - Матриця відстаней між вузлами
Мінімальним елементом матриці є елемент l6, 5 = l5, 6 = 3,162.
Відповідно до алгоритму Прима виписуємо п'яту та шосту рядки, викресливши п'ятий і шостий стовпці (таблиця 1.3).
Таблиця 1.3
Формуємо з цих рядків допоміжну рядок, записуючи в кожному її стовпці найменший з двох елементів стовпця попередньої таблиці (таблиця 1.4).
Таблиця 1.4
12347891012,083 (6) 7,616 (6) 11,045 (6) 5,831 (6) 6,708 (5) 5,831 (6) 11,402 (6) 9,487 (6)
Цифрою в дужках вказується, з якого рядка узятий той чи інший елемент
Мінімальний елемент першої допоміжної рядка l4, 6 = l6, 4 = 5.831.
З урахуванням цього виписуємо першу допоміжну рядок і четвертий рядок матриці, попередньо викресливши з неї п'ятий, шостий і четвертий стовпці (таблиця 1.5).
Таблиця 1.5
1237891012,083 (6) 7,616 (6) 11,045 (6) 6,708 (5) 5,831 (6) 11,402 (6) 9,487 (6) 410,0006,3256,32512,36911,66217, 08814,422 Формуємо другу допоміжну рядок (таблиця 1.6)
Таблиця 1.6
1237891010,000 (4) 6,325 (4) 6,325 (4) 6,708 (5) 5,831 (6) 11,402 (6) 9,487 (6)
Мінімальний елемент l8, 6 = l6, 8 = 5.831.
Продовжуючи аналогічним чином, отримаємо інші гілки кратчайшесвязной мережі.
Таблиця 1.7
123791010,000 (4) 6,325 (4) 6,325 (4) 6,708 (5) 11,402 (6) 9,487 (6) 816,12512,00016,4923,6066,0006,325
Таблиця 1.8
123791010,000 (4) 6,325 (4) 6,325 (4) 3,606 (8) 6,000 (8) 6,325 (8)
Мінімальний елемент l7, 8 = l8, 7 = 3.606.
Таблиця 1.9
12391010,000 (4) 6,325 (4) 6,325 (4) 6,000 (8) 6,325 (8) 718,68214,31818,0285,0009,849
Таблиця 1.10
+12391010,000 (4) 6,325 (4) 6,325 (4) 5,000 (7) 6,325 (8) Мінімальний елемент l9, 7 = l7, 9 = 5,000.
Таблиця 1.11
