Изменения
→Необходимые определения
[[Файл: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>.
{{Определение
|id = spanning_tree
|definition =
}}
Заметим, что граф может содержать несколько минимальных остовных деревьев.
Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.
{{Определение
|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=
|proof=
}}
==Cм. также==
*[[Алгоритм Прима]]
*[[Алгоритм Краскала]]
*[[Алгоритм Борувки]]
==Источники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ : Вильямс, 2-е издание, 2005, С. 644-649
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья]]
[[Категория: Построение остовных деревьев]]