(2)
При виконанні даної контрольної роботи, для пошуку максимального покриваючого дерева мною було використано два алгоритми:
1. Оптимальний алгоритм – алгоритм Прима (або «жадібний алгоритм»);
2. Наближений алгоритм – алгоритм прямого перебору.
2. Оптимальний алгоритм
«Жадібний алгоритм» спеціально розроблено для вирішення завдань пошуку оптимальних покриваючих дерев. Назва алгоритму походить від особливості вибору ребер на кожній ітерації алгоритму, а саме: завжди вибирається ребро з максимальною вагою.
Для опису жадібного алгоритму заздалегідь вводяться в розгляд дві множини вершин: – множина сполучених покриваючим деревом вершин початкового графа і – множина не сполучених покриваючим деревом вершин початкового графа. За визначенням: , , де множина вершин початкового графа . Множина ребер, що входять в максимальне покриваюче дерево, позначимо через .
Жадібний алгоритм має ітеративний характер і полягає у виконанні наступних дій (кроків):