Критерий Тарьяна минимальности остовного дерева
Теорема (критерий минимальности остовного дерева Тарьяна): |
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево. |
Доказательство: |
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. Теперь докажем, что дерево, удовлетворяющее условию, минимально: Обозначим дерево и покажем, что его можно построить алгоритмом Крускала.Индукция по количеству ребер в дереве: База: пустое дерево. Переход: Строим дерево по лемме о безопасном ребре. Рассмотрим минимальное ребро . Рассмотрим разрез по этому ребру .Пусть не минимально в разрезе, тогда существует такое, что . Рассмотрим : некое ребро , такое что , будет лежать на цикле . Противоречие условию теоремы.Если В процессе индукции добавлялись только ребра из минимально — добавим его в . , поэтому построенное дерево совпадет с . |