Изменения

Перейти к: навигация, поиск

Алгоритм Борувки

1 байт добавлено, 23:58, 15 декабря 2012
Описание алгоритма
Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например полный граф из трех вершин, вес каждого ребра равен один.В <tex>T</tex> могут быть добавлены все 3 ребра. Избежать эту проблему можно, выбирая в пункте 1 среди ребер, равных по весу, ребро с наименьшим номером.
Доказательство будем проводить, считая веса всех ребер различными.
394
правки

Навигация