271
правка
Изменения
Нет описания правки
Мы говорим, что ребро <tex> (u, v) \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) </tex>.
}}
==Согласованность разреза==
{{Определение
|definition =
Мы говорим, что разрез согласован с множеством <tex> A </tex> по ребрам, если ни одно ребро из <tex> A </tex> не пересекает разрез.
}}
==Легкое ребро==
{{Определение
|definition =
Ребро, пересекающее разрез, является легким, если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
}}
Заметим, что может быть несколько легких ребер одновременно.
