Остовные деревья: определения, лемма о безопасном ребре

Дан связный неориентированный граф [math] G = (V, E) [/math], где [math]\ V [/math] - множество вершин, [math]\ E [/math] - множество ребер. Для каждого ребра [math]\ e \in E [/math] задана весовая функция [math]\ w(u, v) [/math], которая определяет стоимость перехода из [math]\ u [/math] в [math]\ v [/math].

Определение:

Минимальным остовным деревом графа(как вариант MST) [math] G = (V, E) [/math] называется ациклическое подмножество [math] T \subseteq E [/math], которое соединяется все вершины [math] G [/math] и чей общий вес минимален. Граф может содержать несколько минимальных остовных деревьев.

Пусть [math] A [/math] - подмножество некоторого минимального остовного дерева графа [math] G = (V, E) [/math], которое мы хотим полностью достроить до MST.

Определение:

Ребро [math] (u, v) \notin A [/math] называется безопасным, если при добавлении его в [math] A [/math], [math] A [/math] остается подмножеством некоторого минимального остовного дерева графа [math] G [/math].