Инструменты сайта


Раздел - в процессе разработки. Строительные работы: 18.05.2015 - ??.??.????.


Дерево Штейнера

Задача. Для заданного множества точек $ \mathbb P= \{P_j\}_{j=1}^n $ плоскости построить такую систему отрезков $ \mathbb U $, чтобы она образовывала связное множество, содержащее $ \mathbb P_{} $, и при этом имела бы минимально возможную длину.

Здесь длина отрезка $ P_1P_2 $ понимается в смысле евклидовой метрики: $ |P_1P_2|=\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2} $ при $ P_1=(x_1,y_1),P_2=(x_2,y_2) $. Эта задача построения наикратчайшей сети, соединяющей точки множества $ \mathbb P $, известна как задача о минимальном дереве Штейнера.

Точки множества $ \mathbb P_{} $ часто называют терминалами.

Три терминала

Для трех коллинеарных терминалов решением задачи будет отрезок, соединяющий два крайних терминала.

Как изменится решение, если терминалы слегка «подвигать», чтобы они стали неколлинеарными? — Интуитивно ожидаемый ответ: решение должно слегка измениться, т.е. из отрезка превратиться в ломаную, соединяющую крайние терминалы с «внутренним». Пусть этим внутренним терминалом является $ P_{2} $.

Увеличим величину его отклонения от прямой $ P_1P_3 $, т.е. уменьшим величину угла $ \widehat{P_1P_2P_3} $. Можно ли ожидать, что минимальное дерево Штейнера останется совпадающим с ломаной $ P_1P_2P_{3} $? — Оказывается, что это заключение справедливо только до определенного значения угла $ \widehat{P_1P_2P_3} $, а именно до тех пор, пока он остается $ \ge 2\pi/3_{} $.

Что происходит с решением при переходе этого значения? — Оказывается минимум длины обеспечивается теперь принципиально иной конфигурацией: не ломаной $ P_1P_2P_{3} $, а трехзвенной конструкцией, в которой терминалы связываются посредством некоторой вспомогательной, «узловой», точки $ S_{} $, расположенной внутри терминального треугольника.

Эта точка называется точкой Ферма-Торричелли треугольника $ P_1P_2P_{3} $, и она формально определяется именно как точка треугольника, обеспечивающая минимальное значение величины $$ |P_1P|+ |P_2P|+|P_3P| $$ где $ P_{} $ — произвольная точка треугольника.

Т

Теорема. Если все углы треугольника $ P_1P_2P_{3} $ меньше $ 2\pi/3 $, то существует единственная точка $ S_{} $, лежащая внутри этого треугольника, которая дает минимальное значение для $ |P_1P|+ |P_2P|+|P_3P| $. Если один из углов треугольника $ \ge 2\pi/3 $, то минимум указанной суммы достигается когда точка $ P_{} $ совпадает с вершиной при этом угле.

Выяснение свойств точки Ферма-Торричелли и способы ее нахождения излагаются в следующих пунктах. А пока, забегая вперед, ответим на ожидаемый вопрос: если добавление одной дополнительной точки оптимизирует решение построения кратчайшей сети, соединяющей три терминала, то, возможно, добавление двух (или более) дополнительных даст еще бóльшую выгоду? — Ответ оказывается отрицательным.

Геометрия

Т

Теорема. Точка Ферма-Торричелли $ S_{} $ треугольника $ P_1P_2P_{3} $ обладает свойством $$ \widehat{P_1SP_2}=\widehat{P_2SP_3}=\widehat{P_1SP_3}=\frac{2\pi}{3} \, . $$

Можно образно охарактеризовать точку Ферма-Торричелли как точку треугольника, из которой любую пару его вершин $ P_j,P_k $ «видно» под углом раствора $ 2\pi/3 $.

Существует несколько геометрических способов построения точки Ферма-Торричелли. Излагаемый в следующем примере алгоритм представляет собой комбинацию алгоритмов Торричелли и Симпсона.

П

Пример. Построить точку Ферма-Торричелли для треугольника с вершинами

$$ P_1=(4,4), \ P_2= (2,1), P_3=(7,1) \, . $$

