1
правка
Изменения
м
[[Файл:Граф_тарьян.png|thumb|right|300x200px|Зеленые ребра принадлежат <tex>T'\Rightarrow </tex>, красные принадлежат <tex>T</tex>]]Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
Если существует реброДокажем, не максимальное что остовное дерево, состоящее из ребер наименьшего веса на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальноециклах {{---}} минимально.
Теперь докажем, что Предположим противное: пусть остовное дерево<tex> A </tex> состоит из всех минимальных ребер на циклах, удовлетворяющее условию, тогда оно не минимально:.
Обозначим дерево Если <tex>TA </tex> и покажемне минимально, что то его можно построить алгоритмом Краскалаулучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие.
Индукция по количеству ребер в дереве:<tex> \Leftarrow </tex>
'''Переход:''' Заметим, что дерево <tex> A </tex> состоит полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.
Строим дерево Теперь, рассмотрим какой-нибудь разрез <tex>(S, T') </tex> по лемме о безопасном ребре. Рассмотрим минимальное уже построенного дерева <tex> A </tex> и пересекающее ребро <tex>uv (u, v) </tex>, причем <tex> u \in S </tex>, а <tex> v \in T</tex>. Найдем путь в изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то какое-нибудь ребро <tex> (a, uv b) \notin T'A</tex>. Рассмотрим тоже будет пересекать разрез по этому ребру <tex>(US,VT): </tex>. Очевидно, что <tex> w(u \in U, v ) \in Vleqslant w(a, b) </tex>, так как первое {{---}} безопасное ребро.
Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такоеСледовательно, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое любое ребро не принадлежащее <tex>xy \in TA</tex>, такое что не легче ребер принадлежащих <tex>w(xy) \ge w(uv) > w(ab)A </tex>, будет лежать на этом цикле <tex>C</tex>. Противоречие условию теоремы.
Если <tex>uv</tex> минимально — добавим его в <tex>T'</tex>.
В процессе индукции добавлялись только ребра из <tex>T</tex>, поэтому построенное дерево <tex>T'</tex> совпадет с <tex>T</tex>.}}
→Критерий Тарьяна: Орфография
== Критерий Тарьяна ==
{{Теорема
|about=
критерий Тарьяна минимальности остовного дерева
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро для любого ребра, не из дерева является максимальным на циклепринадлежащего остову, цикл, который образуется образуемый этим ребром при его добавлении в деревок остову, не содержит рёбер тяжелее этого ребра.
|proof=
Построим минимальное остовное дерево <tex> A </tex>, с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра на каждом цикле. '''function'''БазаGeneric MST(<tex> G </tex>): <tex> A = \{ \} </tex> '''while'''<tex> A </tex> не является остовом ' пустое дерево.''do''' найти безопасное ребро <tex> ( u, v ) \in E </tex> для <tex> A </tex> <font color = darkgreen>// нужное ребро находится с помощью [[Лемма о безопасном ребре|леммы о безопасном ребре]] </font color = darkgreen> <tex> A = A \cup \{( u, v )\} </tex> '''return''' <tex> A </tex>
== Уникальность остовного дерева ==
{{Задача
|definition=Поиск минимального остовного дерева и проверка его на уникальность.
}}
<h4>Алгоритм решения</h4>
Построим минимальное остовное дерево используя [[алгоритм Краскала]].
Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим <tex>e = (u, v)</tex>. Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев.
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.
*Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.
После рассмотрения всех рёбер, если мы не нашли ребро вне остова, при добавлении которого создаётся цикл с максимальным ребром таким же как и на пути <tex>u</tex> и <tex>v</tex>, то в графе нету другого остовного дерева и наше дерево уникально.
Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи [[Heavy-light декомпозиция|heavy-light декомпозиции]].
<h4>Асимптотика</h4>
Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение heavy-light декомпозиции работает за <tex>O(N)</tex>, остов мы построим один раз, heavy-light декомпозицию тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.
== См.также ==
* [[Остовные деревья: определения, лемма о безопасном ребре]]
* [[Минимально узкое остовное дерево]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Алгоритм Прима]]
==Источники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
