logo search
Алгоритмы решения некоторых теоретико-графовых задач

Кратчайшее остовное дерево

Задача: найти кратчайшее остовное дерево взвешенного графа.

Пример прикладной задачи: необходимо проложить линии коммуникаций (дороги, линии связи, электропередач и т.п.) между n заданными "точечными" объектами, при условии, что, во-первых, известны "расстояния" между каждой парой объектов (это может быть геометрическое расстояние или стоимость прокладки коммуникаций между ними), и, во-вторых, объекты могут быть связаны как непосредственно, так и с участием произвольного количества промежуточных объектов.

При допущении, что разветвления возможны только в этих же n объектах, задача сводится к нахождению кратчайшего остовного дерева (SST - shortest spanning tree, или MST - minimal spanning tree) во взвешенном графе, вершины которого соответствуют заданным объектам, а веса ребер равны "расстояниям" между ними. Если каждая пара вершин соединена ребром, то граф является полным и решение существует всегда, в противном случае решение существует тогда и только тогда, когда граф связен (отсутствие ребра между двумя вершинами означает невозможность прямой связи между соответствующими объектами).

Замечание: в случае введения дополнительных точек разветвления, длина кратчайшего дерева, включающего все исходные точки, а также некоторое количество новых, может быть меньше длины кратчайшего дерева, построенного только на исходных точках. Если допустить, что точки разветвления не произвольны, а берутся из некоторого множества, то задачу можно сформулировать так: построить кратчайшее дерево, покрывающее заданное подмножество вершин взвешенного графа. Данная задача, называемая задачей Штейнера, является чрезвычайно сложной с вычислительной точки зрения и может быть практически решена только при небольшом количестве дополнительных вершин. В то же время, существует эффективный приближенный алгоритм, строящий дерево, длина которого превышает длину кратчайшего дерева не более чем в два раза.

В отличие от задачи Штейнера, задача поиска кратчайшего остовного дерева допускает эффективное решение. Ниже будут рассмотрены два алгоритма решения этой задачи.

Алгоритм Краскала

Вход: связный взвешенный граф G=(V,E), n=|V|, m=|E|.

