45
правок
Изменения
small-fix
== Критерий Тарьяна ==
{{Теорема
|about=
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</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> и выбираем максимальное из них.
}}
<h4>Алгоритм решения</h4>
Построим минимальное остовное дерево используя [[алгоритм Краскала]].
Рассмотрим рёбра <tex>e = (u, v)</tex> вне остова в любом порядке. Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева.
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.
*Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.
Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя [[метод двоичного подъема]].
Подвесим дерево за любую вершину, обозначим её за <tex>root</tex>. Построим LCA. Построим массив <tex>Dp</tex>, используя дополнительный массив <tex>up</tex> из LCA. <br><tex>dp[i][j]= \begin{cases}
0 & j = 0,\\
max(dp[up[i][j - 1]][j - 1], dp[i][j - 1]) & j \: \textgreater \: 0.
\end{cases}</tex> <br> Храним максимальный вес ребра на пути <tex>i</tex> и <tex>root</tex>, где <tex>i -</tex> номер вершины, <tex>j -</tex> степень подъёма(как в LCA). При запросе рассмотрим два случая:
*Путь ребра содержит корень. Заметим, если разделить путь на две части, то максимальным ребром будет максимальное среди меньших путей. Разобьём путь <tex>u</tex> и <tex>v</tex> на пути <tex>u</tex> и <tex>root</tex>, <tex>v</tex> и <tex>root</tex>. Найдём максимальное ребро на пути <tex>u</tex> и <tex>root</tex>, <tex>v</tex> и <tex>root</tex>, максимальное из них и будет являться ответом.
*Путь ребра не содержит корень. Будем подниматься из нижней вершины до высокой используя массив <tex>Dp</tex>. Какая из вершин выше узнаём используя функцию isUpper(в LCA используется).
<h4>Асимптотика</h4>
Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение LCA и дополнительного массива работает за <tex>O(N \log N)</tex>, остов мы построим один раз, LCA тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.
