Оптимальные каркасы и пути

В задаче об оптимальном каркасе (она известна также как задача о кратчайшем остовном дереве) задан граф , каждому ребру которого приписано число, называемое весом ребра. Вес ребра будем обозначать через . Вес множества определяется как сумма весов составляющих его ребер. Требуется в графе G найти каркас минимального веса. Для решения этой задачи известно несколько алгоритмов. Рассмотрим два из них.