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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Легкое ребро)
(Лемма о безопасном ребре)
Строка 42: Строка 42:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <tex>\ G = (V, E) </tex> - связный неориентированный граф с действительной весовой функцией <tex> w </tex>, определенной на <tex> E </tex>. Пусть <tex> A </tex> - подмножество <tex> E </tex>, которое входит в некоторое минимальное остовное дерево графа <tex> G </tex>; <tex> (S, V - S) </tex> - разрез <tex> G </tex>, согласованный с <tex> A </tex> по ребрам, а <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V - S) </tex>. Тогда ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>.
+
Пусть <tex>\ G = (V, E) </tex> - связный неориентированный граф с действительной весовой функцией <tex> w </tex>, определенной на <tex> E </tex>. Пусть <tex> A </tex> - подмножество <tex> E </tex>, которое входит в некоторое минимальное остовное дерево графа <tex> G </tex>; <tex> (S, V \setminus S) </tex> - разрез <tex> G </tex>, согласованный с <tex> A </tex> по ребрам, а <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V \setminus S) </tex>. Тогда ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>.
 
|proof=
 
|proof=
 
   Пусть <tex> T </tex> - минимальное остовное дерево, которое включает в себя <tex> A </tex>. Предположим, что <tex> T </tex> не содержит ребро <tex> (u, v) </tex>, поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево  <tex> T^* </tex>, которое включает <tex> A \cup {(u, v)} </tex>, путем использования метода вырезания и вставки, показывая таким образом, что ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>. <br>
 
   Пусть <tex> T </tex> - минимальное остовное дерево, которое включает в себя <tex> A </tex>. Предположим, что <tex> T </tex> не содержит ребро <tex> (u, v) </tex>, поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево  <tex> T^* </tex>, которое включает <tex> A \cup {(u, v)} </tex>, путем использования метода вырезания и вставки, показывая таким образом, что ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>. <br>
При добавлении ребро <tex> (u, v) </tex> образует цикл с ребрами на пути <tex> p </tex> от <tex> u </tex> к <tex> v </tex> в минимальном остовном дереве <tex> T </tex>. Так как вершины <tex> u </tex> и <tex> v </tex> находятся на разных сторонах разреза <tex> (S, V - S) </tex>, то на пути <tex> p </tex> имеется как минимум одно ребро из <tex> T </tex>, которое пересекает разрез. Пусть таким ребром является ребро <tex> (x, y) </tex>. Ребро <tex> (x, y) </tex> не входит в <tex> A </tex>, поскольку разрез согласован с <tex> A </tex> по ребрам. Так как <tex> (x, y) </tex> является единственным путем от <tex> u </tex> к <tex> v </tex> в <tex> T </tex>, то его удаление разбивает <tex> T </tex> на две компоненты. Добавление ребра <tex> (u, v) </tex> восстанавливает разбиение, образуя новое остовное дерево <tex> T^* </tex>. Покажем, что <tex> T^* </tex> - минимальное остовное дерево. Поскольку <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V - S) </tex>, и <tex> (x, y) </tex> тоже пересекает этот разрез, то <tex> w(u, v) \le w(x, y) </tex>. Следовательно, <tex> w(T^*) = w(T) - w(x, y) + w(u, v) \le w(T) </tex>. Но <tex> T </tex> - минимальное остовное дерево, так что <tex> w(T) \le w(T^*) </tex>. Значит <tex> T^* </tex> также должно быть минимальным остовным деревом. <br>
+
При добавлении ребро <tex> (u, v) </tex> образует цикл с ребрами на пути <tex> p </tex> от <tex> u </tex> к <tex> v </tex> в минимальном остовном дереве <tex> T </tex>. Так как вершины <tex> u </tex> и <tex> v </tex> находятся на разных сторонах разреза <tex> (S, V \setminus S) </tex>, то на пути <tex> p </tex> имеется как минимум одно ребро из <tex> T </tex>, которое пересекает разрез. Пусть таким ребром является ребро <tex> (x, y) </tex>. Ребро <tex> (x, y) </tex> не входит в <tex> A </tex>, поскольку разрез согласован с <tex> A </tex> по ребрам. Так как <tex> (x, y) </tex> является единственным путем от <tex> u </tex> к <tex> v </tex> в <tex> T </tex>, то его удаление разбивает <tex> T </tex> на две компоненты. Добавление ребра <tex> (u, v) </tex> восстанавливает разбиение, образуя новое остовное дерево <tex> T^* </tex>. Покажем, что <tex> T^* </tex> - минимальное остовное дерево. Поскольку <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V \setminus S) </tex>, и <tex> (x, y) </tex> тоже пересекает этот разрез, то <tex> w(u, v) \le w(x, y) </tex>. Следовательно, <tex> w(T^*) = w(T) - w(x, y) + w(u, v) \le w(T) </tex>. Но <tex> T </tex> - минимальное остовное дерево, так что <tex> w(T) \le w(T^*) </tex>. Значит <tex> T^* </tex> также должно быть минимальным остовным деревом. <br>
 
Покажем, что <tex> (u, v) </tex> действительно безопасное ребро для <tex> A </tex>. Мы имеем <tex> A \subseteq T^* </tex>, поскольку <tex> A \subseteq T </tex> и <tex> (x, y) \notin A </tex>. Таким образом, <tex> A \cup {(u, v)} \subseteq T^* </tex> и, поскольку <tex> T^* </tex> - минимальное остовное дерево, ребро <tex> (u, v) </tex> безопасно для <tex> A </tex>.  
 
Покажем, что <tex> (u, v) </tex> действительно безопасное ребро для <tex> A </tex>. Мы имеем <tex> A \subseteq T^* </tex>, поскольку <tex> A \subseteq T </tex> и <tex> (x, y) \notin A </tex>. Таким образом, <tex> A \cup {(u, v)} \subseteq T^* </tex> и, поскольку <tex> T^* </tex> - минимальное остовное дерево, ребро <tex> (u, v) </tex> безопасно для <tex> A </tex>.  
 
}}
 
}}

Версия 08:36, 21 января 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]

Литература

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