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

Материал из Викиконспекты
Перейти к: навигация, поиск
(фикс)
(фикс)
Строка 21: Строка 21:
  
 
Строим дерево <tex>T'</tex> по лемме о безопасном ребре. Рассмотрим минимальное ребро <tex>uv \in uv \notin T'</tex>.  
 
Строим дерево <tex>T'</tex> по лемме о безопасном ребре. Рассмотрим минимальное ребро <tex>uv \in uv \notin T'</tex>.  
Рассмотрим разрез <tex>(U,V): u \in U v \in V</tex>.
+
Рассмотрим разрез <tex>(U,V): u \in U, v \in V</tex>.
  
 
Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое ребро <tex>xy \in T</tex>, такое что <tex>w(xy) \ge w(uv) > w(ab)</tex>, будет лежать на цикле. Противоречие условию теоремы.
 
Пусть <tex>uv</tex> не минимально в разрезе, тогда существует <tex>ab \notin T</tex> такое, что <tex>w(ab) < w(uv)</tex>. Рассмотрим <tex>\{ab\} \cup T</tex>: некое ребро <tex>xy \in T</tex>, такое что <tex>w(xy) \ge w(uv) > w(ab)</tex>, будет лежать на цикле. Противоречие условию теоремы.

Версия 20:39, 15 января 2011

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

Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально:

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

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

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

Индукция по количеству ребер в дереве:

База: пустое дерево.

Переход:

Строим дерево [math]T'[/math] по лемме о безопасном ребре. Рассмотрим минимальное ребро [math]uv \in uv \notin T'[/math]. Рассмотрим разрез [math](U,V): u \in U, v \in V[/math].

Пусть [math]uv[/math] не минимально в разрезе, тогда существует [math]ab \notin T[/math] такое, что [math]w(ab) \lt w(uv)[/math]. Рассмотрим [math]\{ab\} \cup T[/math]: некое ребро [math]xy \in T[/math], такое что [math]w(xy) \ge w(uv) \gt w(ab)[/math], будет лежать на цикле. Противоречие условию теоремы.

Если [math]uv[/math] минимально — добавим его в [math]T'[/math].

В процессе индукции добавлялись только ребра из [math]T[/math], поэтому построенное дерево [math]T'[/math] совпадет с [math]T[/math].
[math]\triangleleft[/math]