Информационные технологии проектирования электронных средств

- 63 - Эвклидова задача Штейнера впервые была поставлена как геометриче- ская задача, в которой нужно было множество Р точек на плоскости соединить так, чтобы сумма длин отрезков была минимальной. Если не допускается пересечение любых двух линий в точках вне данно- го множества Р , то задача сводится к одной из задач определения кратчайшего остова эквивалентного графа на  Р  вершинах с матрицей весов, вычисленных как эвклидово расстояние между точками множества Р . Если же допускается на плоскости введение дополнительных точек × (точек Штейнера), то длину кратчайшего остова на множестве Р ′⊃ Р можно уменьшать соответствующим подбором точек Штейнера (рис. 28). Рис.28 Таким образом для решения задачи Штейнера можно добавить в любых местах плоскости столько точек, сколько необходимо для построения кратчай- шего пути, стягивающего множество из Р точек. Получающееся наикратчайшее дерево называют наикратчайшим деревом Штейнера. Рассмотрим наиболее важные свойства: 1) точка Штейнера s i имеет локальную степень ρ ( s i )=3, т.е. точно три ребра должны быть инцидентны s i ; 2) для вершины р i ∈ Р степень d ( р i ) ≤ 3; 3) число точек Штейнера в наикратчайшем дереве Штейнера равно k : 0 ≤ k ≤ n -2, где n =  P  .