Преобразование задачи Штейнера на евклидовой плоскости к задаче Штейнера на графе

Если в задаче Штейнера на графе число терминальных узлов много меньше числа всех узлов графа (например, число всех узлов равно 1000, а число терминальных – 50), то в решении задачи ( в минимальном дереве) можно увидеть не разрозненный набор ребер (или дуг), а систему путей на графе, связывающих терминальные вершины. Эта система путей аналогична системе отрезков, составляющих дерево Штейнера на евклидовой плоскости: локальная степень терминальных узлов, как правило, равна 1, а локальная степень некоторых узлов из тех, которые составляют пути, равна 3 или более. Такие узлы являются аналогом точек Штейнера в задаче на плоскости. Совпадение структуры деревьев в задачах Штейнера на евклидовой плоскости и на графе позволяют строить алгоритм решения в задаче Штейнера на графе по той же схеме, что и в задачи Штейнера на евклидовой плоскости. С другой стороны, при необходимости за решение задачи на евклидовой плоскости можно принять решение задачи на графе (если только граф отвечает определенным требованиям).

Статья представлена к публикации членом редколлегии: П. Ю. Чеботарев