Изменения

Перейти к: навигация, поиск
Необходимые определения
[[Файл:MST-example.png|right|thumb|200px|Пример минимального остовного дерева.]]==Минимальное остовное деревоНеобходимые определения==Дан Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G = (V, E) </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>.
{{Определение
|id = spanning_tree
|definition =
Минимальным остовным деревом'''Остовное дерево''' (как вариант MSTангл. ''spanning tree'') графа <tex> G = (V, E) </tex> называется ациклическое подмножество {{---}} ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.}}{{Определение|definition ='''Минимальное остовное дерево''' (англ. ''minimum spanning tree'') графа <tex> T \subseteq G = ( V, E ) </tex> {{---}} это его ациклический связный подграф, которое соединяется в который входят все его вершины <tex> G </tex> и чей общий вес минимален. <br>Граф может содержать несколько минимальных остовных деревьев, обладающий минимальным суммарным весом ребер.
}}
Заметим, что граф может содержать несколько минимальных остовных деревьев.
Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.
==Безопасное ребро==Пусть <tex> A G'</tex> {{- подмножество --}} подграф некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>.
{{Определение
|definition =
Ребро <tex> (u, v) \notin A G' </tex> называется '''безопасным''' (англ. ''safe edge''), если при добавлении его в <tex> A G' </tex>, <tex> A G' \cup \{ ( u, v ) \}</tex> остается подмножеством также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.}} ==Разрез=={{Определение|definition = '''Разрезом ''' (англ. ''cut'') неориентированного графа <tex> G = (V, E) </tex> называется разбиение <tex> V </tex> на два непересекающихся подмножества: <tex> S </tex> и <tex> T = V - \setminus S </tex>. Обозначается как <tex> (\langle S, V - S) </tex>.}} ==Пересечение разреза=={{Определение|definition = Мы говорим, что ребро <tex> (u, v) T \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) rangle </tex>.}} ==Согласованность разреза=={{Определение|definition = Мы говорим, что разрез согласован с множеством <tex> A </tex> по ребрам, если ни одно ребро из <tex> A </tex> не пересекает разрез.}} ==Легкое ребро=={{Определение
|definition =
Ребро<tex> ( u, пересекающее v ) \in E </tex> '''пересекает''' (англ. ''crosses'') разрез<tex> \langle S, является легкимT \rangle </tex>, если оно имеет минимальный вес среди всех реберодин из его концов принадлежит множеству <tex> S </tex>, пересекающих разреза другой {{---}} множеству <tex> T </tex>.
}}
Заметим, что может быть несколько легких ребер одновременно.
==Лемма о безопасном ребре==
{{Теорема
|statement=
Пусть Рассмотрим связный неориентированный взвешенный граф <tex>\ G = (V, E) </tex> - связный неориентированный граф с действительной весовой функцией <tex> w </tex>, определенной на <tex> : E \to \mathbb{R}</tex>. Пусть <tex> A G' = ( V, E' ) </tex> {{--- подмножество }} подграф некоторого минимального остовного дерева <tex> E G </tex>, которое входит в некоторое минимальное остовное дерево графа <tex> G </tex>; <tex> (\langle S, V - S) T \rangle </tex> {{--- }} разрез <tex> G </tex>, согласованный с такой, что ни одно ребро из <tex> A E' </tex> по ребрамне пересекает разрез, а <tex> (u, v) </tex> {{--- легкое }} реброминимального веса среди всех ребер, пересекающее пересекающих разрез <tex> (\langle S, V - S) T \rangle </tex>. Тогда ребро <tex> e = (u, v) </tex> является безопасным для <tex> A G'</tex>.
|proof=
Пусть [[Файл:Лемма_о_безопасном_ребре.png‎|right|thumb|300px]]Достроим <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 - 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 - S) </tex>, и <tex> (x, y) </tex> тоже пересекает этот разрез, то По условию леммы <tex> w(u, ve) \le leqslant 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м. также==*[[Алгоритм Прима]]*[[Алгоритм Краскала]]*[[Алгоритм Борувки]] ==Источники информации==* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{- --}} Алгоритмы. Построение и анализ: Вильямс, 2-е издание, 2005, С.644-649 [[Категория: Алгоритмы и структуры данных]] [[Категория: Остовные деревья]][[Категория: Построение остовных деревьев]]
Анонимный участник

Навигация