Изменения

==Минимальное остовное деревоНеобходимые определения==Дан Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G = (\langle V, E) \rangle </tex>, где <tex>\ V </tex> {{--- }} множество [[Основные определения теории графов|вершин]], <tex>\ E </tex> {{- --}} множество [[Основные определения теории графов|ребер]]. Для каждого Вес ребра <tex>\ (uопределяется, v) \in E </tex> задана весовая функция как <tex>\ w(u, v) </tex>, которая определяет стоимость перехода из <tex>: E \ u </tex> в <tex>to \ v mathbb{R} </tex>.

'''Минимальным остовным деревом''' (англ. '''Minimum spanning tree''') графа <tex> G = (\langle V, E) \rangle </tex> называется ациклическое подмножество <tex> T \subseteq E </tex>его ациклический связный подграф, которое соединяет в который входят все его вершины <tex> G </tex> и чей общий вес минимален. <br>Граф может содержать несколько минимальных остовных деревьев, обладающий минимальным суммарным весом ребер.

Заметим, что граф может содержать несколько минимальных остовных деревьев. ==Вспомогательные Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения==.Пусть <tex>AG'</tex> {{--- подмножество }} подграф некоторого минимального остовного дерева графа <tex> G = (\langle V, E) \rangle </tex>.

Ребро <tex> (\langle u, v) \rangle \notin A G' </tex> называется '''безопасным''', если при добавлении его в <tex> A G' </tex>, <tex> A G' \cup \{ \langle u, v \rangle \}</tex> остается подмножеством также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.

'''Разрезом''' неориентированного графа <tex> G = (\langle V, E) \rangle </tex> называется разбиение <tex> V </tex> на два непересекающихся подмножества: <tex> S </tex> и <tex> T = V \setminus S </tex>. Обозначается как <tex> (\langle S, V T \setminus S) rangle </tex>.

Ребро <tex> (\langle u, v) \rangle \in E </tex> '''пересекает разрез''' <tex> (\langle S, V T \setminus S) rangle </tex>, если один из его концов оказывается в множестве принадлежит множеству <tex> S </tex>, а другой в множестве {{---}} множеству <tex> V \setminus S T </tex>.

Разрез '''согласован''' с множеством <tex>AE' \subset E </tex> по ребрам, если ни одно ребро из <tex>AE'</tex> не пересекает разрез.

Ребро, пересекающее разрез, является называется '''легким''', если оно имеет минимальный вес среди всех ребер, пересекающих разрез.

Пусть Рассмотрим связный неориентированный взвешенный граф <tex>\ G = (\langle V, E) \rangle </tex> - связный неориентированный граф с вещественной весовой функцией <tex> w </tex>, определенной на <tex> : E \to \mathbb{R}</tex>. Пусть <tex> A G' = \langle V, E' \rangle </tex> {{--- подмножество <tex> E </tex>, которое входит в некоторое минимальное остовное дерево графа }} подграф некоторого минимального остовного дерева <tex> G </tex>; . <tex> (\langle S, V T \setminus S) rangle </tex> {{- --}} разрез <tex> G </tex>, согласованный с <tex> A E' </tex> по ребрам, а <tex> (\langle u, v) \rangle </tex> {{--- }} легкое ребро, пересекающее разрез <tex> (\langle S, V T \setminus S) rangle </tex>. Тогда ребро <tex> (e = \langle u, v) \rangle </tex> является безопасным для <tex> A G'</tex>.

Пусть Достроим <tex> T E' </tex> - минимальное остовное дереводо некоторого минимального остовного дерева, которое включает в себя обозначим его <tex> A T_{min}</tex>. Предположим, что <tex> T </tex> не содержит Если ребро <tex> (u, v) </tex>, поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево <tex> T^* </tex>, которое включает <tex> A e \cup in T_{(u, v)min} </tex>, путем использования метода вырезания и вставкито лемма доказана, показывая таким образомпоэтому рассмотрим случай, что когда ребро <tex> (u, v) </tex> является безопасным для <tex> A e \notin T_{min}</tex>. <br>При добавлении ребро Рассмотрим путь в <tex> (u, v) </tex> образует цикл с ребрами на пути <tex> p T_{min}</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^* e'</tex> - минимальное остовное дерево. Поскольку <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V \setminus S) </tex>, и <tex> (x, y) </tex> тоже пересекает этот разрез, то По условию леммы <tex> w(u, ve) \le w(x, ye') </tex>. Следовательно, Заменим ребро <tex> w(T^*) = w(T) - w(x, y) + w(u, v) \le w(T) e</tex>. Но в <tex> T T_{min}</tex> - минимальное остовное дерево, так что на ребро <tex> w(T) \le w(T^*) e'</tex>. Значит <tex> T^* </tex> Полученное дерево также должно быть является минимальным остовным деревом. <br>Покажем, что <tex> (u, v) </tex> действительно безопасное ребро для <tex> A </tex>. Мы имеем графа <tex> A \subseteq T^* G</tex>, поскольку все вершины <tex> A \subseteq T G</tex> по-прежнему связаны и <tex> (x, y) \notin A </tex>вес дерева не увеличился. Таким образом, Следовательно <tex> A E' \cup \{(u, v)e\} \subseteq T^* </tex> и, поскольку можно дополнить до минимального остовного дерева в графе <tex> T^* G</tex> - минимальное остовное дерево, то есть ребро <tex> (u, v) </tex> безопасно для <tex> A e</tex>{{---}} безопасное.

* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{- --}} Алгоритмы. Построение и анализ.==Cм. также==*[[Алгоритм Прима]]*[[Алгоритм Краскала]]