271
правка
Изменения
Нет описания правки
}}
Заметим, что может быть несколько легких ребер одновременно.
==Лемма о безопасном ребре==
{{Теорема
|statement=
Пусть <tex>\ G = (V, E) </tex> - связный неориентированный граф с действительной весовой функцией <tex> w </tex>, определенной на <tex> E </tex>. Пусть <tex> A </tex> - подмножество <tex> E </tex>, которое входит в некоторое минимальное остовное дерево графа <tex> G </tex>; <tex> (S, V - S) </tex> - разрез <tex> G </tex>, согласованный с <tex> A </tex> по ребрам, а <tex> (u, v) </tex> - легкое ребро, пересекающее разрез <tex> (S, V - S) </tex>. Тогда ребро <tex> (u, v) </tex> является безопасным для <tex> A </tex>.
|proof=
dasdasd
}}
