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

Критерий Тарьяна

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

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

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

[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]

Уникальность остовного дерева

Задача:

Поиск минимального остовного дерева и проверка его на уникальность.

Алгоритм решения

Построим минимальное остовное дерево используя алгоритм Краскала. Рассмотрим рёбра [math]e = (u, v)[/math] вне остова в любом порядке. Рассмотрим максимальное ребро на пути [math]u[/math] и [math]v[/math] внутри остова:

• Если его вес совпадает с весом ребра, то при добавлении ребра в остов, мы получим остов с циклом на котором несколько рёбер имеют одинаковый вес, значит мы можем удалить любое из них и остовное дерево будет всё ещё минимальным, это нарушает уникальность дерева.
• Если его вес больше ребра, то заменив ребро мы получим остов с большим весом, этот случай не влияет на уникальность.
• Его вес не может быть меньше ребра из остова, иначе мы смогли бы построить минимальное остовное дерево с меньшим весом.

Искать максимальное ребро на пути [math]u[/math] и [math]v[/math] в дереве мы можем при помощи алгоритма минимального общего предка(LCA), используя метод двоичного подъема. Подвесим дерево за любую вершину, обозначим её за [math]root[/math]. Построим LCA. Построим массив [math]Dp[/math], используя дополнительный массив [math]up[/math] из LCA.
[math]dp[i][j]= \begin{cases} 0 & j = 0,\\ max(dp[up[i][j - 1]][j - 1], dp[i][j - 1]) & j \: \textgreater \: 0. \end{cases}[/math]
Храним максимальный вес ребра на пути [math]i[/math] и [math]root[/math], где [math]i -[/math] номер вершины, [math]j -[/math] степень подъёма(как в LCA). При запросе рассмотрим два случая:

• Путь ребра содержит корень. Заметим, если разделить путь на две части, то максимальным ребром будет максимальное среди меньших путей. Разобьём путь [math]u[/math] и [math]v[/math] на пути [math]u[/math] и [math]root[/math], [math]v[/math] и [math]root[/math]. Найдём максимальное ребро на пути [math]u[/math] и [math]root[/math], [math]v[/math] и [math]root[/math], максимальное из них и будет являться ответом.
• Путь ребра не содержит корень. Будем подниматься из нижней вершины до высокой используя массив [math]Dp[/math]. Какая из вершин выше узнаём используя функцию isUpper(в LCA используется).

Асимптотика

Построение минимального остовного дерева работает за [math]O(N \log N)[/math], нахождение максимального ребра за [math]O(\log N)[/math], максимальное количество рёбер вне остова не больше [math]N[/math], каждое ребро проверяется за [math]O(\log N)[/math]. Построение LCA и дополнительного массива работает за [math]O(N \log N)[/math], остов мы построим один раз, LCA тоже один раз, каждое ребро мы не больше одного раза проверим на замену, сложность алгоритма [math]O(N \log N)[/math].

См.также

• Остовные деревья: определения, лемма о безопасном ребре

Литература

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