Изменения

Ребро <tex> \langle ( u, v \rangle ) \notin G' </tex> называется '''безопасным''' (англ. ''safe edge''), если при добавлении его в <tex> G' </tex>, <tex> G' \cup \{ \langle ( u, v \rangle ) \}</tex> также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.

Ребро <tex> \langle ( u, v \rangle ) \in E </tex> '''пересекает''' (англ. ''crosses'') разрез <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.

Рассмотрим связный неориентированный взвешенный граф <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> \langle ( u, v \rangle ) </tex> {{---}} ребро минимального веса среди всех ребер, пересекающих разрез <tex> \langle S, T \rangle </tex>. Тогда ребро <tex> e = \langle ( u, v \rangle ) </tex> является безопасным для <tex> G'</tex>.