Задача мінімізації мережі полягає в знаходженні ребер, які з’єднують всі вузли мережі і мають мінімальну сумарну довжину. Розв’язок задачі не повинен містити циклів. Він представляє собою мінімальне дерево. Його знаходження починаємо з будь-якого вузла, який з’єднуємо з найближчим вузлом мережі. З’єднані два вузли утворюють зв’язну множину, а всі решта – незв’язну. Тепер в незв’язній множині вибираємо вузол, який знаходиться найближче до одного з них і з’єднуємо їх. Процес повторюємо доти, доки у зв’язну множину не попадуть всі вузли мережі.
Приклад 2.1. Телевізійна фірма планує створити кабельну мережу для обслуговування п’яти районів-новобудов. Числа на ребрах вказують довжину кабеля, який з’єднує відповідні вузли. Вузол 1 – це телевізійний центр, а решта (2–6) відповідають п’яти новобудовам. Відсутність ребра між двома вузлами означає, що з’єднати ці вузли неможливо ( рис. 2.5).
Рис. 2.5
Розв’язок. Зобразимо на рис 2.6 поетапну побудову мінімальної мережі:
1.
2.
3.
4.
5.
Рис.2.6.
Вузол 3 можна зв’язувати як з вузлом 1 так і з вузлом 4. Оскільки всі вузли зв’язані, то мінімальна довжина кабелю дорівнює 1+3+4+5+3=16.