29
правок
Изменения
Добавлен раздел
{{Утверждение
|statement=
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа, соединяющего вершины <math>u</math> и <math>v</math>, не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между <math>u</math> и <math>v</math> в остовном дереве.
}}
Используем следующие обозначения:
В завершении алгоритма, требуется сравнить веса рёбер графа, которые не входят в остовное дерево, с найденными в дереве <math>B</math> рёбрами наибольшего веса, что потребует дополнительных <math>O(m)</math> операций сравнения.
== См. также ==* [[Остовные деревья: определения, лемма о безопасном ребре]]* [[Алгоритм Борувки]]* [[Критерий Тарьяна минимальности остовного дерева]]
== Источники информации ==
* King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037
