113
правок
Изменения
→Критерий Тарьяна
<tex> \Rightarrow </tex>
Пусть дано есть остовное дерево <tex> A </tex>, состоящее из минимальных ребер на циклах. Докажем, что такое дерево минимально. Предположим противное: в дереве <tex> A </tex> не все минимальные ребра на циклах. Тогда, найдется цикл, в котором есть ребро <tex> (u, v) \notin A</tex>, которое легче остальных ребер этого цикла, включая ребро <tex> (a, b) \in A</tex>. Следовательно, можно получить остов с меньшим весом, удалив ребро <tex> (a, b) </tex>, и, добавив <tex> (u, v) </tex>. Поэтому, дерево содержащее не минимальные ребра на циклах не минимально {{---}} противоречие. <tex> \Leftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, которое получилось в результате с помощью общего алгоритма построения MST. Докажем, что оно имеет ребра минимального веса на каждом цикле.
'''function''' Generic MST(<tex> G </tex>):
Следовательно, любое ребро <tex> \notin A</tex> не легче ребер <tex> \in A </tex> на этом цикле.
}}
