3.3. Родственные задачи

До сих пор мы занимались задачей нахождения SST и в связи с этим привели описание двух алгоритмов, которые можно использовать для решения этой задачи. Применимость этих методов, однако, значительно шире, чем кажется с первого взгляда. Операция на которую опираются эти методы, не накладывает никаких ограничений на знак веса и, следовательно, описанные методы построения SST применимы также для графов с произвольными (положительными, отрицательными или нулевыми) весами ребер. Отсюда немедленно вытекает, что длиннейшее остовное дерево графа можно найти таким же способом, надо лишь изменить знаки весов ребер на противоположные и применить затем один из приведенных выше алгоритмов построения SST.

Более того, при доказательстве утверждения, связанного с операцией не используется тот факт, что полный вес остовного дерева равен сумме весов его ребер. Предполагалось только, что при замене ребра с весом С на ребро с весом вес дерева уменьшается.

Таким образом, если вес дерева представляет собой монотонно возрастающую симметричную функцию, зависящую от реберных весов, то остовное дерево, минимизирующее эту весовую функцию, должно быть тем же самым SST (которое минимизирует сумму весов ребер). Например, если стоимости ребер графа остовным деревом графа минимизирующим или где — веса каких-либо ребер, образующих остовное дерево графа будет то же самое SST графа Добавим, что поскольку

в первой из упомянутых выше функций третью степень можно заменить на любую другую степень и поскольку при

то остовное дерево, у которого ребро с наибольшим весом имеет минимально возможный вес, совпадает с SST графа