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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма о безопасном ребре)
Строка 7: Строка 7:
 
}}
 
}}
  
==Безопасное ребро==
+
==Вспомогательные определения==
Пусть <tex> A </tex> - подмножество некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>.
+
Пусть <tex>A</tex> - подмножество некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
 
Ребро <tex> (u, v) \notin A </tex> называется '''безопасным''', если при добавлении его в <tex> A </tex>, <tex> A </tex> остается подмножеством некоторого минимального остовного дерева графа <tex> G </tex>.
 
Ребро <tex> (u, v) \notin A </tex> называется '''безопасным''', если при добавлении его в <tex> A </tex>, <tex> A </tex> остается подмножеством некоторого минимального остовного дерева графа <tex> G </tex>.
 
}}
 
}}
 
==Разрез==
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
 
'''Разрезом''' неориентированного графа <tex> G = (V, E) </tex> называется разбиение <tex> V </tex> на два подмножества: <tex> S </tex> и <tex> V \setminus S </tex>. Обозначается как <tex> (S, V \setminus S) </tex>.
 
'''Разрезом''' неориентированного графа <tex> G = (V, E) </tex> называется разбиение <tex> V </tex> на два подмножества: <tex> S </tex> и <tex> V \setminus S </tex>. Обозначается как <tex> (S, V \setminus S) </tex>.
 
}}
 
}}
 
==Пересечение разреза==
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Мы говорим, что ребро <tex> (u, v) \in E </tex> '''пересекает разрез''' <tex> (S, V \setminus S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> V \setminus S </tex>.
+
Ребро <tex> (u, v) \in E </tex> '''пересекает разрез''' <tex> (S, V \setminus S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> V \setminus S </tex>.
 
}}
 
}}
 
==Согласованность разреза==
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Мы говорим, что разрез '''согласован''' с множеством <tex>A</tex> по ребрам, если ни одно ребро из <tex>A</tex> не пересекает разрез.
+
Разрез '''согласован''' с множеством <tex>A</tex> по ребрам, если ни одно ребро из <tex>A</tex> не пересекает разрез.
 
}}
 
}}
  
==Легкое ребро==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =

Версия 10:57, 24 сентября 2011

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

Дан связный неориентированный граф [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].

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


Вспомогательные определения

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

Определение:
Ребро [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 \setminus S [/math]. Обозначается как [math] (S, V \setminus S) [/math].


Определение:
Ребро [math] (u, v) \in E [/math] пересекает разрез [math] (S, V \setminus S) [/math], если один из его концов оказывается в множестве [math] S [/math], а другой в множестве [math] V \setminus 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 \setminus S) [/math] - разрез [math] G [/math], согласованный с [math] A [/math] по ребрам, а [math] (u, v) [/math] - легкое ребро, пересекающее разрез [math] (S, V \setminus 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 \setminus 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 \setminus 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]

Литература

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