Свойства минимального связующего дерева (MST)
Для связного и неориентированного графа остовным деревом этого графа является подграф, который является деревом и соединяет все вершины вместе. Один граф может иметь несколько остовных деревьев. Минимальное остовное дерево (MST) или остовное дерево с минимальным весом для взвешенного связного неориентированного графа — это остовное дерево, имеющее вес, меньший или равный весу любого другого возможного остовного дерева. Вес остовного дерева — это сумма весов, присвоенных каждому ребру остовного дерева.
Необходимые условия для минимального связующего дерева:
- Он не должен образовывать цикл, т. е. ни одно ребро не проходится дважды.
- Не должно быть другого остовного дерева с меньшим весом.
В этой статье мы обсудим свойства MST :
Возможная кратность :
Если G(V, E) — граф, то каждое остовное дерево графа G состоит из (V — 1) ребер, где V — количество вершин в графе, а E — количество ребер в графе. Таким образом, ребра (E – V + 1) не являются частью остовного дерева. Минимальных остовных деревьев одного веса может быть несколько. Если все веса ребер графа одинаковы, то каждое остовное дерево этого графа минимально.
Рассмотрим полный граф из трех вершин, и все веса ребер одинаковы, тогда возможны три остовных дерева (которые также минимальны) с одинаковой длиной пути. Ниже приведено изображение, иллюстрирующее то же самое:
Каждое из остовных деревьев имеет одинаковый вес, равный 2 .
Вырезать свойство :
Для любого разреза C графа, если вес ребра E в наборе разрезов графа C строго меньше весов всех остальных ребер набора разрезов графа C , то это ребро принадлежит всем MST множества C . график. Ниже приведено изображение, иллюстрирующее то же самое:
Свойство цикла :
Для любого цикла C в графе, если вес ребра E из C больше индивидуальных весов всех других ребер C , то это ребро не может принадлежать MST . На приведенном выше рисунке в цикле ABD ребро BD не может присутствовать ни в одном минимальном остовном дереве, поскольку оно имеет наибольший вес среди всех ребер цикла.
Уникальность :
Если каждое ребро имеет свой вес, то будет только одно, т. е. уникальное минимальное остовное дерево.
Подграф минимальной стоимости
Для всех возможных остовных деревьев минимальное остовное дерево должно иметь минимально возможный вес. Однако может существовать еще несколько остовов с тем же весом, что и минимальное остовное дерево, и все они также могут рассматриваться как минимальное остовное дерево.
- Ребро минимальной стоимости: если ребро минимальной стоимости графа уникально, то это ребро включается в любой MST. Например, на приведенном выше рисунке ребро AB (наименьшего веса) всегда включено в MST.
- Если к остовному дереву добавить новое ребро, то оно станет циклическим, поскольку каждое остовное дерево минимально ациклично. На приведенном выше рисунке, если к результирующему MST добавить ребро AD или BC , то получится цикл.
- Остовное дерево минимально связно, т. е. если из остовного дерева удалить какое-либо ребро, граф разъединится. На приведенном выше рисунке, если удалить какое-либо ребро из результирующего MST, это приведет к отключению графа.
Алгоритмы поиска минимального остовного дерева (MST): -
- Алгоритм Прима
- Алгоритм Крускала