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