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