143
правки
Изменения
теорема Тарьяна
{{Теорема
|about=
Теорема Тарьяна (критерий минимальности остовного дерева)
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро не из графа является максимальным на цмкле, который образуется при его добавлении в дерево
|proof=
Если существует ребро, не максимальное на образовавшемся цикле мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
Обозначим дерево <tex>T</tex>, покажем что его можно построить алгоритмом Крускала.
Индукция:
База:
пустое дерево. Строим дерево(<tex>T'</tex>) по лемме о безопасном ребре.
Переход:
Рассмотрим минимальное невзятое ребро <tex>uv \in T</tex>
Рассмотрим разрез, окружающий одну из двух компонент
Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. При добавлении <tex>ab</tex> в дерево <tex>T</tex> Некое ребро <tex>xy</tex>, такое что <tex>w(xy) \ge w(uv) < w(ab)</tex> будет лежать на цикле. Противоречие условию теоремы.
Если <tex>uv</tex> минимально - добавим его в <tex>T'</tex>.
По окончании (просмотрели все ребра <tex>T</tex>) <tex>T</tex> совпадет с <tex>T'</tex>
}}
|about=
Теорема Тарьяна (критерий минимальности остовного дерева)
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро не из графа является максимальным на цмкле, который образуется при его добавлении в дерево
|proof=
Если существует ребро, не максимальное на образовавшемся цикле мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
Обозначим дерево <tex>T</tex>, покажем что его можно построить алгоритмом Крускала.
Индукция:
База:
пустое дерево. Строим дерево(<tex>T'</tex>) по лемме о безопасном ребре.
Переход:
Рассмотрим минимальное невзятое ребро <tex>uv \in T</tex>
Рассмотрим разрез, окружающий одну из двух компонент
Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. При добавлении <tex>ab</tex> в дерево <tex>T</tex> Некое ребро <tex>xy</tex>, такое что <tex>w(xy) \ge w(uv) < w(ab)</tex> будет лежать на цикле. Противоречие условию теоремы.
Если <tex>uv</tex> минимально - добавим его в <tex>T'</tex>.
По окончании (просмотрели все ребра <tex>T</tex>) <tex>T</tex> совпадет с <tex>T'</tex>
}}
