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