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

Минимальное остовное дерево

Дан связный неориентированный граф [math] G = (V, E) [/math], где [math]\ V [/math] - множество вершин, [math]\ E [/math] - множество ребер. Для каждого ребра [math]\ (u, v) \in E [/math] задана весовая функция [math]\ w(u, v) [/math], которая определяет стоимость перехода из [math]\ u [/math] в [math]\ v [/math].

Определение:

Минимальным остовным деревом(как вариант MST) графа [math] G = (V, E) [/math] называется ациклическое подмножество [math] T \subseteq E [/math], которое соединяется все вершины [math] G [/math] и чей общий вес минимален. Граф может содержать несколько минимальных остовных деревьев.

Безопасное ребро

Пусть [math] A [/math] - подмножество некоторого минимального остовного дерева графа [math] G = (V, E) [/math], которое мы хотим полностью достроить до MST.

Определение:

Ребро [math] (u, v) \notin A [/math] называется безопасным, если при добавлении его в [math] A [/math], [math] A [/math] остается подмножеством некоторого минимального остовного дерева графа [math] G [/math].

Разрез

Определение:

Разрезом неориентированного графа [math] G = (V, E) [/math] называется разбиение [math] V [/math] на два подмножества: [math] S [/math] и [math] V - S [/math]. Обозначается как [math] (S, V - S) [/math].

Пересечение разреза

Определение:

Мы говорим, что ребро [math] (u, v) \in E [/math] пересекает разрез [math] (S, V - S) [/math], если один из его концов оказывается в множестве [math] S [/math], а другой в множестве [math] (V - S) [/math].

Согласованность разреза

Определение:

Мы говорим, что разрез согласован с множеством [math] A [/math] по ребрам, если ни одно ребро из [math] A [/math] не пересекает разрез.

Легкое ребро

Определение:

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

Заметим, что может быть несколько легких ребер одновременно.

Лемма о безопасном ребре

Теорема:

Пусть [math]\ G = (V, E) [/math] - связный неориентированный граф с действительной весовой функцией [math] w [/math], определенной на [math] E [/math]. Пусть [math] A [/math] - подмножество [math] E [/math], которое входит в некоторое минимальное остовное дерево графа [math] G [/math]; [math] (S, V - S) [/math] - разрез [math] G [/math], согласованный с [math] A [/math] по ребрам, а [math] (u, v) [/math] - легкое ребро, пересекающее разрез [math] (S, V - S) [/math]. Тогда ребро [math] (u, v) [/math] является безопасным для [math] A [/math].

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

[math]\triangleright[/math]

Пусть [math] T [/math] - минимальное остовное дерево, которое включает в себя [math] A [/math]. Предположим, что [math] T [/math] не содержит ребро [math] (u, v) [/math], поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево [math] T^* [/math], которое включает [math] A \cup {(u, v)} [/math], путем использования метода вырезания и вставки, показывая таким образом, что ребро [math] (u, v) [/math] является безопасным для [math] A [/math]. При добавлении ребро [math] (u, v) [/math] образует цикл с ребрами на пути [math] p [/math] от [math] u [/math] к [math] v [/math] в минимальном остовном дереве [math] T [/math]. Так как вершины [math] u [/math] и [math] v [/math] находятся на разных сторонах разреза [math] (S, V - S) [/math], то на пути [math] p [/math] имеется как минимум одно ребро из [math] T [/math], которое пересекает разрез. Пусть таким ребром является ребро [math] (x, y) [/math]. Ребро [math] (x, y) [/math] не входит в [math] A [/math], поскольку разрез согласован с [math] A [/math] по ребрам. Так как [math] (x, y) [/math] является единственным путем от [math] u [/math] к [math] v [/math] в [math] T [/math], то его удаление разбивает [math] T [/math] на две компоненты. Добавление ребра [math] (u, v) [/math] восстанавливает разбиение, образуя новое остовное дерево [math] T^* [/math]. Покажем, что [math] T^* [/math] - минимальное остовное дерево. Поскольку [math] (u, v) [/math] - легкое ребро, пересекающее разрез [math] (S, V - S) [/math], и [math] (x, y) [/math] тоже пересекает этот разрез, то [math] w(u, v) \le w(x, y) [/math]. Следовательно, [math] w(T^*) = w(T) - w(x, y) + w(u, v) \le w(T) [/math]. Но [math] T [/math] - минимальное остовное дерево, так что [math] w(T) \le w(T^*) [/math]. Значит [math] T^* [/math] также должно быть минимальным остовным деревом. Покажем, что [math] (u, v) [/math] действительно безопасное ребро для [math] A [/math]. Мы имеем [math] A \subseteq T^* [/math], поскольку [math] A \subseteq T [/math] и [math] (x, y) \notin A [/math]. Таким образом, [math] A \cup {(u, v)} \subseteq T^* [/math] и, поскольку [math] T^* [/math] - минимальное остовное дерево, ребро [math] (u, v) [/math] безопасно для [math] A [/math].

[math]\triangleleft[/math]

Литература

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