Критерий Тарьяна минимальности остовного дерева

Теорема (критерий Тарьяна минимальности остовного дерева):

Остовное дерево минимально тогда и только тогда, когда любое ребро не из дерева является максимальным на цикле, который образуется при его добавлении в дерево.

Доказательство:

[math]\triangleright[/math]

Зеленые ребра принадлежат [math]T'[/math], красные принадлежат [math]T[/math] Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. Теперь докажем, что дерево, удовлетворяющее условию, минимально: Обозначим дерево [math]T[/math] и покажем, что его можно построить алгоритмом Краскала. Индукция по количеству ребер в дереве: База: пустое дерево. Переход: Строим дерево [math]T'[/math] по лемме о безопасном ребре. Рассмотрим минимальное ребро [math]uv \in T, 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]C[/math]. Противоречие условию теоремы. Если [math]uv[/math] минимально — добавим его в [math]T'[/math]. В процессе индукции добавлялись только ребра из [math]T[/math], поэтому построенное дерево [math]T'[/math] совпадет с [math]T[/math].

[math]\triangleleft[/math]