Участник:Savelin - История изменений

Savelin: /* Cм. также */

2015-01-10T08:04:56Z

‎Cм. также

Savelin: /* Необходимые определения */

2015-01-10T08:04:34Z

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

Savelin в 18:57, 25 декабря 2014

2014-12-25T18:57:39Z

Savelin: /* Лемма о безопасном ребре */

2014-12-25T18:49:43Z

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

Savelin: /* Лемма о безопасном ребре */

2014-12-25T18:46:55Z

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

Savelin: /* Необходимые определения */

2014-12-25T18:43:36Z

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

Savelin: /* Литература */

2014-12-25T18:41:24Z

‎Литература

Savelin: /* Необходимые определения */

2014-12-25T18:39:58Z

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

Savelin: /* Необходимые определения */

2014-12-25T18:39:03Z

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

Savelin: /* Необходимые определения */

2014-12-25T18:37:23Z

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

@@ Строка 29: / Строка 29: @@
 *[[Алгоритм Прима]]
 *[[Алгоритм Краскала]]
 ==Источники информации==

@@ Строка 3: / Строка 3: @@
 {{Определение
 |definition =
-'''Минимальное остовное дерево'''  графа <tex> G = \langle V, E \rangle </tex> (англ. ''minimum spanning tree'') {{---}} это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
+'''Минимальное остовное дерево''' (англ. ''minimum spanning tree'') графа <tex> G = \langle V, E \rangle </tex>  {{---}} это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
 }}
 Заметим, что граф может содержать несколько минимальных остовных деревьев.

@@ Строка 25: / Строка 25: @@
 Достроим <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м. также==
 *[[Алгоритм Прима]]
 *[[Алгоритм Краскала]]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]

@@ Строка 22: / Строка 22: @@
 Рассмотрим связный неориентированный взвешенный граф <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|400px]]
+[[Файл:Лемма_о_безопасном_ребре.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> {{---}} безопасное.
 }}

@@ Строка 23: / Строка 23: @@
 |proof=
 [[Файл:Лемма_о_безопасном_ребре.png‎|right|thumb|400px]]
-Достроим <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) \le 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> {{---}} безопасное.
 }}

@@ Строка 12: / Строка 12: @@
 Ребро <tex> \langle u, v \rangle \notin G' </tex> называется '''безопасным''', если при добавлении его в <tex> G' </tex>, <tex> G' \cup \{ \langle u, v \rangle \}</tex> также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.
-'''Разрезом''' неориентированного графа <tex> G = \langle V, E \rangle </tex> называется разбиение <tex> V </tex> на два непересекающихся подмножества: <tex> S </tex> и <tex> T = V \setminus S </tex>.  Обозначается как <tex> \langle S, T \rangle </tex>.
+'''Разрезом''' (англ. ''cut'') неориентированного графа <tex> G = \langle V, E \rangle </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>.