Остовные деревья: определения, лемма о безопасном ребре — различия между версиями

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

Версия 19:06, 10 февраля 2020

Пример минимального остовного дерева.

Необходимые определения

Рассмотрим связный неориентированный взвешенный граф [math] G =( V, E ) [/math], где [math]V [/math] — множество вершин, [math]E [/math] — множество ребер. Вес ребра определяется, как функция [math] w : E \to \mathbb{R} [/math].

Определение:
Остовное дерево (англ. spanning tree) графа [math] G = ( V, E ) [/math] — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины.
Определение:
Минимальное остовное дерево (англ. minimum spanning tree) графа [math] G = ( V, E ) [/math] — это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.

Заметим, что граф может содержать несколько минимальных остовных деревьев. Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.

Пусть [math]G'[/math] — подграф некоторого минимального остовного дерева графа [math] G = ( V, E ) [/math].

Определение:
Ребро [math] ( u, v ) \notin G' [/math] называется безопасным (англ. safe edge), если при добавлении его в [math] G' [/math], [math] G' \cup \{ ( u, v ) \}[/math] также является подграфом некоторого минимального остовного дерева графа [math] G [/math].
Определение:
Разрезом (англ. cut) неориентированного графа [math] G = ( V, E ) [/math] называется разбиение [math] V [/math] на два непересекающихся подмножества: [math] S [/math] и [math] T = V \setminus S [/math]. Обозначается как [math] \langle S, T \rangle [/math].
Определение:
Ребро [math] ( u, v ) \in E [/math] пересекает (англ. crosses) разрез [math] \langle S, T \rangle [/math], если один из его концов принадлежит множеству [math] S [/math], а другой — множеству [math] T [/math].


Лемма о безопасном ребре

Теорема:
Рассмотрим связный неориентированный взвешенный граф [math] G = ( V, E ) [/math] с весовой функцией [math]w : E \to \mathbb{R}[/math]. Пусть [math] G' = ( V, E' ) [/math] — подграф некоторого минимального остовного дерева [math] G [/math], [math] \langle S, T \rangle [/math] — разрез [math] G [/math], такой, что ни одно ребро из [math] E' [/math] не пересекает разрез, а [math] ( u, v ) [/math] — ребро минимального веса среди всех ребер, пересекающих разрез [math] \langle S, T \rangle [/math]. Тогда ребро [math] e = ( u, v ) [/math] является безопасным для [math] G'[/math].
Доказательство:
[math]\triangleright[/math]
Лемма о безопасном ребре.png
Достроим [math] E' [/math] до некоторого минимального остовного дерева, обозначим его [math]T_{min}[/math]. Если ребро [math]e \in T_{min}[/math], то лемма доказана, поэтому рассмотрим случай, когда ребро [math]e \notin T_{min}[/math]. Рассмотрим путь в [math]T_{min}[/math] от вершины [math]u[/math] до вершины [math]v[/math]. Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его [math]e'[/math]. По условию леммы [math]w(e) \leqslant w(e')[/math]. Заменим ребро [math]e'[/math] в [math]T_{min}[/math] на ребро [math]e[/math]. Полученное дерево также является минимальным остовным деревом графа [math]G[/math], поскольку все вершины [math]G[/math] по-прежнему связаны и вес дерева не увеличился. Следовательно [math]E' \cup \{e\} [/math] можно дополнить до минимального остовного дерева в графе [math]G[/math], то есть ребро [math]e[/math] — безопасное.
[math]\triangleleft[/math]

Cм. также

Источники информации

  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — Алгоритмы. Построение и анализ : Вильямс, 2-е издание, 2005, С. 644-649