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),F E, с минимальным весом

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, k 1…K.

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

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

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

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

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

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

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

Проблема обобщенного минимального каркасного дерева (The Generalized Minimum Spanning Tree Problem – 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.