(2)

При виконанні даної контрольної роботи, для пошуку максимального покриваючого дерева мною було використано два алгоритми:

1. Оптимальний алгоритм – алгоритм Прима (або «жадібний алгоритм»);

2. Наближений алгоритм – алгоритм прямого перебору.

2. Оптимальний алгоритм

«Жадібний алгоритм» спеціально розроблено для вирішення завдань пошуку оптимальних покриваючих дерев. Назва алгоритму походить від особливості вибору ребер на кожній ітерації алгоритму, а саме: завжди вибирається ребро з максимальною вагою.

Для опису жадібного алгоритму заздалегідь вводяться в розгляд дві множини вершин: _– множина сполучених покриваючим деревом вершин початкового графа і – множина не сполучених покриваючим деревом вершин початкового графа. За визначенням: , , де множина вершин початкового графа . Множина ребер, що входять в максимальне покриваюче дерево, позначимо через .

Жадібний алгоритм має ітеративний характер і полягає у виконанні наступних дій (кроків):