Критерий Тарьяна минимальности остовного дерева — различия между версиями
(Новое доказательство) |
|||
| Строка 5: | Строка 5: | ||
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево. | Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево. | ||
|proof= | |proof= | ||
| − | |||
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: | Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: | ||
Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. | Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. | ||
| − | Теперь докажем, что дерево, удовлетворяющее условию, минимально: | + | Теперь докажем, что дерево <tex>T</tex>, удовлетворяющее условию, минимально: |
| − | + | Для этого заметим, что для любого разреза <tex>\langle S, T \rangle</tex> исходного графа <tex>G</tex>, вес ребра <tex>uv \in T</tex>, пересекающего этот разрез, минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим ребро <tex>ab \notin T</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>T</tex>. | |
| − | + | По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) </tex>, ч. т. д. | |
| − | + | Найдем теперь минимальное остовное дерево графа используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано выше, равен весу ребра <tex>T</tex>, пересекающего этот разрез. Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>T</tex>, что и требовалось. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
Версия 21:13, 14 декабря 2011
| Теорема (критерий Тарьяна минимальности остовного дерева): |
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево. |
| Доказательство: |
|
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. Теперь докажем, что дерево , удовлетворяющее условию, минимально: Для этого заметим, что для любого разреза исходного графа , вес ребра , пересекающего этот разрез, минимален среди всех ребер , пересекающих этот разрез. Действительно, рассмотрим ребро , пересекающее и путь между вершинами и по дереву . По условию теоремы, вес не меньше веса любого ребра на этом пути. При этом пересекает , поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это . Таким образом, , ч. т. д. Найдем теперь минимальное остовное дерево графа используя алгоритм Краскала, который представляет собой применение леммы о безопасном ребре некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано выше, равен весу ребра , пересекающего этот разрез. Поэтому вес получившегося минимального остова будет равен весу , что и требовалось. |