Решение. Построим сначала равносторонний треугольник на стороне $ P_1P_2 $ и внешний треугольнику $ P_{1}P_2P_3 $. Обозначим его третью вершину $ Q_1 $. Далее, опишем окружность вокруг этого треугольника: Проведем прямую $ Q_1P_3 $. Точка пересечения $ S_{} $ этой прямой с окружностью и будет точкой Ферма-Торричелли треугольника $ P_1P_{2}P_3 $: Длина построенной сети (минимального дерева Штейнера) оказывается равной $ |Q_1P_3| $ — это следует из того, что $ |Q_1S|=|P_1S|+|P_2S| $. Последнее вытекает из теоремы Птолемея.

Аналитика

Т

Теорема.[5] Пусть $ \{P_j= (x_{j},y_j)\}_{j=1}^3 $. Обозначим

$$ r_{j\ell}=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2}=|P_jP_{\ell}| \quad npu \ \{j,\ell\} \subset \{1,2,3\} \ . $$ Пусть все углы треугольника $ P_{1}P_2P_3 $ меньше $ 2\pi /3 $, или, что то же, выполнены условия: $$ r_{12}^2+r_{13}^2+r_{12}r_{13}-r_{23}^2>0,\ r_{23}^2+r_{12}^2+r_{12}r_{23}-r_{13}^2>0,\ r_{13}^2+r_{23}^2+r_{13}r_{23}-r_{12}^2>0 \ . $$ Точка $ S_{} $ Ферма-Торричелли имеет координаты $$ x_{\ast}=\frac{\kappa_1\kappa_2\kappa_3}{2 \sqrt{3} |S| d} \left(\frac{x_1}{\kappa_1}+\frac{x_2}{\kappa_2}+\frac{x_3}{\kappa_3} \right), \ y_{\ast}=\frac{\kappa_1\kappa_2\kappa_3}{2 \sqrt{3} |S| d} \left(\frac{y_1}{\kappa_1}+\frac{y_2}{\kappa_2}+\frac{y_3}{\kappa_3} \right) $$ при $$ |P_1S|+|P_2S|+|P_3S|= \sqrt{d} \ . $$ Здесь $$ d=\frac{1}{\sqrt{3}}(\kappa_1+\kappa_2+\kappa_3)=\frac{r_{12}^2+r_{13}^2+r_{23}^2}{2}+ \sqrt{3}\, |\mathfrak{S}| \ , $$ $$ \left\{ \begin{array}{lcl} \kappa_1=\frac{\sqrt{3}}{2}(r_{12}^2+r_{13}^2-r_{23}^2)+|\mathfrak{S}| , \\ \kappa_2=\frac{\sqrt{3}}{2}(r_{23}^2+r_{12}^2-r_{13}^2)+|\mathfrak{S}| , \\ \kappa_3=\frac{\sqrt{3}}{2}(r_{13}^2+r_{23}^2-r_{12}^2)+|\mathfrak{S}| \ ; \end{array} \right. $$ и $$ \mathfrak{S}=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1= $$ $$ =\left|\begin{array}{cc} x_2-x_1 & x_3-x_1 \\ y_2-y_1 & y_3-y_1 \end{array} \right|= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| \ . $$

Вариации приведенных формул см. в разделе Задача Ферма-Торричелли и ее развитие. Внимание: в настоящем разделе сменены обозначения! Точка Ферма-Торричелли в отсылаемом разделе обозначалась $ P_{\ast} $, в настоящем же разделе обозначается $ S_{} $; а, соответственно, величина $ S_{} $ теперь обозначается $ \mathfrak S $.

Доказательство формул может быть произведено аналитически: cтационарные точки функции $ F(x,y)=|P_1U|+|P_2U|+|P_3U| $ должны удовлетворять системе уравнений $$ \left\{ \begin{array}{lll} \displaystyle \frac{\partial F}{\partial x} &= \displaystyle \frac{x-x_1}{\sqrt{(x-x_1)^{2}+(y-y_1)^2}}+ \frac{x-x_2}{\sqrt{(x-x_2)^{2}+(y-y_2)^2}}+\frac{x-x_3}{\sqrt{(x-x_3)^{2}+(y-y_3)^2}}&=0 \\ \displaystyle \frac{\partial F}{\partial y} &= \displaystyle \frac{y-y_1}{\sqrt{(x-x_1)^{2}+(y-y_1)^2}}+ \frac{y-y_2}{\sqrt{(x-x_2)^{2}+(y-y_2)^2}}+\frac{y-y_3}{\sqrt{(x-x_3)^{2}+(y-y_3)^2}}&=0 \, . \end{array} \right. $$ Последнюю можно записать в векторной форме $$ \frac{U-P_1}{|UP_1|}+\frac{U-P_2}{|UP_2|}+\frac{U-P_3}{|UP_3|}=\mathbb O \, , $$ если считать $ U=(x,y) , \left\{ P_j=(x_j,y_j) \right\}_{j=1}^3 $ векторами, заданными своими координатами.

Четыре терминала

Решение задачи для случая трех терминалов наводит на мысль о поиске вспомогательной узловой точки для решения аналогичной задачи для случая четырех терминалов. Иначе говоря, поставим задачу поиска точки $ S_{} $, обеспечивающей минимум сумме расстояний $$ |PP_1|+|PP_2|+|PP_3|+|PP_4| \, , $$ где $ P_{} $ означает произвольную точку плоскости.

Т

Теорема [Фаньяно]. Если точки $ P_{1},P_2,P_3, P_{4} $ образуют выпуклый четырехугольник, то минимум суммы расстояний

$$ |PP_1|+|PP_2|+|PP_3|+|PP_{4}|$$ достигается в точке $ S_{} $, лежащей на пересечении диагоналей четырехугольника. Если же точки $ P_{1},P_2,P_3, P_{4} $ не образуют выпуклый четырехугольник, и точка $ P_{i} $ лежит внутри треугольника, образованного тремя оставшимися точками, то минимум суммы расстояний достигается в точке $ P_{i} $.

Итак, решение задачи получено. В случае выпуклого четырехугольника длина дерева оказывается равной сумме длин диагоналей четырехугольника.

Так вот, оказывается, что это решение неверно. Во-первых, существуют конфигурации терминалов, для которых введение дополнительной точки (или нескольких точек) не приводит к минимизации длины дерева, построенного путем соединения отрезками соседних терминалов.

П

Пример. Для системы терминалов $$ P_1=(0,2),\ P_2=(3,1),\ P_3=(5,1),\ P_4=(7,2) $$ минимальное дерево Штейнера является ломаной линией $ P_1P_2P_3P_4 $:

Ее длина $ 2+ \sqrt{5}+\sqrt{10} \approx 7.398346 $. Сумма длин диагоналей четырехугольника равна $ \sqrt{26}+\sqrt{17} \approx 9.222125 $.

Во-вторых, даже если добавление одной дополнительной точки приводит к уменьшению длины дерева, то добавление двух дополнительных точек может оказаться еще более выгодным!

П

Пример. Построить минимальное дерево Штейнера для системы терминалов $$ P_1=(0,3),\ P_2=(0,0),\ P_3=(4,0),\ P_4=(4,3) \, . $$

Решение. Будем пробовать последовательные варианты решения задачи. Если не добавлять дополнительных точек вообще, то эта задача относится к классу задач построения минимального покрывающего дерева1). В такой постановке решением рассматриваемого примера будет ломаная $ P_1P_2P_3P_4 $ длиной $ 3+4+3=10 $.

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

Тем не менее, выигрыша в длине дерева не получим: $ 5+5=10 $. Но если разрешено добавлять две дополнительных точки, то расположив их в $ S_1=\left(\frac{\sqrt{3}}{2},\frac{3}{2} \right) $ и $ S_2=\left(4-\frac{\sqrt{3}}{2},\frac{3}{2} \right) $ и построив следующую систему отрезков

получим суммарную длину равной $ 4+ 3\sqrt{3} \approx 9.196152 $.

Можно ли улучшить этот результат добавлением еще большего количества дополнительных точек? Ответ отрицателен: оказывается, что для произвольной конфигурации системы из четырех терминалов количество дополнительных точек, необходимых для решения задачи о минимальном дереве, никогда не превосходит двух.

В этом месте происходит расщепление двух задач: задачи о минимальном дереве Штейнера и задачи Ферма-Торричелли о поиске единственной точки плоскости, которая обеспечивает минимум суммы $ \sum_{j=1}^n |PP_j| $. Последняя задача подробно обсуждается ЗДЕСЬ.

Фундаментальные свойства дерева Штейнера

Для случая $ n=3 $ терминалов $ P_1,P_2,P_3 $, удовлетворяющих условиям теоремы ПУНКТА, решение задачи сводится к нахождению единственной точки треугольника $ P_1P_2P_3 $, а именно точки Ферма-Торричелли. В теории деревьев Штейнера эту точку принять называть также точкой Штейнера для множества $ \{P_1,P_2,P_3\} $. Если же условие теоремы не выполняется, то решением задачи является ломаная из двух звеньев, соединяющая две вершины при острых углах треугольника с вершиной при тупом угле (величиной $ \ge 2\pi/3 $).

В общем случае $ n> 3 $ терминалов $ \mathbb P= \{P_1,\dots,P_n\} $ на плоскости задача о дереве Штейнера заключается в нахождении дополнительного конечного множества узловых точек2) $ \mathbb S=\{S_1,\dots,S_k\}, k\ge 0 $ и множества прямолинейных отрезков, соединяющих эти дополнительные точки с терминалами из $ \mathbb P $.

