Изменения

Остовное дерево минимально тогда и только тогда, когда любое ребро для любого ребра, не из дерева является максимальным на циклепринадлежащего остову, цикл, который образуется образуемый этим ребром при его добавлении в деревок остову, не содержит рёбер тяжелее этого ребра.

Теперь докажемДокажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}} минимально. Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребер на циклах, тогда оно не минимально.  Если <tex> A </tex> не минимально, то его можно улучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex>KA </tex>, удовлетворяющее условиюс помощью общего алгоритма построения MST. Докажем, минимальночто оно имеет минимальные ребра на каждом цикле. '''function''' Generic MST(<tex> G </tex>): <tex> A = \{ \} </tex> '''while''' <tex> A </tex> не является остовом '''do''' найти безопасное ребро <tex> ( u, v ) \in E </tex> для <tex> A </tex> <font color = darkgreen>// нужное ребро находится с помощью [[Лемма о безопасном ребре|леммы о безопасном ребре]] </font color = darkgreen> <tex> A = A \cup \{( u, v )\} </tex> '''return''' <tex> A </tex> Заметим, что дерево <tex> A </tex> состоит полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро. Теперь, рассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, причем <tex> u \in S </tex>, а <tex> v \in T </tex>. Найдем путь в изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то какое-нибудь ребро <tex> (a, b) \notin A</tex> тоже будет пересекать разрез <tex> (S, T) </tex>. Очевидно, что <tex> w(u, v) \leqslant w(a, b) </tex>, так как первое {{---}} безопасное ребро.  Следовательно, любое ребро не принадлежащее <tex> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.

|definition=Проверка уникальности Поиск минимального остовного дерева}}Построим минимальное остовное дерево(MST) используя [[алгоритм Краскала]]. Рассмотрим рёбра <tex>ab</tex> вне остова, посмотрим на максимальное ребро на пути <tex>ab</tex> внутри остова:*Если его вес совпадает с весом ребра <tex>ab</tex>, то заменив ребро из остова ребром вне остова, мы получим остов с точно таким же весом, а значит остов не уникален. *Если и проверка его вес больше ребра из остова, значит заменив рёбра мы получим остов с большим весом, этот случай не влияет на уникальность. *Так же его вес не может быть меньше ребра из остова, иначе мы построили не минимальный остов в начале алгоритма.Искать максимальное ребро на пути <tex>ab</tex> в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя [[Метод двоичного подъема]].Построим дополнительный массив <tex>D</tex>, при помощи массива двоичных подъёмов. В <tex>D[i][j]</tex> храним номер ребра с максимальным весом на пути <tex>i-root</tex>, где <tex>i</tex> - номер вершины, <tex>j</tex> - степень подъёма(как в LCA). Когда нам нужно получить максимальное ребро на пути <tex>a-b</tex>, ищем максимальное ребро на пути <tex>a-root</tex>, <tex>b-root</tex> и выбираем максимальное из них.

Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение LCA и дополнительного массива heavy-light декомпозиции работает за <tex>O(N \log N)</tex>, остов мы построим один раз, LCA heavy-light декомпозицию тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.

==ЛитератураИсточники информации==