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

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

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

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

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

[math]\triangleright[/math]

[math] \Rightarrow [/math] Докажем, что остовное дерево, состоящее из ребер наименьшего веса на циклах — минимально. Предположим противное: пусть в остовном дереве [math] A [/math] не все минимальные ребра на циклах, тогда оно минимально. Найдем цикл в графе [math] G [/math], в котором есть ребро [math] (u, v) \notin A[/math], которое легче остальных ребер этого цикла, включая ребро [math] (a, b) \in A[/math]. Следовательно, можно получить остов [math] A' [/math] с меньшим весом, удалив ребро [math] (a, b) [/math] из [math] A [/math], и, добавив вместо него [math] (u, v) [/math]. Поэтому, остовное дерево [math] A [/math] не минимально — противоречие. Теперь, рассмотрим остовное дерево, состоящее из минимальных ребер. Попробуем проделать тоже самое: найти цикл в котором есть пара нужных ребер. Так как остов состоит из ребер наименьшего веса, то таких циклов нет, следовательно его улучшить нельзя, следовательно такое остовное дерево минимально. [math] \Leftarrow [/math] Построим минимальное остовное дерево [math] A [/math], с помощью общего алгоритма построения MST. Докажем, что оно имеет минимальные ребра на каждом цикле. function Generic MST([math] G [/math]): [math] A = \{ \} [/math] while [math] A [/math] не является остовом do найти безопасное ребро [math] ( u, v ) \in E [/math] для [math] A [/math] // нужное ребро находится с помощью леммы о безопасном ребре [math] A = A \cup \{( u, v )\} [/math] return [math] A [/math] Заметим, что дерево [math] A [/math] состоит полностью из безопасных ребер, так как на каждом шаге добавлялось безопасное ребро. Теперь, рассмотрим какой-нибудь разрез [math] (S, T) [/math] уже построенного дерева [math] A [/math] и пересекающее ребро [math] (u, v) [/math], причем [math] u \in S [/math], а [math] v \in T [/math]. Найдем путь в изначальном графе [math] G [/math], соединяющий вершины [math] u [/math] и [math] v [/math]. Так как они находятся в разных компонентах связности, то какое-нибудь ребро [math] (a, b) \notin A[/math] тоже будет пересекать разрез [math] (S, T) [/math]. Очевидно, что [math] w(u, v) \leqslant w(a, b) [/math], так как первое — безопасное ребро. Следовательно, любое ребро [math] \notin A[/math] не легче ребер [math] \in A [/math] на этом цикле.

[math]\triangleleft[/math]

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

Задача:

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

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

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

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

После рассмотрения всех рёбер, если мы не нашли ребро вне остова, при добавлении которого создаётся цикл с максимальным ребром таким же как и на пути [math]u[/math] и [math]v[/math], то в графе нету другого остовного дерева и наше дерево уникально. Искать максимальное ребро на пути [math]u[/math] и [math]v[/math] в дереве мы можем при помощи heavy-light декомпозиции.

Асимптотика

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

См.также

• Остовные деревья: определения, лемма о безопасном ребре
• Минимально узкое остовное дерево
• Алгоритм Краскала
• Алгоритм Борувки
• Алгоритм Прима

Источники информации

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