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