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

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

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

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

[math]\triangleright[/math]

Легко заметить, что остовное дерево, не удовлетворяющее условию, не минимально: Если существует ребро, не максимальное на образовавшемся цикле, мы можем уменьшить вес дерева, добавив это ребро и удалив максимальное. Теперь докажем, что дерево [math]T[/math], удовлетворяющее условию, минимально: Для этого покажем, что для любого разреза [math]\langle S, T \rangle[/math] исходного графа [math]G[/math], вес ребра [math]uv \in T[/math], пересекающего этот разрез, минимален среди всех ребер [math]G[/math], пересекающих этот разрез. Действительно, рассмотрим ребро [math]ab \notin T[/math], пересекающее [math]\langle S, T \rangle [/math] и путь между вершинами [math]a[/math] и [math]b[/math] по дереву [math]T[/math]. По условию теоремы, вес [math]ab[/math] не меньше веса любого ребра на этом пути. При этом [math]ab[/math] пересекает [math]\langle S, T \rangle[/math], поэтому на этом пути найдется ребро, пересекающее этот разрез. Но единственное такое ребро в остовном дереве - это [math]uv[/math]. Таким образом, [math]w(ab) \ge w(uv) [/math], ч. т. д. Найдем теперь минимальное остовное дерево графа используя алгоритм Краскала, который представляет собой применение леммы о безопасном ребре некоторое число раз. На каждом шаге к строящемуся остову будет добавляться ребро минимального веса, пересекающего некоторый разрез, а этот вес, как было показано выше, равен весу ребра [math]T[/math], пересекающего этот разрез. Поэтому вес получившегося минимального остова [math]G[/math] будет равен весу [math]T[/math], что и требовалось.

[math]\triangleleft[/math]

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — Алгоритмы. Построение и анализ.