271
правка
Изменения
Нет описания правки
==Минимальное остовное дерево==
Дан связный неориентированный граф <tex> G = (V, E) </tex>, где <tex>\ V </tex> - множество вершин, <tex>\ E </tex> - множество ребер. Для каждого ребра <tex>\ e \in E </tex> задана весовая функция <tex>\ w(u, v) </tex>, которая определяет стоимость перехода из <tex>\ u </tex> в <tex>\ v </tex>.
{{Определение
|definition =
Минимальным остовным деревом графа(как вариант MST) графа <tex> G = (V, E) </tex> называется ациклическое подмножество <tex> T \subseteq E </tex>, которое соединяется все вершины <tex> G </tex> и чей общий вес минимален. <br>
Граф может содержать несколько минимальных остовных деревьев.
}}
==Безопасное ребро==
Пусть <tex> A </tex> - подмножество некоторого минимального остовного дерева графа <tex> G = (V, E) </tex>, которое мы хотим полностью достроить до MST.
{{Определение
|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 - S </tex>. Обозначается как <tex> (S, V - S) </tex>.
}}
==Пересечение разреза==
{{Определение
|definition =
Мы говорим, что ребро <tex> (u, v) \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) </tex>.
}}
