Изменения

Очевидно, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но в таком случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальным. Зато его можно найти быстрее чем MST, а конкретно за <tex>O(E)</tex>. Для этого с Алгоритм описанный ниже ищет максимальное ребро минимального веса, но по этому ребру можно достаточно просто построить остовное дерево. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> ребро-медиану и разделим множество ребер на два подмножестваравных по мощности так, так чтобы в первом подмножестве все ребра были меньше медианы, а во втором большене превосходили ребро-медиану. Проверим образуют ли ребра из первого подмножества остов, просто запустив Запустим [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]] за <tex>O(E)</tex>, чтобы проверить образуют ли ребра из первого подмножества остов, иначе говоря связен ли этот подграф. Если да, то ответ меньше либо равен медиане, следовательновторое подмножество ребер можно "вкинуть", а от первого подмножества рекурсивно запустим запустить алгоритм для первой половины, а вторую "выкинем". Иначе сожмем полученные компоненты связности В противном случае сконденсируем в супервершины за <tex>O(E)</tex>, получившиеся несвязные компоненты и рассмотрим получившийся граф с этими супервершинами и ребра ребрами из второго подмножества. На последнем шаге ребро алгоритм соединит две оставшиеся оставшихся компоненты связности, - это ребро и будет ответоммаксимальное ребро минимального веса.На каждой итерации остается половина ребер, следовательно, время Время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</tex>.