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