Выход: SST - кратчайшее остовное дерево G.

  1. SST'=<пустой граф с n вершинами>;

  2. k=0;

  3. если |E(SST')|=n-1, то SST=SST'; КОНЕЦ;

  4. k=k+1;

  5. e=<k-ое по возрастанию весов ребро графа G>;

  6. если добавление e в SST' не приводит к появлению цикла, то добавить его в SST';

  7. перейти на шаг 3.

Доказательство корректности алгоритма Краскала

A.

Алгоритм Краскала (АК) завершает работу за конечное число шагов и строит остовное дерево графа, т.к. он является частным случаем следующего алгоритма построения остовного дерева графа (без весов).

Алгоритм построения остовного дерева графа (алгоритм ST)

Вход: связный граф G=(V,E), n=|V|, m=|E|.

Выход: ST - остовное дерево графа G.

  1. Занумеровать произвольным образом ребра графа G;

  2. ST'=<пустой граф с n вершинами>;

  3. k=0;

  4. если |E(ST')|=n-1, то ST=ST'; КОНЕЦ;

  5. k=k+1;

  6. e=<k-ое ребро графа G>;

  7. если добавление e в ST' не приводит к появлению цикла, то добавить его в ST';

  8. перейти на шаг 4.

Доказательство корректности алгоритма ST

A.

Докажем, что алгоритм ST завершает работу не более чем за m шагов, т.е. на шаге 4 при некотором km выполняется равенство |E(ST')|=n-1. Допустим обратное: |E(ST')|<n-1 при k=m (*). После выполнения шага 2 алгоритма |V(ST')|=n, следовательно, граф ST' не является связным (по следствию 1 леммы 3). Рассмотрим два произвольных связных компонента графа ST': графы T' и T''. В G не может существовать ни одного ребра, один из концов которого лежал бы в T', а другой в T'' (**) - в противном случае такое ребро было бы добавлено в ST' при некотором km на шаге 7 алгоритма, т.к. это ребро заведомо не привело бы к появлению цикла. Но из (**) следует, что G несвязен - получили противоречие с (*).

B.

Получаемый подграф ST является деревом по теореме 3 п.3 и является остовным деревом по определению, т.к. в него входят все вершины графа G.

~

АК является вариантом алгоритма ST, в котором ребра занумерованы по возрастанию весов.

B.

Докажем индукцией по числу ребер, что получаемое в результате работы АК остовное дерево является кратчайшим.

Базис индукции: при m=1 остовное дерево единственно, поэтому дерево, которое строит АК, является кратчайшим.

Допустим, что АК строит SST для всех графов G=(V,E), таких, что |E(G)|m. Докажем, что АК строит SST для графа G'=(V',E'): |E(G')|=m+1. Рассмотрим ребро e'E(G'), вес которого максимален. Возможны два варианта:

  1. e' - кольцевое;

  2. e' - ациклическое.

Рассмотрим первый случай (e' - кольцевое). Удалим e' из G'; получим связный граф G''=(V',E'\e'). В силу предположения индукции АК строит его SST. Вернемся к графу G': в силу максимальности веса e' АК "обработает" e' в последнюю очередь, поэтому при k=m граф SST'k(G') совпадает с SST(G''). При k=m+1 ребро e' не будет добавлено к SST'(G'), т.к. это привело бы к возникновению цикла, следовательно, SST(G') совпадает с SST(G''). Остается доказать, что при добавлении в связный граф ребра, вес которого не меньше, чем вес любого другого его ребра, длина кратчайшего остовного дерева графа не уменьшается. Но это верно в силу Леммы 1 (см. ниже). Таким образом, длина кратчайшего остовного дерева G' не меньше длины кратчайшего остовного дерева G''. Это минимальное значение достигается на SST(G'), следовательно, SST(G') является кратчайшим остовным деревом графа G'.

Лемма 1. Пусть G=G(V,E) - связный взвешенный граф; G'=(V,E+e'), Weight(e')Weight(e), eE(G) (*). Тогда существует кратчайшее остовное дерево графа G' , в которое не входит ребро e' (если Weight(e')>Weight(e), eE(G) (**), то e' не входит ни в какое кратчайшее остовное дерево G').

Доказательство: допустим, e' входит в кратчайшее остовное дерево T=SST(G') графа G'. Удалим из T ребро e': T распадется на два дерева T1 и T2. Найдем в графе G ребро e''E(G), один из концов которого лежит в T1, а второй - в T2: e''=(v,u), vT1, uT2 (такое ребро существует, т.к. в противном случае G не был бы связным). Соединим деревья T1 и T2 ребром e'': получим дерево T', которое является остовным деревом графа G', причем в силу (*) Weight(T') = Weight(T1) + Weight(T2) + Weight(e'') Weight(T1) + Weight(T2) + Weight(e') = Weight(T) - построили остовное дерево не большего суммарного веса (длины), в которое не входит ребро e'; в случае (**), очевидно, Weight(T') < Weight(T).

~

Рассмотрим второй случай (e' - ациклическое). Удалим e' из G'; получим граф G''=(V',E'\e'), состоящий из двух связных компонент G''1 и G''2, количество ребер в каждой из которых не превосходит m. В силу предположения индукции АК построит их SST. Как и в первом случае, при k=m граф SST'k(G') совпадает с SST(G''). При k=m+1 ребро e' будет добавлено в G' на шаге 7 АК, поэтому Weight(SST'm+1(G')) = Weight(SST(G''1)) + Weight(SST(G''2)) + Weight(e'). Но это минимальное возможное значение веса кратчайшего остовного дерева G', следовательно, АК построил кратчайшее остовное дерево G'.

~