Фундаментальные свойства общего решения задачи формулируются в терминах теории графов.

Дерево $ \mathbb U $ с вершинами $ \mathbb P \cup \mathbb S $ и прямолинейными ребрами, соединяющими некоторые пары вершин, является деревом Штейнера на множестве $ \mathbb P $ тогда и только тогда, когда оно удовлетворяет следующим условиям:

1. $ \mathbb U $ не имеет самопересечений;

2. для каждой точки $ S_i $ количество ребер дерева $ \mathbb U $, имеющих ее своим концом (называется также валентностью или степенью вершины графа) равно $ 3 $;

3. валентность каждого терминала $ P_j $ не превосходит $ 3 $;

4. каждая точка $ S_j $ является точкой Штейнера для треугольника, составленного из смежных с ней точек дерева $ \mathbb U $ , т.е. непосредственно связанных ребрами дерева с точкой $ S_j $;

5. $ 0 \le k \le n-2 $.

Точки $ S_i $ из множества $ \mathbb S $ называются точками Штейнера для дерева Штейнера $ \mathbb U $.

Для заданного множества терминалов $ \mathbb P $ имеется лишь конечное число деревьев Штейнера на $ \mathbb P $ и, по крайней мере, одно из них будет минимальным деревом Штейнера. Полным деревом Штейнера3) на $ \mathbb P $ называется дерево, удовлетворяющее условиям 1 4 и имеющее ровно $ k=n-2 $ точек Штейнера. Все терминалы в таком дереве имеют степень (валентность) $ 1 $ («являются листьями дерева»). Любое минимальное дерево Штейнера $ \mathbb T $ может быть представлено в виде объединения полных деревьев Штейнера. Именно, найдется множество деревьев $ \{\mathbb T_{k}\}_{k=1}^m $, такое что $$ \mathbb T = \mathbb T_1 \cup \dots \cup \mathbb T_m \ ; $$ каждое $ \mathbb T_{k} $ является полным деревом Штейнера для подмножества терминалов $ \mathbb P_k $: $$ \mathbb P=\mathbb P_1 \cup \dots \cup \mathbb P_k $$ и любая пара $ \mathbb T_{k}, \mathbb T_{\ell} $ может иметь общим элементом разве что один терминал. Такое представление дерева $ \mathbb T $ однозначно.

