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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий Тарьяна)
(Критерий Тарьяна)
Строка 6: Строка 6:
 
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
 
Остовное дерево минимально тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра.
 
|proof=
 
|proof=
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально.
 
Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом, добавив это ребро в остов, и удалив самое тяжелое ребро из цикла. Если же это условие не выполнилось ни для одного ребра, то вес остова при добавлении не изменится.
 
 
  
Теперь, рассмотрим общий алгоритм построения минимального остовного дерева <tex> A </tex>, но сначала надо ознакомиться с [[Лемма о безопасном ребре|леммой о безопасном ребре]].
+
Рассмотрим общий алгоритм построения минимального остовного дерева <tex> A </tex>, но сначала, ознакомившись с определением [[Лемма о безопасном ребре|безопасного ребра]].
 
   
 
   
 
  '''function''' Generic MST(<tex> G </tex>):  
 
  '''function''' Generic MST(<tex> G </tex>):  
Строка 18: Строка 15:
 
           <tex> A = A \cup \{( u, v )\} </tex>  
 
           <tex> A = A \cup \{( u, v )\} </tex>  
 
  '''return''' <tex> A </tex>
 
  '''return''' <tex> A </tex>
 +
 +
В результате алгоритма получится минимальное остовное дерево <tex> A </tex>, состоящее полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро.
 +
 +
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально.
 +
Если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом, добавив это ребро в остов, и удалив самое тяжелое ребро из цикла. Если же это условие не выполнилось ни для одного ребра, то вес остова при добавлении не изменится.
 +
  
  
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
 
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
 
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
 
  
 
}}
 
}}

Версия 23:06, 24 июня 2017

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

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

Рассмотрим общий алгоритм построения минимального остовного дерева [math] A [/math], но сначала, ознакомившись с определением безопасного ребра.

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]\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].

См.также

Литература

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