73
правки
Изменения
→Необходимые определения
==Необходимые определения==
Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G =\langle ( V, E \rangle ) </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Вес ребра определяется, как функция <tex> w : E \to \mathbb{R} </tex>.
{{Определение
|definition =
'''Минимальное остовное дерево''' (англ. ''minimum spanning tree'') графа <tex> G = \langle ( V, E \rangle ) </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>.
'''Разрезом''' (англ. ''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> '''пересекает''' (англ. ''crosses'') разрез <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.
