Изменения

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

Минимальным остовным деревом'''Остовное дерево''' (как вариант 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>, которое мы хотим полностью достроить до MST.

Ребро <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, T \rangle </tex>.}}{{Определение|definition =Ребро <tex> ( u, v ) \in E </tex> '''пересекает''' (англ. ''crosses'') разрез <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.

==РазрезЛемма о безопасном ребре=={{ОпределениеТеорема|definition statement= Разрезом неориентированного графа Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E) </tex> называется разбиение с весовой функцией <tex> w : E \to \mathbb{R}</tex>. Пусть <tex> G' = ( V , E' ) </tex> {{---}} подграф некоторого минимального остовного дерева <tex> G </tex> на два подмножества: , <tex> \langle S , T \rangle </tex> {{---}} разрез <tex> G </tex>, такой, что ни одно ребро из <tex> E' </tex> и не пересекает разрез, а <tex> ( u, v ) </tex> V {{--- }} ребро минимального веса среди всех ребер, пересекающих разрез <tex> \langle S , T \rangle </tex>. Обозначается Тогда ребро <tex> e = ( u, v ) </tex> является безопасным для <tex> G'</tex>.|proof=[[Файл:Лемма_о_безопасном_ребре.png‎|right|thumb|300px]]Достроим <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) \leqslant w(Se')</tex>. Заменим ребро <tex>e'</tex> в <tex>T_{min}</tex> на ребро <tex>e</tex>. Полученное дерево также является минимальным остовным деревом графа <tex>G</tex>, V поскольку все вершины <tex>G</tex> по- S) прежнему связаны и вес дерева не увеличился. Следовательно <tex>E' \cup \{e\} </tex> можно дополнить до минимального остовного дерева в графе <tex>G</tex>, то есть ребро <tex>e</tex>{{---}} безопасное.

==Пересечение разрезаCм. также=={{Определение|definition = *[[Алгоритм Прима]]Мы говорим, что ребро <tex> (u, v) \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) </tex>.*[[Алгоритм Краскала]]}}*[[Алгоритм Борувки]]

==Согласованность разрезаИсточники информации==* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{Определение|definition = Мы говорим---}} Алгоритмы. Построение и анализ : Вильямс, 2-е издание, что разрез согласован с множеством <tex> A </tex> по ребрам2005, если ни одно ребро из <tex> A </tex> не пересекает разрезС.}}644-649