1
правка
Изменения
м
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.<tex> \Rightarrow </tex>
Теперь докажемДокажем, что остовное дерево <tex>K</tex>, удовлетворяющее условию, состоящее из ребер наименьшего веса на циклах {{---}} минимально:.
{{Утверждение|statement=Для любого разреза Предположим противное: пусть остовное дерево <tex>\langle S, T \rangleA </tex>, в котором ребро <tex>uv</tex> {{---}} единственное, пересекающее его в <tex>K</tex>, вес этого ребра минимален среди состоит из всех минимальных ребер <tex>G</tex>на циклах, пересекающих этот разрезтогда оно не минимально.
|proof=Рассмотрим Если <tex> A </tex> не минимально, то его можно улучшить, значит есть ребро , которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие. <tex>ab \notin KLeftarrow </tex> Построим минимальное остовное дерево <tex> A </tex>, пересекающее с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра на каждом цикле. '''function''' Generic MST(<tex> G </tex>): <tex>A = \{ \langle S} </tex> '''while''' <tex> A </tex> не является остовом '''do''' найти безопасное ребро <tex> ( u, T v ) \rangle in E </tex> и путь между вершинами для <tex>aA </tex> и <font color = darkgreen>// нужное ребро находится с помощью [[Лемма о безопасном ребре|леммы о безопасном ребре]] </font color = darkgreen> <tex>bA = A \cup \{( u, v )\} </tex> по дереву '''return''' <tex>KA </tex>.По условию теоремыЗаметим, вес что дерево <tex>abA </tex> не меньше веса любого ребра состоит полностью из безопасных ребер, так как на этом путикаждом шаге добавлялось безопасное ребро.При этом Теперь, рассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex>ab(u, v) </tex> пересекает , причем <tex>u \langle in S</tex>, а <tex> v \in T \rangle</tex>. Найдем путь в изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, поэтому на этом пути найдется то какое-нибудь ребро<tex> (a, пересекающее этот b) \notin A</tex> тоже будет пересекать разрез.Но единственное такое ребро в остовном дереве {{---}} это <tex>uv(S, T) </tex>.СледовательноОчевидно, что <tex>w(uvu, v) \le leqslant w(aba, b)</tex>, так как первое {{---}} безопасное ребро.}}Следовательно, любое ребро не принадлежащее <tex> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
→Критерий Тарьяна: Орфография
критерий Тарьяна минимальности остовного дерева
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро для любого ребра, не из дерева является максимальным на циклепринадлежащего остову, цикл, который образуется образуемый этим ребром при его добавлении в деревок остову, не содержит рёбер тяжелее этого ребра.
|proof=
}}
== Уникальность остовного дерева ==
{{Задача
<h4>Алгоритм решения</h4>
Построим минимальное остовное дерево используя [[алгоритм Краскала]].
Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим <tex>e = (u, v)</tex> . Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев.
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.
== См.также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Минимально узкое остовное дерево]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Алгоритм Прима]]
==ЛитератураИсточники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
