Критерий Тарьяна минимальности остовного дерева — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(small-fix)
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 6 участников)
Строка 4: Строка 4:
 
критерий Тарьяна минимальности остовного дерева
 
критерий Тарьяна минимальности остовного дерева
 
|statement=
 
|statement=
Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.
+
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
 
|proof=
 
|proof=
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
+
<tex> \Rightarrow </tex>
если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
 
  
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:
+
Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах {{---}}  минимально.
  
{{Утверждение
+
Предположим противное: пусть остовное дерево <tex> A </tex> состоит из всех минимальных ребер на циклах, тогда оно не минимально.  
|statement=Для любого разреза <tex>\langle S, T \rangle</tex>, в котором ребро <tex>uv</tex> {{---}} единственное, пересекающее его в <tex>K</tex>, вес этого ребра минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез.
 
  
|proof=Рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.
+
Если <tex> A </tex> не минимально, то его можно улучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах {{---}} противоречие.
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути.
+
 
При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез.
+
<tex> \Leftarrow </tex>
Но единственное такое ребро в остовном дереве {{---}} это <tex>uv</tex>.
+
 
Следовательно, <tex>w(uv) \le w(ab)</tex>.
+
Построим минимальное остовное дерево <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>
 +
 
 +
Заметим, что дерево <tex> A </tex> состоит полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.
 +
 
 +
Теперь, рассмотрим какой-нибудь разрез <tex> (S, T) </tex> уже построенного дерева <tex> A </tex> и пересекающее ребро <tex> (u, v) </tex>, причем <tex> u \in S </tex>, а <tex> v \in T </tex>. Найдем путь в изначальном графе <tex> G </tex>, соединяющий вершины <tex> u </tex> и <tex> v </tex>. Так как они находятся в разных компонентах связности, то какое-нибудь ребро <tex> (a, b) \notin A</tex> тоже будет пересекать разрез <tex> (S, T) </tex>. Очевидно, что <tex> w(u, v) \leqslant  w(a, b) </tex>, так как первое {{---}} безопасное ребро.  
 +
 
 +
Следовательно, любое ребро не принадлежащее <tex> A</tex> не легче ребер принадлежащих <tex> A </tex> на этом цикле.
  
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
 
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
 
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
 
  
 
}}
 
}}
 +
 
== Уникальность остовного дерева ==
 
== Уникальность остовного дерева ==
 
