Для данного графа найдите остов максимального веса

Воспользуемся, например, алгоритмом Прима поиска минимального остова: на каждом шаге алгоритма минимальное остовное дерево достраивается следующим образом – к множеству ребер уже построенного дерева добавляется ребро минимального веса, один конец которого находится в дереве VT, а второй – в множестве вершин, не входящих в дерево.
Чтобы применить алгоритм, меняем знаки ребер на противоположные:
1-2 3-4 1-5 2-3 1-4 2-7 3-7 3-6 4-5 5-6 6-7
-2 -8 -5 1 -2 -6 0 -5 -3 -7 -1
На начальном этапе VT=∅ . Начнем строить минимальное дерево с вершины v1.
1. Выбираем инцидентное ребро минимального веса:
cv1;v5=-5
Таким образом:
VT=v1;v5;ET=v1;v5
2. Из ребер, инцидентных вершинам из множества VT=v1;v5 наименьший вес имеет ребро:
cv5;v6=-7
Таким образом:
VT=v1;v5;v6;ET=v1;v5,v5;v6
3