Остовные деревья
Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом. В связном неориентированном графе
существует по крайней мере один путь между каждой парой вершин; отсутствие циклов в
означает, что существует самое большее один такой путь между любой парой вершин в
. Поэтому, если
- дерево, то между каждой парой вершин в
существует в точности один путь. Рассуждение легко обратимо, и поэтому неориентированный граф
будет деревом тогда и только тогда, если между каждой парой вершин в
существует в точности один путь. Так как наименьшее число ребер, которыми можно соединить
вершин, равно
и дерево с
вершинами содержит в точности
ребер, то деревья можно считать минимально связными графами. Удаление из дерева любого ребра превращает его в несвязный граф, разрушая единственный путь между по крайней мере одной парой вершин.
Особый интерес представляют остовные деревья графа
, то есть деревья, являющиеся подграфами графа
и содержащие все его вершины. Если граф
несвязен, то множество, состоящее из остовных деревьев каждой компоненты называется остовном лесом графа. Для построения остовного дерева (леса) данного неориентированного графа
, мы последовательно просматриваем ребра
, оставляя те, которые не образуют циклов с уже выбранными.
Во взвешенном графе
часто интересно определить остовное дерево (лес) с минимальным общим весом ребер, то есть дерево (лес), у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом оставных деревьев или минимальное остовное дерево. Другими словами, на каждом шаге мы выбираем новое ребро с наименьшим весом (наименьшее ребро), не образующее циклов с уже выбранными ребрами; этот процесс продолжаем до тех пор, пока не будет выбрано
ребер, образующих остовное дерево
. Этот процесс известен как жадный алгоритм.
Жадный алгоритм может быть выполнен в два этапа. Сначала ребра сортируются по весу и затем строится остовное дерево путем выбора наименьших из имеющихся в распоряжении ребер.
Существует другой метод получения минимума остовных деревьев, который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, - так называемый алгоритм ближайшего соседа.
Мы начинаем с некоторой произвольной вершины
в заданном графе. Пусть
- ребро с наименьшим весом, инцидентное
; ребро
включается в дерево. Затем среди всех ребер, инцидентных либо
, либо
, выбираем ребро с наименьшим весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, например,
. Повторяя процесс, ищем наименьшее ребро, соединяющее
,
или
с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из
не будут включены в дерево, то есть пока дерево не станет остовным.
Наихудшим для этого алгоритма будет случай, когда
- полный граф (то есть когда каждая пара вершин в графе соединена ребром); в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро, мы сравниваем веса всех
ребер, инцидентных вершине
, и выбираем наименьшее; этот шаг требует
сравнений. Для выбора второго ребра мы ищем наименьшее среди возможных
ребер (инцидентных
или
) и делаем для этого
сравнений. Таким образом, ясно, что для выбора
-го ребра требуется
сравнений, и поэтому в сумме потребуется
сравнений для построения минимума остовных деревьев.
Содержание раздела
