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

Материал из Викиконспекты
Перейти к: навигация, поиск
(изменено обозначение MST на K)
(утверждение исправлено и вынесено в шаблон)
Строка 6: Строка 6:
 
|proof=
 
|proof=
 
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
 
Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:
−
 
+
если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
−
Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.
 
  
 
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:
 
Теперь докажем, что дерево <tex>K</tex>, удовлетворяющее условию, минимально:
  
−
Для этого покажем, что для любого разреза <tex>\langle S, T \rangle</tex> исходного графа <tex>G</tex>, вес ребра <tex>uv \in K</tex>, пересекающего этот разрез, минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез. Действительно, рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.
+
{{Утверждение
−
 
+
|statement=Для любого разреза <tex>\langle S, T \rangle</tex>, в котором ребро <tex>uv</tex> {{---}} единственное, пересекающее его в <tex>K</tex>, вес этого ребра минимален среди всех ребер <tex>G</tex>, пересекающих этот разрез.
−
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути. При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это <tex>uv</tex>. Таким образом, <tex>w(ab) \ge w(uv) </tex>, ч. т. д.
 
  
−
Найдем теперь минимальное остовное дерево графа используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано выше, равен весу ребра <tex>T</tex>, пересекающего этот разрез. Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>T</tex>, что и требовалось.
+
|proof=Рассмотрим ребро <tex>ab \notin K</tex>, пересекающее <tex>\langle S, T \rangle </tex> и путь между вершинами <tex>a</tex> и <tex>b</tex> по дереву <tex>K</tex>.
 +
По условию теоремы, вес <tex>ab</tex> не меньше веса любого ребра на этом пути.
 +
При этом <tex>ab</tex> пересекает <tex>\langle S, T \rangle</tex>, поэтому на этом пути найдется ребро, пересекающее этот разрез.
 +
Но единственное такое ребро в остовном дереве {{---}} это <tex>uv</tex>.
 +
Следовательно, <tex>w(uv) \le w(ab)</tex>.
 +
}}
  
 +
Для доказательства минимальности <tex>K</tex> построим минимальное остовное дерево графа <tex>G</tex> используя [[алгоритм Краскала]], который представляет собой применение [[Лемма о безопасном ребре|леммы о безопасном ребре]] некоторое число раз.
 +
На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из <tex>K</tex>, пересекающего этот разрез.
 +
Поэтому вес получившегося минимального остова <tex>G</tex> будет равен весу <tex>K</tex>, что и требовалось.
 
}}
 
}}
  

Версия 21:59, 10 января 2015

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

Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: если существует ребро, не максимальное на образовавшемся цикле, то мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное.

Теперь докажем, что дерево [math]K[/math], удовлетворяющее условию, минимально:

Утверждение:
Для любого разреза [math]\langle S, T \rangle[/math], в котором ребро [math]uv[/math] — единственное, пересекающее его в [math]K[/math], вес этого ребра минимален среди всех ребер [math]G[/math], пересекающих этот разрез.
[math]\triangleright[/math]

Рассмотрим ребро [math]ab \notin K[/math], пересекающее [math]\langle S, T \rangle [/math] и путь между вершинами [math]a[/math] и [math]b[/math] по дереву [math]K[/math]. По условию теоремы, вес [math]ab[/math] не меньше веса любого ребра на этом пути. При этом [math]ab[/math] пересекает [math]\langle S, T \rangle[/math], поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве — это [math]uv[/math].

Следовательно, [math]w(uv) \le w(ab)[/math].
[math]\triangleleft[/math]

Для доказательства минимальности [math]K[/math] построим минимальное остовное дерево графа [math]G[/math] используя алгоритм Краскала, который представляет собой применение леммы о безопасном ребре некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано в утверждении выше, равен весу ребра из [math]K[/math], пересекающего этот разрез.

Поэтому вес получившегося минимального остова [math]G[/math] будет равен весу [math]K[/math], что и требовалось.
[math]\triangleleft[/math]

Литература

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