322
правки
Изменения
м
Нет описания правки
==Необходимые определения==
Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Вес ребра определяется, как функция <tex> w : E \to \mathbb{R} </tex>.
{{Определение
|definition =
Ребро <tex> \langle u, v \rangle \in E </tex> '''пересекает разрез''' <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.
}}
==Лемма о безопасном ребре==
{{Теорема
