322
правки
Изменения
Нет описания правки
}}
==Безопасное реброВспомогательные определения==Пусть <tex> A </tex> - подмножество некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>.
{{Определение
|definition =
Ребро <tex> (u, v) \notin A </tex> называется '''безопасным''', если при добавлении его в <tex> A </tex>, <tex> A </tex> остается подмножеством некоторого минимального остовного дерева графа <tex> G </tex>.
}}
{{Определение
|definition =
'''Разрезом''' неориентированного графа <tex> G = (V, E) </tex> называется разбиение <tex> V </tex> на два подмножества: <tex> S </tex> и <tex> V \setminus S </tex>. Обозначается как <tex> (S, V \setminus S) </tex>.
}}
{{Определение
|definition =
}}
{{Определение
|definition =
}}
{{Определение
|definition =
