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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (whitespace fix)
м (фикс)
Строка 9: Строка 9:
 
Обозначим дерево <tex>T</tex>, покажем что его можно построить алгоритмом Крускала.
 
Обозначим дерево <tex>T</tex>, покажем что его можно построить алгоритмом Крускала.
  
Индукция:
+
Индукция по количеству ребер в дереве:
 
База:
 
База:
 
пустое дерево. Строим дерево <tex>T'</tex> по лемме о безопасном ребре.
 
пустое дерево. Строим дерево <tex>T'</tex> по лемме о безопасном ребре.

Версия 22:51, 1 декабря 2010

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

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

Обозначим дерево [math]T[/math], покажем что его можно построить алгоритмом Крускала.

Индукция по количеству ребер в дереве: База: пустое дерево. Строим дерево [math]T'[/math] по лемме о безопасном ребре.

Переход: Рассмотрим минимальное невзятое ребро [math]uv \in T[/math] Рассмотрим разрез, окружающий одну из двух компонент

Пусть [math]uv[/math] не минимально в разрезе, тогда существует [math]ab \notin T[/math] такое, что [math]w(ab) \lt w(uv)[/math]. При добавлении [math]ab[/math] в дерево [math]T[/math] Некое ребро [math]xy[/math], такое что [math]w(xy) \ge w(uv) \lt w(ab)[/math] будет лежать на цикле. Противоречие условию теоремы. Если [math]uv[/math] минимально - добавим его в [math]T'[/math].

По окончании (просмотрели все ребра [math]T[/math]) [math]T[/math] совпадет с [math]T'[/math]
[math]\triangleleft[/math]