2.3. Алгоритмы построения деревьев

Очень часто при решении прикладных задач возникает проблема построения кратчайшего связывающего или остовного дерева для данного взвешенного графа, то есть графа, ребрам которого приписаны некоторые весовые коэффициенты.

Эта задача возникает при проектировании линий электропередач, трубопроводов, дорог и т.п., когда требуется данные центры соединить каналами связи так, чтобы два центра были связаны либо непосредственно каналом, либо через другие центры и каналы и чтобы длина каналов связи была минимальна. Центры в этой задаче – это вершины, а каналы связи – это рёбра с заданными длинами (или весами). Тогда искомая сеть будет кратчайшим остовным подграфом, который является деревом. Вообще, деревья используются в прикладных задачах, решение которых заключается в установлении связей между объектами кратчайшим образом. Кроме того, деревья применяются в задачах трассировки печатных плат, при моделировании иерархических структур.

Примеры:

1. Несколько городов связаны между собой сетью автомобильных дорог, качество которых не является идеальным. Для перевозки ценных грузов необходимо для каждой пары городов наличие по крайней мере одной хорошей дороги между ними. Стоимость ремонта покрытия одного километра каждой дороги известна. Покрытие каких дорог требуется усилить, чтобы затраты на ремонт всех дорог были минимальны?

2. Несколько населенных пунктов требуется связать друг с другом сетью телефонных линий. Известна стоимость прокладки линии между двумя любыми пунктами. Где следует проложить линии, чтобы затраты были минимальными?

3. Информационно-вычислительная сеть связывает между собой вычислительные центры нескольких предприятий. Ввиду большого объема потока информации и ограниченной надежности некоторые линии сети могут оказаться блокированными. Для проведения телеконференций необходимо, чтобы каждые два предприятия могли связаться друг с другом. Как в произвольный момент времени определить, возможна ли организация такой связи?

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

Поскольку полный граф G_N имеет число остовов N^N-2, то решение задачи путём перебора всех вариантов требует больших вычислений. Однако, для произвольного связного графа существует несколько алгоритмов, позволяющих эффективно решить данную задачу.

Пусть G=< V, U > – неориентированный граф с N вершинами, {a_ij} – матрица весов ребер, которые в данном случае будем называть длинами ребер, a_ij=, если ребра между вершинами i и j нет, a_ii=0. Следует отметить, что во многих случаях понятие длины ребра является чисто условным: числа {a_ij} могут, вообще говоря, быть отрицательными и не подчиняться неравенству треугольника. Основная идея рассматриваемого ниже алгоритма построения кратчайшего связывающего (покрывающего) дерева состоит в следующем. Просматриваются ребра графа в порядке возрастания их длин и для каждого ребра принимается решение, будет ли оно включено в строящееся дерево. Если ребро образует контур с ранее включенными ребрами, то оно не может входить в дерево, в противном случае оно включается в дерево. Таким образом, множество включенных ребер образует лес, их количество возрастает. Процесс заканчивается, если количество включенных ребер становится равным N-1 – это означает, что они образуют покрывающее дерево, или если все ребра исходного графа G просмотрены, а покрывающее дерево все еще не построено. В этом случае исходный граф является несвязным, покрывающего дерева не существует, а получившийся лес является кратчайшим остовом исходного графа.

Алгоритм Краскала (построения кратчайшего остовного дерева).

Обозначим M – множество ребер исходного графа G, D₁, D₂, … - деревья, которые будут образовывать включенные ребра, n – счетчик количества включенных ребер. Перед началом выполнения алгоритма M включает все ребра исходного графа G, все D_i – пустые, n=0.

Шаг 1. Если множество Mпусто, то СТОП: остовного дерева не существует, непустыеD_iобразуют остов исходного графа (лес).

Шаг 2. Выбрать в множестве Mребро минимальной длины и исключить его изM. Для этого ребра возможны следующие случаи:

1. Обе инцидентные вершины не принадлежат никаким деревьям D_i. Образовать из них и этого ребра новое деревоD_i, n:=n+1.

2. Одна из вершин (концов ребра) принадлежит дереву D_i, другая не принадлежит ни одному дереву. Включить в деревоD_iребро другую вершину,n:=n+1.

3. Одна из инцидентных вершин принадлежит дереву D_i, другая – деревуD_j. Объединить оба дерева в одно, присоединив ребро к новому дереву,n:=n+1.

4. Обе вершины принадлежат одному дереву D_i. В этом случае ребро не включается в строящийся остов.

Шаг 3. Если n=N-1, то СТОП: единственное непустое деревоD_i– кратчайшее покрывающее дерево исходного графа, иначе перейти к шагу 1.

Рис. 2.6

На рис. 2.6 приведен граф и кратчайшее остовное дерево, найденное с помощью алгоритма Краскала. Двойной линией отмечены ребра, просмотренные, но не включенные в дерево в процессе работы алгоритма.

В таблице приведены промежуточные результаты работы алгоритма.

Имеются и другие способы построения кратчайшего остовного дерева, например, алгоритм Прима, более простой для описания (но не для реализации). В нем на каждом шаге строится не просто ациклический граф, а дерево.

Шаг 1. Выбрать в графе ребро минимальной длины и построить дерево D₁, состоящее из этого ребра и инцидентных ему вершин.

Шаг 2. Если дерево D_iпорядкаiуже построено иi<N-1, то среди рёбер, соединяющих вершины этого дерева с вершинами графаG, не входящими вD_iвыбрать ребро минимальной длины. Построить деревоD_i+1, присоединяя кD_iэто ребро вместе с его не входящим вD_i концом, увеличитьiна единицу и перейти к шагу 2.

Если этот алгоритм применить к графу из рассмотренного примера, то ребра будут включаться в дерево в следующем порядке: (1,2), (1,3), (3,5), (5,6), (3,4).