Комбинаторные алгоритмы для программистов


Остовные деревья


Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом. В связном неориентированном графе

G
существует по крайней мере один путь между каждой парой вершин; отсутствие циклов в
G
означает, что существует самое большее один такой путь между любой парой вершин в
G
. Поэтому, если
G
- дерево, то между каждой парой вершин в
G
существует в точности один путь. Рассуждение легко обратимо, и поэтому неориентированный граф
G
будет деревом тогда и только тогда, если между каждой парой вершин в
G
существует в точности один путь. Так как наименьшее число ребер, которыми можно соединить
n
вершин, равно
n - 1
и дерево с
n
вершинами содержит в точности
n - 1
ребер, то деревья можно считать минимально связными графами. Удаление из дерева любого ребра превращает его в несвязный граф, разрушая единственный путь между по крайней мере одной парой вершин.

Особый интерес представляют остовные деревья графа

G
, то есть деревья, являющиеся подграфами графа
G
и содержащие все его вершины. Если граф
G
несвязен, то множество, состоящее из остовных деревьев каждой компоненты называется остовном лесом графа. Для построения остовного дерева (леса) данного неориентированного графа
G
, мы последовательно просматриваем ребра
G
, оставляя те, которые не образуют циклов с уже выбранными.

Во взвешенном графе

G = (V,E)
часто интересно определить остовное дерево (лес) с минимальным общим весом ребер, то есть дерево (лес), у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом оставных деревьев или минимальное остовное дерево. Другими словами, на каждом шаге мы выбираем новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжаем до тех пор, пока не будет выбрано
\left| V \right| - 1
ребер, образующих остовное дерево
T
. Этот процесс известен как жадный алгоритм.

Жадный алгоритм может быть выполнен в два этапа. Сначала ребра сортируются по весу и затем строится остовное дерево путем выбора наименьших из имеющихся в распоряжении ребер.

Существует другой метод получения минимума остовных деревьев, который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, - так называемый алгоритм ближайшего соседа.


Начало  Назад  Вперед



Книжный магазин