{{Задача
 
{{Задача
Строка 32: Строка 40:
 
<h4>Алгоритм решения</h4>
 
<h4>Алгоритм решения</h4>
 
Построим минимальное остовное дерево используя [[алгоритм Краскала]].  
 
Построим минимальное остовное дерево используя [[алгоритм Краскала]].  
Рассмотрим рёбра <tex>e = (u, v)</tex> вне остова в любом порядке. Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:
+
Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим <tex>e = (u, v)</tex>. Рассмотрим максимальное ребро на пути <tex>u</tex> и <tex>v</tex> внутри остова:
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева.  
+
*Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев.  
 
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.  
 
*Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.  
 
*Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.
 
*Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.
Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя [[метод двоичного подъема]].
+
После рассмотрения всех рёбер, если мы не нашли ребро вне остова, при добавлении которого создаётся цикл с максимальным ребром таким же как и на пути <tex>u</tex> и <tex>v</tex>, то в графе нету другого остовного дерева и наше дерево уникально.
Подвесим дерево за любую вершину, обозначим её за <tex>root</tex>. Построим LCA. Построим массив <tex>Dp</tex>, используя дополнительный массив <tex>up</tex> из LCA. <br><tex>dp[i][j]= \begin{cases}
+
Искать максимальное ребро на пути <tex>u</tex> и <tex>v</tex> в дереве мы можем при помощи [[Heavy-light декомпозиция|heavy-light декомпозиции]].
0 & j = 0,\\
 
max(dp[up[i][j - 1]][j - 1], dp[i][j - 1]) & j \: \textgreater \: 0.
 
\end{cases}</tex> <br> Храним максимальный вес ребра на пути <tex>i</tex> и <tex>root</tex>, где <tex>i -</tex> номер вершины, <tex>j -</tex> степень подъёма(как в LCA). При запросе рассмотрим два случая:
 
*Путь ребра содержит корень. Заметим, если разделить путь на две части, то максимальным ребром будет максимальное среди меньших путей. Разобьём путь <tex>u</tex> и <tex>v</tex> на пути <tex>u</tex> и <tex>root</tex>, <tex>v</tex> и <tex>root</tex>. Найдём максимальное ребро на пути <tex>u</tex> и <tex>root</tex>, <tex>v</tex> и <tex>root</tex>, максимальное из них и будет являться ответом.
 
*Путь ребра не содержит корень. Будем подниматься из нижней вершины до высокой используя массив <tex>Dp</tex>. Какая из вершин выше узнаём используя функцию isUpper(в LCA используется).
 
 
<h4>Асимптотика</h4>
 
<h4>Асимптотика</h4>
Построение минимального остовного дерева работает за <tex>O(N \log N)</tex>, нахождение максимального ребра за <tex>O(\log N)</tex>, максимальное количество рёбер вне остова не больше <tex>N</tex>, каждое ребро проверяется за <tex>O(\log N)</tex>. Построение LCA и дополнительного массива работает за <tex>O(N \log N)</tex>, остов мы построим один раз, LCA тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма <tex>O(N \log N)</tex>.
+
Построение минимального остовного дерева работает за <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>.
  
 
== См.также ==
 
== См.также ==
 
* [[Остовные деревья: определения, лемма о безопасном ребре]]
 
* [[Остовные деревья: определения, лемма о безопасном ребре]]
 +
* [[Минимально узкое остовное дерево]]
 +
* [[Алгоритм Краскала]]
 +
* [[Алгоритм Борувки]]
 +
* [[Алгоритм Прима]]
  
==Литература==
+
==Источники информации==
 
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
 
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]

Текущая версия на 19:39, 4 сентября 2022

Критерий Тарьяна

Теорема (критерий Тарьяна минимальности остовного дерева):
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
Доказательство:
[math]\triangleright[/math]

[math] \Rightarrow [/math]

Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах — минимально.

Предположим противное: пусть остовное дерево [math] A [/math] состоит из всех минимальных ребер на циклах, тогда оно не минимально.

Если [math] A [/math] не минимально, то его можно улучшить, значит есть ребро, которое имеет наименьший вес на цикле и не принадлежит дереву. Следовательно, дерево построено не на минимальных ребрах в циклах — противоречие.

[math] \Leftarrow [/math]

Построим минимальное остовное дерево [math] A [/math], с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра на каждом цикле.

function Generic MST([math] G [/math]): 
   [math] A = \{ \} [/math]
   while [math] A [/math] не является остовом
      do найти безопасное ребро [math] ( u, v ) \in E [/math] для [math] A [/math] // нужное ребро находится с помощью леммы о безопасном ребре 
         [math] A = A \cup \{( u, v )\} [/math] 
return [math] A [/math]

Заметим, что дерево [math] A [/math] состоит полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.

Теперь, рассмотрим какой-нибудь разрез [math] (S, T) [/math] уже построенного дерева [math] A [/math] и пересекающее ребро [math] (u, v) [/math], причем [math] u \in S [/math], а [math] v \in T [/math]. Найдем путь в изначальном графе [math] G [/math], соединяющий вершины [math] u [/math] и [math] v [/math]. Так как они находятся в разных компонентах связности, то какое-нибудь ребро [math] (a, b) \notin A[/math] тоже будет пересекать разрез [math] (S, T) [/math]. Очевидно, что [math] w(u, v) \leqslant w(a, b) [/math], так как первое — безопасное ребро.

Следовательно, любое ребро не принадлежащее [math] A[/math] не легче ребер принадлежащих [math] A [/math] на этом цикле.
[math]\triangleleft[/math]

Уникальность остовного дерева

Задача:
Поиск минимального остовного дерева и проверка его на уникальность.

Алгоритм решения

Построим минимальное остовное дерево используя алгоритм Краскала. Рассмотрим рёбра вне остова в любом порядке. Очередное обозначим [math]e = (u, v)[/math]. Рассмотрим максимальное ребро на пути [math]u[/math] и [math]v[/math] внутри остова:

  • Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева. На этом алгоритм завершается и по критерию Тарьяна мы можем сказать, что в графе можно построить несколько остовных деревьев.
  • Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.
  • Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.

После рассмотрения всех рёбер, если мы не нашли ребро вне остова, при добавлении которого создаётся цикл с максимальным ребром таким же как и на пути [math]u[/math] и [math]v[/math], то в графе нету другого остовного дерева и наше дерево уникально. Искать максимальное ребро на пути [math]u[/math] и [math]v[/math] в дереве мы можем при помощи heavy-light декомпозиции.

Асимптотика

Построение минимального остовного дерева работает за [math]O(N \log N)[/math], нахождение максимального ребра за [math]O(\log N)[/math], максимальное количество рёбер вне остова не больше [math]N[/math], каждое ребро проверяется за [math]O(\log N)[/math]. Построение heavy-light декомпозиции работает за [math]O(N)[/math], остов мы построим один раз, heavy-light декомпозицию тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма [math]O(N \log N)[/math].

См.также

Источники информации

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — Алгоритмы. Построение и анализ.