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