Изменения

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

Навигация