Задача. Для заданного множества точек $ \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_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| \ . $$

Доказательство формул может быть произведено аналитически: 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 $.

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

Для случая $ 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\} $ на плоскости задача о дереве Штейнера заключается в нахождении дополнительного конечного множества узловых точек²⁾ $ \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 $ точек Штейнера. Все терминалы в таком дереве имеют степень (валентность) $ 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 $ однозначно.

Алгоритм, разобранный в приведенном ниже примере, был разработан Жергонном⁴⁾ в 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 \} $. ♦

Пример. Найти точные координаты точек и длину дерева Штейнера в топологии $ \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) \, . $$ ♦

Достаточно просто длина дерева Штейнера в топологии $ \begin{array}{c} P_1 \\ P_2 \end{array} S_1 S_2 \begin{array}{c} P_4 \\ P_3 \end{array} $ (в случае его существования) выражается через координаты терминалов если перевести эту задачу на комплексную плоскость. Именно [9]: $$ d= | \varepsilon_2(z_3-z_1)+ \varepsilon_1(z_4-z_2) | \, \mbox{ при } \{z_j:=x_j+ \mathbf i y_j \}_{j=1}^4,\ \varepsilon_{1,2}=-\frac{1}{2} \pm \mathbf i \frac{\sqrt{3}}{2} \, . $$

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

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

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

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

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

[9]. Uteshev A.Yu., Semenova E.A. Length of a Full Steiner Tree as a Function of Terminal Coordinates. 2021. arXiv:2102.03303