Четыре терминала: геометрия

Алгоритм, разобранный в приведенном ниже примере, был разработан Жергонном4) в 1810 г., и был переоткрыт Мелзаком в 1961 г.

П

Пример. Для терминалов

$$ P_1=(2,6), \ P_2= (1,1), P_3=(9,2), P_4=(6,7) $$ построить дерево Штейнера в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $.

Решение. Построим сначала два равносторонних треугольника на сторонах $ P_1P_2 $ и $ P_3P_4 $ и внешних четырехугольнику $ P_1P_2P_3P_4 $: Обозначим их третьи вершины $ Q_1 $ и $ Q_2 $ соответственно. Далее, построим описанные окружности для этих треугольников: Проведем отрезок $ Q_1Q_2 $. Точки пересечения отрезка с окружностями и будут точками Штейнера. Дерево Штейнера в данной топологии имеет вид Его длина равна $ |Q_1Q_2| $.

Как изменяется топология дерева Штейнера при вариации параметров задачи, например, координат какого-либо из терминалов см. ЗДЕСЬ.

Четыре терминала: аналитика

§

Материалы настоящего пункта взяты из [4].

Будем предполагать, что терминалы $ \{P_j\}_{j=1}^4 $ пронумерованы так, что четырехугольник $ P_1P_2P_3P_4 $ является выпуклым, при его вершинах занумерованных в порядке против часовой стрелки.

