Постановка задачі та алгоритм синтезу мінимальної зірки

Оптимальна (мінімальна) зірка є окремим випадком остовного дерева, коли один вузол – центр зірки – безпосередньо зв’язан з кожним іншим вузлом. Для визначення центра мінімальної зірки, треба для кожного вузла обчислити сумарну довжину всіх дуг до інших вузлів, та вибрати мінімальне значення.

Приклад 3.2.

Для мережі (рис. 3.2) побудувати мінімальну зірку.

Рисунок 3.2 – Граф мережі

Додамо в матрицю вартостей рядок з сумою довжин дуг – отримаємо таблицю рішення (табл.3.2)

Табл. 3.2

Таблиця рішення

Таким чином оптимальною буде зірка з центром в вузлі 4.