1169
правок
Алгоритм Борувки: различия между версиями
Материал из WikiGrapp
нет описания правки
KVN (обсуждение | вклад) (Новая страница: «'''Алгоритм Борувки''' (''Borůvka's algorithm'') --- алгоритм поиска каркаса наименьшего веса во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой. Алгоритм начинает с рассмотрения исходного графа, как множес...») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Алгоритм Борувки''' (''Borůvka's algorithm'') --- алгоритм поиска [[Каркас|каркаса]] наименьшего веса во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой. | '''Алгоритм Борувки''' (''Borůvka's algorithm'') --- алгоритм поиска [[Каркас|каркаса]] наименьшего веса во [[Взвешенный граф|взвешенном]] неориентированном [[Связный граф|связном]] графе. Впервые был опубликован в 1926 году Отакаром Борувкой. | ||
Алгоритм начинает с рассмотрения исходного графа, как множества тривиальных деревьев (по числу вершин исходного графа), и затем до тех пор, пока не останется только одно дерево (оно и есть результат работы алгоритма), для каждого дерева находит минимальное по весу инцидентное ему ребро и добавляет все такие ребра. | Алгоритм начинает с рассмотрения исходного графа, как множества [[Тривиальный граф|тривиальных]] деревьев (по числу вершин исходного графа), и затем до тех пор, пока не останется только одно дерево (оно и есть результат работы алгоритма), для каждого дерева находит минимальное по весу инцидентное ему ребро и добавляет все такие ребра. | ||
Алгоритм может работать неправильно, если в графе есть равные по весу ребра, которые образуют треугольник, и нуждается в модификации. | Алгоритм может работать неправильно, если в графе есть равные по весу ребра, которые образуют треугольник, и нуждается в модификации. | ||
[[Категория:Деревья]] | |||
[[Категория:Обыкновенные графы]] | |||
