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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
==Минимальное остовное дерево==
+
==Необходимые определения==
Дан связный неориентированный [[Основные определения теории графов|граф]] <tex> G = (V, E) </tex>, где <tex>\ V </tex> - множество [[Основные определения теории графов|вершин]], <tex>\ E </tex> - множество [[Основные определения теории графов|ребер]]. Для каждого ребра <tex>\ (u, v) \in E </tex> задана весовая функция <tex>\ w(u, v) </tex>, которая определяет стоимость перехода из <tex>\ u </tex> в <tex>\ v </tex>.
+
Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Вес ребра определяется, как <tex> w : E \to \mathbb{R} </tex>.  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Минимальным остовным деревом''' (англ. '''Minimum spanning tree''') графа <tex> G = (V, E) </tex> называется ациклическое подмножество <tex> T \subseteq E </tex>, которое соединяет все вершины <tex> G </tex> и чей общий вес минимален. <br>
+
'''Минимальным остовным деревом''' (англ. '''Minimum spanning tree''') графа <tex> G = \langle V, E \rangle </tex> называется его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
Граф может содержать несколько минимальных остовных деревьев.
 
 
}}
 
}}
 
+
Заметим, что граф может содержать несколько минимальных остовных деревьев.
==Вспомогательные определения==
+
Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.
Пусть <tex>A</tex> - подмножество некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>.
+
Пусть <tex>G'</tex> {{---}} подграф некоторого минимального остовного дерева графа <tex> G = \langle V, E \rangle </tex>.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Ребро <tex> (u, v) \notin A </tex> называется '''безопасным''', если при добавлении его в <tex> A </tex>, <tex> A </tex> остается подмножеством некоторого минимального остовного дерева графа <tex> G </tex>.
+
Ребро <tex> \langle u, v \rangle \notin G' </tex> называется '''безопасным''', если при добавлении его в <tex> G' </tex>, <tex> G' \cup \{ \langle u, v \rangle \}</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 = \langle V, E \rangle </tex> называется разбиение <tex> V </tex> на два непересекающихся подмножества: <tex> S </tex> и <tex> T = V \setminus S </tex>. Обозначается как <tex> \langle S, T \rangle </tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Ребро <tex> (u, v) \in E </tex> '''пересекает разрез''' <tex> (S, V \setminus S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> V \setminus S </tex>.
+
Ребро <tex> \langle u, v \rangle \in E </tex> '''пересекает разрез''' <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Разрез '''согласован''' с множеством <tex>A</tex> по ребрам, если ни одно ребро из <tex>A</tex> не пересекает разрез.
+
Разрез '''согласован''' с множеством <tex> E' \subset E </tex> по ребрам, если ни одно ребро из <tex> E'</tex> не пересекает разрез.
 
}}
 
}}
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Ребро, пересекающее разрез, является '''легким''', если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
+
Ребро, пересекающее разрез, называется '''легким''', если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
 
}}
 
}}
Заметим, что может быть несколько легких ребер одновременно.
 
 
 
==Лемма о безопасном ребре==
 
==Лемма о безопасном ребре==
 
{{Теорема
 
{{Теорема
 
|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 \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>.
+
Рассмотрим связный неориентированный взвешенный граф <tex> G = \langle V, E \rangle </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex> Пусть <tex> G' = \langle V, E' \rangle </tex> {{---}} подграф некоторого минимального остовного дерева <tex> G </tex>. <tex> \langle S, T \rangle </tex> {{---}} разрез <tex> G </tex>, согласованный с <tex> E' </tex> по ребрам, а <tex> \langle u, v \rangle </tex> {{---}} легкое ребро, пересекающее разрез <tex> \langle S, T \rangle </tex>. Тогда ребро <tex> e = \langle u, v \rangle </tex> является безопасным для <tex> G'</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> E' </tex> до некоторого минимального остовного дерева, обозначим его <tex>T_{min}</tex>. Если ребро <tex>e \in T_{min}</tex>, то лемма доказана, поэтому рассмотрим случай, когда ребро <tex>e \notin T_{min}</tex>. Рассмотрим путь в <tex>T_{min}</tex> от вершины <tex>u</tex> до вершины <tex>v</tex>. Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его <tex>e'</tex>. По условию леммы <tex>w(e) \le w(e')</tex>. Заменим ребро <tex>e</tex> в <tex>T_{min}</tex> на ребро <tex>e'</tex>. Полученное дерево также является минимальным остовным деревом графа <tex>G</tex>, поскольку все вершины <tex>G</tex> по-прежнему связаны и вес дерева не увеличился. Следовательно <tex>E' \cup \{e\} </tex> можно дополнить до минимального остовного дерева в графе <tex>G</tex>, то есть ребро <tex>e</tex> {{---}} безопасное.
При добавлении ребро <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>.  
 
 
}}
 
}}
 
 
==Литература==
 
==Литература==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. - Алгоритмы. Построение и анализ.
+
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ.
 +
==Cм. также==
 +
*[[Алгоритм Прима]]
 +
*[[Алгоритм Краскала]]

Версия 01:12, 5 декабря 2011

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

Рассмотрим связный неориентированный взвешенный граф [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] E' \subset E [/math] по ребрам, если ни одно ребро из [math] E'[/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м. также