Изменения

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