Алгоритм Каркас-Рек
Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-1 ребро1) (N - количество вершин графа).
