![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Приклад 3.1.
Побудувати найкоротше остовне дерево для мережі, граф якої приведено на рис. 3.1.
Рисунок 3.1. – Граф мережі
Запишемо по наведеному графу матрицю вартостей (табл.3.1). Табл. 3.1
Матриця вартостей
Вибираємо найменше значення Cij (в прикладі [1]), відмічаємо рядки i та j ( в прикладі знаком *), а стовпці i та j викреслюємо і в подільшому не розглядаємо (в прикладі беремо в дужки (4), (6)). Серед значень Cij, що входять в позначені рядки, вибираємо найменше, викреслюємо стовпець, в якому це найменше значення знаходиться, відмічаємо рядок з номером останнього викресленого стовпця і т.д. Алгоритм закінчує роботу, коли позначені всі рядки та викреслено всі стовпці. 1. S ={4, 6}
2. S ={4, 5, 6}
3. S ={4, 5, 6, 7}
4. S ={1, 4, 5, 6, 7}
5. S ={1, 3, 4, 5, 6, 7}
6. S ={1, 2, 3, 4, 5, 6, 7}
Довжина найкоротшого остовного дерева: L=1+2+2+3+2+3=13.
|