- •Глава 4. Взвешенные графы и орграфы
- •Определения
- •Определение
- •Псевдокод
- •Замечания
- •Замечание
- •3.2.2. Алгоритм Прима (Prim)
- •Определения
- •Псевдокод
- •Замечания
- •3.2.3. Минимальное каркасное дерево для точек на евклидовой плоскости
- •Второй алгоритм решения
- •Определения
- •3.3.2. Минимальное каркасное дерево с максимальным числом листьев
- •Определение
- •Определение
- •3 Определение.3.7. Проблема многоцелевого минимального каркасного дерева с заданной степенью
- •Класс сложности
- •3 Определения.3.8. Обобщенное минимальное каркасное дерево
- •Класс сложности
- •Определения
- •Дерево Штейнера с евклидовой метрикой
- •Алгоритм построения дерева Штейнера с евклидовой метрикой
- •Определение
- •Определение
- •Определение
- •Класс сложности
Дерево Штейнера с евклидовой метрикой
Огромный практический интерес представляет решение проблемы дерева Штейнера на плоскости. Для любых двух пар вершин графа u=(ux,uy) и v=(vx,vy), заданных координатами на плоскости, расстояние задается в Lp-метрике (1 p ):
||uv||p=(|ux–vx|p+ |uy–uy|p)1/p.
Для двух специальных случаев:
Евклидово расстояние ||uv||2=((ux–vx)2+ (uy–uy)2)1/2;
Прямоугольное расстояние ||uv||1=|ux–vx| + |uy–uy|.
Алгоритм построения дерева Штейнера с евклидовой метрикой
На плоскости задано Nточек, изF- терминальные.
Алгоритм приблизительного построения дерева Штейнера:
Построить полносвязный граф G’=(N,E’) на вершинахN. Расстоянием между двумя вершинами этого графа будет кратчайшее расстояние между этими вершинами. Взять эти расстояния в качестве весов.
Найти минимальное каркасное дерево Т’ полносвязного графа G’.
Подставить минимальное каркасное дерево T’ в исходный графG. Заменить каждое ребро дереваT’ минимальным путем исходного графаG. В результате получится новый графT’’ (не всегдаT’’ будет деревом).
Найти каркасное дерево графа T’’, которое будет приблизительным деревом Штейнера.
Аппроксимационное отношение этого алгоритма равно 2.
Пример
G=(V,E) N={A,B,C,D} G’=(N,E’)
Рис.3.4.4.
Построение дерева Штейнера (выделено
жирным)
Замечание
Е
Пример
Исходная задача Дерево Штейнера (длина=9) Дерево Штейнера
с дополнительными вершинами Штейнера
(длина=7)
Рис.3.4.5. Решение
задачи Штейнера в прямоугольных
координатах
Деревья Штейнера с ограничениями
Д
Определение
ерево Штейнера с ограничением степеней
Задан простой связной ненаправленный G=(V,E)cnвершинами, неотрицательными весами реберcij, подмножеством терминальных вершинZVи ограничениями степеней вершинki2.
Проблемой Штейнера с ограничениями на степени вершин (TheDegree-constrainedSteinerProblem–DCSP) является нахождение на графе дерева Т такого, что степень каждой вершины дереваdeg(i)ki, а сумма весов ребер этого дерева минимальна среди всех возможных деревьев с ограничениями на степени вершин.
Класс сложности
Класс сложности DCSP–NP-тяжелая.
Алгоритмы
Точные алгоритмы решения DCSP(алгоритм перечисления каркасных деревьев и динамический программный алгоритм) имеют сложностьO(p22(n-p)+n3) иO(n3p+n22p+n) соответственно. Получить решения в приемлимое время для графа с десятком вершин проблематично.
Существует достаточно большое число эвристических алгоритмов, ряд из них дает расхождение решения на 10% от точного решения.
Д
Определение
ерево Штейнера с ограничением запаздывания
Задан простой связный ненаправленный граф G=(V,E) и две весовые функции на ребрах графа: функция стоимости сij и функция запаздыванияDij. Обе функции являются целыми положительными числами. Кроме того, задана вершина-истокsи терминальные вершиныSV.
Проблема нахождения дерева Штейнера с ограничением запаздывания:
Найти дерево Штейнера при условии, сумма запаздываний всех путей этого дерева от вершины sво все терминальные вершины не превышает некоторой положительной величины.
Класс сложности
Класс сложности данной проблемы – NP-тяжелый.
Алгоритмы
Имеется несколько эвристических алгоритмов решения данной проблемы.