Изменения

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