394
правки
Изменения
→Описание алгоритма
==Описание алгоритма==
Пусть <tex>T</tex> подграф графа <tex>G</tex>. Изначально <tex>T</tex> содердит содержит все вершины из <tex>G</tex> и не содержит ребер.
Будем добавлять в <tex>T</tex> ребра следующим образом:
Пока <tex>T</tex> не является деревом
# Для каждой компоненты связанности связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте. # Добавим в <tex>T</tex> все ребра, которые хотя бы для одной компоненты связанности связности оказались минимальными.
Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
Данный алгоритм может работать неправильно если в графе есть ребра, равные по весу. Например полный граф из 3-х вершин, вес каждого ребра равен 1. Избежать эту проблему можно, выбирая в пункте 1 среди ребер, равных по весу ребро с наименьшим номером.
Доказательство будем производитьпроводить, считая веса всех ребер различными.
==Доказательство корректности==
