29
правок
Изменения
м
Нет описания правки
== Описание алгоритма ==
Пусть <math>T = (V_T, E_T)</math> {{---}} остовное дерево неориентированного взвешенного графа <math>G = (V_G, E_G)</math>. Обозначим как <math>\{u, v\}</math> ребро, которое соединяет вершины <math>u</math> и <math>v</math>.
Описываемый метод заключается в проверке [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]]:
{{Утверждение
|statement=
Остовное дерево является минимальным тогда и только тогда, когда вес любого ребра графа <math>\{u, v\}</math>, не входящего в остовное дерево, больше либо равен весу ребра, имеющего максимальный вес среди ребер входящих в путь между <math>u</math> и <math>v</math> в остовном дереве.
}}
Используем следующие обозначения:
* <math>\{u, v\}</math> {{---}} ребро, соединяющее вершины <math>u</math> и <math>v</math>,
* <math>T(u, v)</math> {{---}} множество рёбер, входящих в путь между вершинами <math>u, v</math> в дереве <math>T</math>,
* <math>w(e)</math> {{---}} вес ребра <math>e</math>,