Свойство выпуклости четырехугольника является необходимым условием существования полного дерева Штейнера.
Т

Теорема. Положим

$$ \begin{array}{lll} \tau_1 &= & 2\, x_1 - x_2 -2\, x_3 + x_4 +\sqrt{3} (y_2- y_4), \\ \tau_2 & = & - x_1 +2\, x_2 + x_3 -2\, x_4 +\sqrt{3} (y_3- y_1), \end{array} $$ и $$ \eta_1=-\frac{1}{\sqrt{3}}(\tau_1+2\,\tau_2),\ \eta_2 = \frac{1}{\sqrt{3}}(2\,\tau_1+\tau_2) $$ Если все значения $$ \delta = -(x_1-x_3) \eta_1 + (y_1-y_3) \tau_1 , $$ $$ \left\{\begin{array}{cc} \begin{array}{c} \delta_1 = (x_1-x_2) \eta_2 - (y_1-y_2) \tau_2, \\ \delta_2 = (x_1-x_2) \eta_1 - (y_1-y_2) \tau_1, \end{array} & \begin{array}{c} \delta_3 = -(x_3-x_4) \eta_2 + (y_3-y_4) \tau_2, \\ \delta_4 = -(x_3-x_4) \eta_1 + (y_3-y_4) \tau_1 \end{array} \end{array} \right. $$ положительны, то существует дерево Штейнера в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $. Координаты точки $ S_1 $ следующие: $$ x_{\ast}=x_1 - \frac{\sqrt{3}}{2} \cdot \frac{\delta_1 \tau_1}{\tau_1^2+\tau_1 \tau_2+ \tau_2^2}, \quad y_{\ast}=y_1 - \frac{\sqrt{3}}{2} \cdot \frac{\delta_1 \eta_1}{\tau_1^2+\tau_1 \tau_2+ \tau_2^2} \ , $$ а точки $ S_2 $ — $$ x_{\ast \ast}=x_3 + \frac{\sqrt{3}}{2} \cdot \frac{\delta_3 \tau_1}{\tau_1^2+\tau_1 \tau_2+ \tau_2^2}, \quad y_{\ast \ast}=y_3 + \frac{\sqrt{3}}{2} \cdot \frac{\delta_3 \eta_1}{\tau_1^2+\tau_1 \tau_2+ \tau_2^2} \ . $$ Длина дерева равна $$ d= \sqrt{\frac{\tau_1^2+\tau_1 \tau_2+ \tau_2^2}{3}} \, . $$

Доказательство формул может быть произведено аналитически. Существование дерева Штейнера в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ означает, что точки $ S_1 $ и $ S_2 $ доставляют минимум целевой функции $$ F(U_1,U_2)=|P_1U_1|+|P_2U_1|+ |U_1U_2| + |P_3U_2|+|P_4U_2| \, . $$ Cтационарные точки этой функции должны удовлетворять системе из $ 4 $х уравнений относительно координат $ U_1=(x,y), U_2=(\tilde x, \tilde y) $: $$ \left\{ \begin{array}{lll} \displaystyle \frac{\partial F}{\partial x} &= \displaystyle \frac{x-x_1}{\sqrt{(x-x_1)^{2}+(y-y_1)^2}}+ \frac{x-x_2}{\sqrt{(x-x_2)^{2}+(y-y_2)^2}}+\frac{x-\tilde x}{\sqrt{(x-\tilde x)^{2}+(y-\tilde y)^2}}&=0 \\ \displaystyle \frac{\partial F}{\partial y} &= \displaystyle \frac{y-y_1}{\sqrt{(x-x_1)^{2}+(y-y_1)^2}}+ \frac{y-y_2}{\sqrt{(x-x_2)^{2}+(y-y_2)^2}}+\frac{y- \tilde y}{\sqrt{(x-\tilde x)^{2}+(y- \tilde y)^2}}&=0 \\ \displaystyle \frac{\partial F}{\partial \tilde x} &= \displaystyle \frac{\tilde x-x_3}{\sqrt{(\tilde x-x_3)^{2}+(\tilde y-y_3)^2}}+ \frac{\tilde x-x_4}{\sqrt{(\tilde x-x_4)^{2}+(\tilde y-y_4)^2}} +\frac{\tilde x-x}{\sqrt{(x-\tilde x)^{2}+(y- \tilde y)^2}}&=0 \\ \displaystyle \frac{\partial F}{\partial \tilde y} &= \displaystyle \frac{\tilde y-y_3}{\sqrt{(\tilde x-x_3)^{2}+(\tilde y-y_3)^2}}+ \frac{\tilde y-y_4}{\sqrt{(\tilde x-x_4)^{2}+(\tilde y-y_4)^2}} +\frac{\tilde y-y}{\sqrt{(x-\tilde x)^{2}+(y- \tilde y)^2}}&=0\, . \end{array} \right. $$ Последнюю можно записать в векторной форме $$ \begin{array}{c} \frac{U_1-P_1}{|U_1P_1|}+\frac{U_1-P_2}{|U_1P_2|}+\frac{U_1-U_2}{|U_1U_2|}=\mathbb O_{2\times 0} \\ \frac{U_2-P_3}{|U_2P_3|}+\frac{U_2-P_4}{|U_2P_4|}+\frac{U_2-U_1}{|U_1U_2|}=\mathbb O_{2\times 0} \end{array} $$ если считать $ U_1,U_2, \{P_j\}_{j=1}^4 $ векторами, заданными своими координатами.

Такая запись позволяет подтвердить свойство 4 из списка фундаментальных свойств дерева Штейнера: если существует решение этой системы, то точка $ U_1 $ обязана быть точкой Штейнера (Ферма-Торричелли) для множества $ \{P_1,P_2,U_2 \} $ — первое из этих векторных уравнений уже встречалось нам в доказательстве теоремы о дереве Штейнера для трех терминалов. На том же основании, делаем вывод, что $ U_2 $ обязана быть точкой Штейнера (Ферма-Торричелли) для множества $ \{P_3,P_4,U_1 \} $.

Необходимость условий $ \delta_1>0 $ и $ \delta_3>0 $ из теоремы становится очевидной из вида формул для координат точек Штейнера. Действительно, эти величины отвечают за несовпадение $ S_1 $ и $ S_2 $ с терминалами $ P_1 $ и $ P_3 $ соответственно. Можно привести эквивалентные представления координат точек $ S_{1} $ и $ S_{2} $, «привязав» их к терминалам $ P_2 $ и $ P_4 $. Отсюда будет следовать и необходимость условий $ \delta_2>0 $ и $ \delta_4>0 $. Условие $ \delta>0 $ не такое очевидное, но завязано на оценку расстояния между точками Штейнера. Именно: $$ |S_1S_2|=\frac{\delta}{\sqrt{\tau_1^2+\tau_1 \tau_2+ \tau_2^2}} \, . $$ И положительность $ \delta $ гарантирует несовпадение точек Штейнера, т.е. невырожденность топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ полного дерева Штейнера.
П

Пример. Найти точные координаты точек и длину дерева Штейнера в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ для примера из предыдущего пункта:

$$ P_1=(2,6), \ P_2= (1,1), P_3=(9,2), P_4=(6,7) \, . $$

Решение. Величины $ \delta, \delta_1,\dots,\delta_4 $ из формулировки теоремы $$ \delta=62+11\sqrt{3},\ $$ $$ \delta_1=-1+13\sqrt{3},\ \delta_2=59+35\sqrt{3},\ \delta_3=63+ 41\sqrt{3},\ \delta_4=3+ 15\sqrt{3} $$ все положительны. Дерево Штейнера в указанной топологии существует. Далее, $$ \tau_1^2+\tau_1 \tau_2 + \tau_2^2 = 345+186\sqrt{3} $$ и, следовательно, длина дерева Штейнера равна $$ d=\sqrt{115+62\sqrt{3}} \approx 14.912651 \, . $$ Точки Штейнера: $$ S_1= \left(\frac{571+323\sqrt{3}}{2(115+62\sqrt{3})},\ \frac{3609+2051\sqrt{3}}{6(115+62\sqrt{3})}\right)=\left(\frac{5587}{3386}+\frac{1743}{3386}\sqrt{3},\ \frac{11183}{3386}+\frac{12107}{10158}\sqrt{3} \right) $$ $$ \approx ( 2.541631,\ 5.367094) $$ и $$ S_2 = \left(\frac{3(441+227\sqrt{3})}{2(115+62\sqrt{3})},\ \frac{1349+747\sqrt{3}}{2(115+62\sqrt{3})} \right)= \left(\frac{25479}{3386}-\frac{3711}{3386}\sqrt{3},\ \frac{16193}{3386}+\frac{2267}{3386}\sqrt{3}\right) $$ $$ \approx ( 5.626509, 5.941984) \, . $$

Физические модели

О равновесии системы стержней

Пусть имеется некоторое дерево, соединяющее терминалы $ P_{j} $. Будем считать ребра графа жесткими стержнями, сязанными между собой шарнирными соединениями. В направление каждого из входящих в терминал $ P_{j} $ ребер графа приложим силы единичной величины (направляющие векторы). Будет ли находиться эта система в равновесии?

Т

Теорема [Максвелл]. Для каждого терминала $ P_j $ минимального дерева Штейнера обозначим через $ {\mathbf e}_j $ сумму единичных векторов, задающих входящие в эту вершину ребра дерева. Тогда система стержней будет находиться в равновесии, а длина этого дерева вычисляется по формуле

$$ | \mathbf L |= \sum_{j} \langle \overrightarrow{TP_j}, \mathbf e_j \rangle \ , $$ здесь $ \langle \ \rangle $ означает скалярное произведение векторов, а точка $ T_{} $ может быть взята произвольной.

Расчет длины будет инвариантен относительно любого выбора точки $ T_{} $. Еще одно замечание касается того обстоятельства, что в теореме составляется сумма только по терминалам дерева Штейнера, с пропуском точек Штейнера. Это упрощение оправдано тем, что в каждой из этих точек входящие в нее ребра расположены под углами $ 2\pi/3 $ и суммирование трех направляющих векторов даст нулевой вектор.
П

Пример. Для терминалов

$$ P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,1) $$ сумма сил из теоремы: $$ \langle \overrightarrow{OP_1}, \mathbf{e}_1 \rangle+ \langle \overrightarrow{OP_2}, \mathbf{e}_2 \rangle + \langle \overrightarrow{OP_3}, \mathbf{e}_3 \rangle + \langle \overrightarrow{OP_4}, \mathbf{e}_4 \rangle \, ; $$ схема их приложения изображена на рисунке Для терминалов $$ P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,4) $$ сумма сил из теоремы: $$ \langle \overrightarrow{OP_1}, \mathbf{e}_1 \rangle + \langle \overrightarrow{OP_2}, \mathbf{e}_2 \rangle + \langle \overrightarrow{OP_3}, \mathbf{e}_3 \rangle + \langle \overrightarrow{OP_4}, \mathbf{e}_{41}+\mathbf{e}_{42} \rangle . $$ Утверждается, что суммы равны длинам соответствующих минимальных деревьев Штейнера.

