4. Задача Штейнера

В предыдущем разделе в задаче определения SST, т. е. наикратчайшего дерева графа ребрами «покрывались» все вершины множества С зтой задачей тесно связана задача, известная как «задача Штейнера на графах» [27, 18], но последняя значительно труднее.

В этой задаче требуется найти наикратчайшее дерево которое «стягивает» («покрывает») заданное подмножество

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

Евклидова задача Штейнера впервые была поставлена как геометрическая задача [13, 14, 44, 24], в которой нужно множество точек на евклидовой плоскости соединить линиями так, чтобы сумма длин отрезков была минимальна.

Рис. 7.14а. Кратчайшее остовное дерево. Длина

Рис. 7.14б. Кратчайшее дерево Штейнера. Длина 9,196.

Если не допускаются пересечения любых двух линий в точках вне заданного множества то задача сводится к одной из задач определения SST эквивалентного графа на вершинах с матрицей весов, вычисленных как евклидово расстояние между точками множества Если допускается на плоскости введение дополнительных «искусственных» вершин (называемых точками Штейнера), то длину SST на множестве точек можно уменьшить соответствующим подбором точек. Например, для четырех точек, показанных на рис. 7.14а, SST имеет длину, большую, чем SST графа, получаемого после добавления двух новых точек расположенных «между» исходными точками (см. рис. 7.146). Таким образом, для решения задачи Штейнера можно добавить в любых местах плоскости столько точек Штейнера, сколько необходимо для построения наикратчайшего дерева, стягивающего множество из точек. Получающееся наикратчайшее дерево называют наикратчайшим деревом Штейнера.

Задача Штейнера на евклидовой плоскости достаточно хорошо изучена [44, 24, 11, 12], и известно большое число свойств наикратчайшего дерева Штейнера. Наиболее важными свойствами являются следующие [24, 11]:

(i) Точка Штейнера имеет степень Это можно легко показать с помощью геометрического построения, поскольку угол между ребрами, инцидентными точке Штейнера должен быть равен 120° и точно три ребра инцидентны любой точке Штейнера Следовательно, эта точка является «центром» (центром Штейнера) воображаемого треугольника, вершинами которого являются три другие точки дерева, с которыми она связана с помощью наикратчайшего дерева Штейнера.

Рис. 7.15а. Кратчайшее остовное дерево. Длина

Рис. 7.15б. Кратчайшее дерево Штейнера. Длина

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

(ii) Для вершины степень Если то угол между любыми двумя ребрами, инцидентными должен быть равен 120°. Если то угол между двумя ребрами, инцидентными должен быть больше или равен 120°.

(iii) Число точек Штейнера в наикратчайшем дереве Штейнера равно к где Доказательство упомянутых выше свойств можно найти в [24].

Несмотря на то внимание, которое уделялось евклидовой задаче Штейнера, при помощи существующих алгоритмов [44, 11] решение возможно только для небольших по размеру задач (не более 10 точек в и, следовательно, можно считать евклидову

эадачу Штейнера нерешенной. Для задач большого размера можно обратиться к ряду эвристических методов [7, 50].

В более позднем варианте задачи Штейнера на плоскости используется обычно линейное (вместо евклидова) расстояние между точками. Такая постановка задач впервые была предложена Хэнном [28, 30] в связи с разработкой теории монтажа печатных схем электронных устройств. Расстояние между точками с координатами в этом случае определяется следующим образом:

При этих условиях можно легко показать [44], что если через каждую точку из множества провести вертикальные и горизонтальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных точек Штейнера точки пересечения полученной сетки линий.

Пусть граф построен так, что множество его вершин X является множеством точек пересечения некоторой сетки линий и ребра графа соответствуют линиям сетки, соединяющим две точки пересечения. Тогда задача Штейнера на плоскости с линейной метрикой переходит в задачу Штейнера для конечного графа, определенную в начале этого раздела [54]. На рис. 7.156 показан пример наикратчайшего дерева Штейнера для линейной задачи с шестью точками, а для сравнения на рис. 7.15а показан SST этой задачи.

Задача Штейнера для обычных неориентированных графов рассматривалась Хакими [27] и Дрейфусом и Вагнером [18]. Они нашли точные алгоритмы решения таких задач. Однако эти алгоритмы с вычислительной точки зрения являются не эффективными процедурами, хотя они и значительно лучше, чем последовательный просмотр SST всех подграфов графа В любом случае (как и в случае задач с евклидовым расстоянием) максимальный размер задач Штейнера, для решения которых требуется разумное вычислительное время, не превышает 10 вершин (в множестве С этой точки зрения задачу Штейнера на графе можно рассматривать как нерешенную проблему, и она в этой книге больше не будет обсуждаться.

5. Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

6. Список литературы

(см. скан)

(см. скан)

(см. скан)