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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 25: Строка 25:
 
Мы говорим, что ребро <tex> (u, v) \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) </tex>.
 
Мы говорим, что ребро <tex> (u, v) \in E </tex> пересекает разрез <tex> (S, V - S) </tex>, если один из его концов оказывается в множестве <tex> S </tex>, а другой в множестве <tex> (V - S) </tex>.
 
}}
 
}}
 +
 +
==Согласованность разреза==
 +
{{Определение
 +
|definition =
 +
Мы говорим, что разрез согласован с множеством <tex> A </tex> по ребрам, если ни одно ребро из <tex> A </tex> не пересекает разрез.
 +
}}
 +
 +
==Легкое ребро==
 +
{{Определение
 +
|definition =
 +
Ребро, пересекающее разрез, является легким, если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
 +
}}
 +
Заметим, что может быть несколько легких ребер одновременно.

Версия 02:37, 8 декабря 2010

Минимальное остовное дерево

Дан связный неориентированный граф [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].


Разрез

Определение:
Разрезом неориентированного графа [math] G = (V, E) [/math] называется разбиение [math] V [/math] на два подмножества: [math] S [/math] и [math] V - S [/math]. Обозначается как [math] (S, V - S) [/math].


Пересечение разреза

Определение:
Мы говорим, что ребро [math] (u, v) \in E [/math] пересекает разрез [math] (S, V - S) [/math], если один из его концов оказывается в множестве [math] S [/math], а другой в множестве [math] (V - S) [/math].


Согласованность разреза

Определение:
Мы говорим, что разрез согласован с множеством [math] A [/math] по ребрам, если ни одно ребро из [math] A [/math] не пересекает разрез.


Легкое ребро

Определение:
Ребро, пересекающее разрез, является легким, если оно имеет минимальный вес среди всех ребер, пересекающих разрез.

Заметим, что может быть несколько легких ребер одновременно.