3

Определение

.3.5. Каркасное дерево оптимальной связи

Задан связный ненаправленный граф G=(V,E). На ребрах графа заданы:

1. Запросы связи или передачи.Задаютсяматрицей запросовR=[r_ij], гдеr_ij– количество нагрузки, необходимое передать между вершинамиv_iиv_j.

2. Расстояния между вершинами v_iиv_j. Задаются матрицей расстоянияw[v_i,v_j].

Найти минимальное каркасное дерево Т=(V,F),FE, с минимальным весом

W(T)= f(w_ij,r_ij).

Во многих случаях рассматриваются функции fвидаf=w_ij*r_ij, где_*- операция умножения.

Класс сложности

Проблема является NP-тяжелой.

Алгоритмы

За последние 10-15 лет для решения проблемы было предложено большое количество эволюционных и генетических алгоритмов.

3.3.6. Проблема многоцелевого минимального каркасного дерева

Определения

Для заданного связного ненаправленного графа G=(V,E) сnвершинами для каждого ребра задаетсяK>1 неотрицательных целых числа. Эти числа определяютKатрибутовна ребрах графаw_ij=(w_ij¹,w_ij²,…,w_ij^K). Тогда проблема нахождениямногоцелевого каркасного дереваформулируется следующим образом:

на каркасном дереве Т графа GминимизироватьW=(W¹,W²,…,W^K), гдеW^k=w_i,j^k,k1…K.

Данная минимизация может и не дать минимум по всем компонентам W. В этом случае требуется найти множество каркасных деревьевS^*S(это множество называется оптимальным множеством Парето (Pareto)).

3 Определение.3.7. Проблема многоцелевого минимального каркасного дерева с заданной степенью

Если к проблеме нахождения многоцелевого минимального каркасного дерева ограничение по величине степени дерева, то в результате получится проблема многоцелевого минимального каркасного дерева с заданной степенью.

Класс сложности

Данная проблема NP-тяжелая.

3 Определения.3.8. Обобщенное минимальное каркасное дерево

Кластерами разбиения вершин графа на несколько групп по определенному признаку. Примером такого разбиения могут служить клики графа.

Проблема обобщенного минимального каркасного дерева (TheGeneralizedMinimumSpanningTreeProblem–GMSTP) формулируется следующим образом.

Задан ненаправленный связный граф G=(V,E) иVявляется объединениемKкластеровV_k,k=1,2,K, кластеров вершин графа. Неотрицательная матрица стоимостиC=[c_ij] ассоциируется с ребрамиE.

GMSTPтребует построения минимального по стоимости каркасного дерева, содержащегопо крайней мере одну вершину из каждого кластера (проблемаL-GMSTP).

Существует иная формулировка проблемы:

Найти минимальное по стоимости каркасное дерево, содержащее точноодну вершину из каждого кластера (проблемаE-GMSTP).

Класс сложности

В обеих формулировках проблема является NP-тяжелой.

Замечание

Впервые проблема E-GMSTPбыла исследована в 1995 году, а проблемаL-GMSTP– в 2000-2001 гг.

Алгоритмы

Различные точные алгоритмы решения применимы для графов с числом вершин от 100 до 200.

Имеется ряд эвристических и генетических алгоритмов алгоритмов, позволившие решить проблему с числом вершин графа около 500.

4. Д

   Определения

   еревья Штейнера (Steiner)

Пусть G=(V,E) будет графом, в котором каждое ребро имеет положительный действительный вес. В графеGзадаетсямножество N терминальных вершин,VN. Оставшиеся вершины (V\N) называютсянетерминальными вершинами иливершинами Штейнера.

Дерево Т, построенное на графе G, являетсяминимальным деревом Штейнераили простодеревом Штейнера, если это дерево содержит все терминальные вершиныN(заметим, что в дереве Штейнера могут содержаться нетерминальные вершины или вершины Штейнера).

Пример

Терминальные вершины:

N={1,3,6}

Рис.3.4.1. Дерево Штейнера (выделено жирным)

с точками Штейнера {2,4,5}

Класс сложности

Проблема нахождения минимального дерева Штейнера относится к NP-тяжелым.

Точные алгоритмы

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

Эвристические алгоритмы

К проблеме поиска деревьев Штейнера сводятся многие важные практические задачи. Поэтому литература по эвристическим алгоритмам по данной проблеме обширна.

В решении проблемы Штейнера имеется два крайних случая, когда они решаются в полиномиальное время:

_{- N=V, когда проблема сводится к поиску минимального каркасного дерева;}

_{- N=2, когда проблема сводится к поиску минимального пути между двумя вершинами.}

Эвристический алгоритм слияния кратчайших путей

(The Merged Shortest Paths Heuristic - SPATH)

_{Задан граф G=(V,E), |V|=n, |E|=m, неотрицательные целочисленные веса ребер и терминальные вершины FV.}

_{Описание алгоритма:}

_{Начиная с дерева, состоящего из одной терминальной вершины, к существующему дереву последовательно по одному прибавляется кратчайший путь к следующей терминальной вершине до тех пор, пока существуют неиспользованные терминальные вершины. Если кратчайшие пути одной или нескольких терминальных вершин содержит общие промежуточные вершины, то эти промежуточные вершины становятся внутренней вершиной дерева Штейнера со степенью больше двух.}

_{Если кратчайший путь выбирается с помощью алгоритма Дейкстры, то сложность алгоритма равна O(zn}²_{), где n – число вершин графа, z- число терминальных вершин.}