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

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

Дан связный неориентированный граф [math] G = (V, E) [/math], где [math]\ V [/math] - множество вершин, [math]\ E [/math] - множество ребер. Для каждого ребра [math]\ e \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]\triangleleft[/math]