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