Критерий Тарьяна минимальности остовного дерева — различия между версиями
Filchenko (обсуждение | вклад) (фикс теха) |
Filchenko (обсуждение | вклад) (фикс) |
||
Строка 22: | Строка 22: | ||
Рассмотрим разрез, окружающий одну из двух компонент. | Рассмотрим разрез, окружающий одну из двух компонент. | ||
− | Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое ребро <tex>xy</tex>, такое что <tex>w(xy) \ge w(uv) | + | Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое ребро <tex>xy \in T</tex>, такое что <tex>w(xy) \ge w(uv) > w(ab)</tex>, будет лежать на цикле. Противоречие условию теоремы. |
Если <tex>uv</tex> минимально - добавим его в <tex>T'</tex>. | Если <tex>uv</tex> минимально - добавим его в <tex>T'</tex>. | ||
Версия 20:21, 15 января 2011
Теорема (критерий минимальности остовного дерева Тарьяна): |
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево. |
Доказательство: |
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: Если существует ребро, не максимальное на образовавшемся цикле мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. Теперь докажем, что дерево, удовлетворяющее условию минимально: Обозначим дерево , покажем что его можно построить алгоритмом Крускала.Индукция по количеству ребер в дереве: База: пустое дерево. Переход: Строим дерево по лемме о безопасном ребре. Рассмотрим минимальное невзятое ребро . Рассмотрим разрез, окружающий одну из двух компонент.Пусть По окончании (просмотрели все ребра не минимально в разрезе, тогда существует такое, что . Рассмотрим : некое ребро , такое что , будет лежать на цикле. Противоречие условию теоремы. Если минимально - добавим его в . ) совпадет с . |