Мінімізація мережі

Задача мінімізації мережі полягає в знаходженні ребер, які з’єднують всі вузли мережі і мають мінімальну сумарну довжину. Розв’язок задачі не повинен містити циклів. Він представляє собою мінімальне дерево. Його знаходження починаємо з будь-якого вузла, який з’єднуємо з найближчим вузлом мережі. З’єднані два вузли утворюють зв’язну множину, а всі решта – незв’язну. Тепер в незв’язній множині вибираємо вузол, який знаходиться найближче до одного з них і з’єднуємо їх. Процес повторюємо доти, доки у зв’язну множину не попадуть всі вузли мережі.

Приклад 2.1. Телевізійна фірма планує створити кабельну мережу для обслуговування п’яти районів-новобудов. Числа на ребрах вказують довжину кабеля, який з’єднує відповідні вузли. Вузол 1 – це телевізійний центр, а решта (2–6) відповідають п’яти новобудовам. Відсутність ребра між двома вузлами означає, що з’єднати ці вузли неможливо ( рис. 2.5).

Рис. 2.5

Розв’язок. Зобразимо на рис 2.6 поетапну побудову мінімальної мережі:

Рис.2.6.

Вузол 3 можна зв’язувати як з вузлом 1 так і з вузлом 4. Оскільки всі вузли зв’язані, то мінімальна довжина кабелю дорівнює 1+3+4+5+3=16.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Матричне представлення графів	\|	Задача про найкоротший шлях

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.016 сек.