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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Критерий Тарьяна)
(→‎Критерий Тарьяна)
Строка 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].

См.также

Литература

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — Алгоритмы. Построение и анализ.
Источник — «https://nerc.itmo.ru/wiki/index.php?title=Критерий_Тарьяна_минимальности_остовного_дерева&oldid=61804»