Источники

Берн М.У., Грэм Р.Л. Поиск кратчайших путей. Scientific American.1989, N 3, cc. 64-70

[1]. Протасов В.Ю. Максимумы и минимумы в геометрии. М.МЦНМО. 2005

[2]. Brazil M., Graham R.I., Thomas D.A., Zachariasen M. On the history of the Euclidean Steiner tree problem. Arch. Hist. Exact Sci., 2014, Vol. 68, P.327-354

[3]. Gilbert E.N., Pollak H.O. Steiner minimal trees. SIAM J. Appl. Math., 1968. Vol. 16, N 1, pp. 1-29

[4]. Uteshev A.Yu. Some Analytics for Steiner Minimal Tree Problem for Four Terminals. 2015. arXiv:1505.03564

[5]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer. Math. Monthly, 2014, Vol. 121, No 4, P. 318-331. Текст (pdf) ЗДЕСЬ

[7]. Maxwell J.C. On the calculation of the equilibrium and stiffness of frames. Philos. Mag., 1864, V. 27 , pp.294-299.

[8]. Melzak Z.A. On the problem of Steiner. Can. Math. Bull., 1961, V. 4, pp. 143–148

1)
(англ.) Minimum spanning tree
2)
Возможно, пустого.
3)
(англ.) Full Steiner tree
4)
Gergonne, Joseph (1771-1859). Французский математик.
algebra2/optimiz/distance/torri/tree.txt · Последние изменения: 2021/01/08 19:22 — au