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

Необходимые определения

Рассмотрим связный неориентированный взвешенный граф [math] G =\langle V, E \rangle [/math], где [math]V [/math] — множество вершин, [math]E [/math] — множество ребер. Вес ребра определяется, как функция [math] w : E \to \mathbb{R} [/math].

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

Минимальным остовным деревом (англ. Minimum spanning tree) графа [math] G = \langle V, E \rangle [/math] называется его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.

Заметим, что граф может содержать несколько минимальных остовных деревьев. Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения. Пусть [math]G'[/math] — подграф некоторого минимального остовного дерева графа [math] G = \langle V, E \rangle [/math].

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

Ребро [math] \langle u, v \rangle \notin G' [/math] называется безопасным, если при добавлении его в [math] G' [/math], [math] G' \cup \{ \langle u, v \rangle \}[/math] также является подграфом некоторого минимального остовного дерева графа [math] G [/math]. Разрезом неориентированного графа [math] G = \langle V, E \rangle [/math] называется разбиение [math] V [/math] на два непересекающихся подмножества: [math] S [/math] и [math] T = V \setminus S [/math]. Обозначается как [math] \langle S, T \rangle [/math]. Ребро [math] \langle u, v \rangle \in E [/math] пересекает разрез [math] \langle S, T \rangle [/math], если один из его концов принадлежит множеству [math] S [/math], а другой — множеству [math] T [/math].

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

Теорема:

Рассмотрим связный неориентированный взвешенный граф [math] G = \langle V, E \rangle [/math] с весовой функцией [math]w : E \to \mathbb{R}[/math]. Пусть [math] G' = \langle V, E' \rangle [/math] — подграф некоторого минимального остовного дерева [math] G [/math], [math] \langle S, T \rangle [/math] — разрез [math] G [/math], такой, что ни одно ребро ни одно ребро из [math] E' [/math] не пересекает разрез, а [math] \langle u, v \rangle [/math] — ребро минимального веса среди всех ребер, пересекающих разрез [math] \langle S, T \rangle [/math]. Тогда ребро [math] e = \langle u, v \rangle [/math] является безопасным для [math] G'[/math].

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

[math]\triangleright[/math]

Достроим [math] E' [/math] до некоторого минимального остовного дерева, обозначим его [math]T_{min}[/math]. Если ребро [math]e \in T_{min}[/math], то лемма доказана, поэтому рассмотрим случай, когда ребро [math]e \notin T_{min}[/math]. Рассмотрим путь в [math]T_{min}[/math] от вершины [math]u[/math] до вершины [math]v[/math]. Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его [math]e'[/math]. По условию леммы [math]w(e) \le w(e')[/math]. Заменим ребро [math]e[/math] в [math]T_{min}[/math] на ребро [math]e'[/math]. Полученное дерево также является минимальным остовным деревом графа [math]G[/math], поскольку все вершины [math]G[/math] по-прежнему связаны и вес дерева не увеличился. Следовательно [math]E' \cup \{e\} [/math] можно дополнить до минимального остовного дерева в графе [math]G[/math], то есть ребро [math]e[/math] — безопасное.

[math]\triangleleft[/math]

Литература

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

Cм. также

• Алгоритм Прима
• Алгоритм Краскала