Для графа найдите остов максимального веса. Отрезки:1 2 равно 2; 3 4 равно 8; 1 5 равно 5; 2 3 равно минус 1; 1 4 равно 2; 2 7 равно 6; 3 7 равно 0; 3 6 равно 5; 4 5 равно 3; 5 6 равно 7; 6 7 равно 1.

Воспользуемся, например, алгоритмом Прима поиска минимального остова: на каждом шаге алгоритма минимальное остовное дерево достраивается следующим образом к множеству ребер уже построенного дерева добавляется ребро минимального веса, один конец которого находится в дереве V_T , а второй в множестве вершин, не входящих в дерево.

Чтобы применить алгоритм, меняем знаки ребер на противоположные:

На на...