73
правки
Изменения
→Необходимые определения
Заметим, что граф может содержать несколько минимальных остовных деревьев.
Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.
{{Определение
|definition =
Пусть <tex>G'</tex> {{---}} подграф некоторого минимального остовного дерева графа <tex> G = \langle V, E \rangle </tex>.
Ребро <tex> \langle u, v \rangle \notin G' </tex> называется '''безопасным''', если при добавлении его в <tex> G' </tex>, <tex> G' \cup \{ \langle u, v \rangle \}</tex> также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.
