Минимальные и максимальные остовные деревья

Остовное дерево связного неориентированного графа — это дерево, которое включает все вершины графа.
Минимальное остовное дерево (MST) — остовное дерево с минимально возможной суммой весов рёбер.
Аналогично, максимальное остовное дерево — остовное дерево с максимально возможной суммой весов рёбер.

Свойства минимального остовного дерева

Уникальность
Если все рёбра графа имеют различные веса, минимальное остовное дерево единственно.
Если же некоторые рёбра имеют одинаковые веса, то возможно существование нескольких различных MST.
Минимизация произведения весов
Минимальное остовное дерево минимизирует не только сумму, но и произведение весов своих рёбер.
Это можно понять, если перейти к логарифмам весов: минимизация суммы логарифмов эквивалентна минимизации логарифма произведения.
Максимальное остовное дерево
Максимальное остовное дерево можно найти аналогично MST. Для этого достаточно изменить знак всех весов рёбер и применить любой алгоритм поиска минимального остовного дерева (например, алгоритм Крускала).