УказательРазделыОбозначенияАвторО проекте


Раздел - в процессе разработки. Строительные работы: 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|.

Аналитика

Т

Теорема.[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) \, .

Решение. Будем пробовать последовательные варианты решения задачи. Если не добавлять дополнительных терминалов, то решением задачи будет ломаная 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\} на плоскости задача о дереве Штейнера заключается в нахождении дополнительного конечного множества узловых точек1) \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 и, по крайней мере, одно из них будет минимальным деревом Штейнера. Полным деревом Штейнера на \mathbb P называется дерево, удовлетворяющее условиям 1 4 и имеющее ровно k=n-2 точек Штейнера. Любое минимальное дерево Штейнера может быть представлено в виде объединения полных деревьев Штейнера.

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

П

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

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|.

.

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

Будем предполагать, что терминалы \{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 \}.

П

Пример. Найти точные координаты точек и длину дерева Штейнера в топологии \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} ( \overrightarrow{TP_j}, \mathbf e_j) \ ,

здесь ( \ ) означает скалярное произведение векторов, а точка T_{} может быть взята произвольной.

§

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

П

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

P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,1)

сумма сил из теоремы:

(\overrightarrow{OP_1}, \mathbf{e}_1)+ (\overrightarrow{OP_2}, \mathbf{e}_2) + (\overrightarrow{OP_3}, \mathbf{e}_3)+(\overrightarrow{OP_4}, \mathbf{e}_4) \, ;

схема их приложения изображена на рисунке Для терминалов

P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,4)

сумма сил из теоремы:

(\overrightarrow{OP_1}, \mathbf{e}_1)+ (\overrightarrow{OP_2}, \mathbf{e}_2) + (\overrightarrow{OP_3}, \mathbf{e}_3)+(\overrightarrow{OP_4}, \mathbf{e}_{41}+\mathbf{e}_{42}) .

Утверждается, что суммы равны длинам соответствующих минимальных деревьев Штейнера.

Источники

Берн М.У., Грэм Р.Л. Поиск кратчайших путей. 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, P. 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.

1) Возможно, пустого.

2018/01/29 09:28 редактировал au