Page 92 - 4496

Вибирається ребро, що має мінімальну вагу серед усіх
ребер, і включається в кістяк. З ребер, що залишилися,
вибирається знову те, яке має мінімальну вагу, і включається в
кістяк, якщо при цьому не утворюються цикли. Процес триває
доти, поки всі вершини не будуть включені в кістяк.
Алгоритм простий для розуміння й забезпечує
одержання мінімального розв'язку. Однак складність його
полягає в тому, що в ньому неявно є присутня процедура
перевірки на появу циклів, яка пов'язана з перебором по
всьому графі, так само як і пошук чергового ребра.
Пошук за цим алгоритмом у графі на рис. 3.15 приведе
до розв'язку, який представимо у вигляді послідовності
переглянутих ребер: (1,4), (3,5), (1,2), [(2,4)], (2,3), (5,7),
[(2,5)], [(4,5)], [(4,7)], (4,8), [(5,8)], [(7,8)], (3,6). У квадратні
дужки укладені ті ребра, які не включені в кістяк через появу
циклів.
Алгоритм Прима.
1. Включимо будь-яку вершину в кістяк.
2. Розглянемо всі ребра, що виходять із вершин,
включених у кістяк до вершин, що залишилися, і з них
виберемо ребро з мінімальною вагою. Його кінцеву вершину
включимо в кістяк. Повторюємо цей пункт, поки не всі
вершини будуть включені в кістяк.
У цьому алгоритмі не потрібно стежити за утворення
циклів. Алгоритм починає роботу з довільно обраної вершини.
Крім того, на кожному кроці проглядається тільки один рядок
матриці суміжності.
Завдання. Доведіть, що незалежно від вибору
початкової вершини виходить мінімальний розв'язок.
Якщо для графа на рис 3.15 алгоритм почати з вершини
7, то послідовність дій буде такою:
1. Вершину 7 віднесемо до кістяка.
2. Оцінимо ребра від вершини 7 до 4, 5 і 8. Виберемо
ребро з мінімальною вагою (7,5) і вершину 5 віднесемо до
кістяка.
2. Для вершин 5, 7 розглянемо ребра у вершини 1, 2, 3, 6,
8, 4 і по мінімальній вартості ребра віднесемо вершину 3 до
кістяка.
2. З вершин 5, 7, 3 ребра йдуть до вершин 1, 2, 4, 6, 8. По
найменшому із цих ребер у кістяк віднесемо вершину 2.
89