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