Задача Штейнера

Минимальное дерево Штейнера для точек A, B и C, где S — точка Ферма треугольника ABC.

Задача Штейнера состоит в поиске минимального дерева Штейнера — кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (1796—1863).

История

История этой задачи восходит ко временам Пьера Ферма (1601—1665), который, после изложения своего метода исследования минимумов и максимумов, написал^[1]:

Qui hanc methodum non probaverit, ei proponitur: Datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minima quantitas.

Тот же, кто этот метод не оценил, пусть он решит [следующую задачу]: для заданных трех точек найти такую четвертую, что если из нее провести три отрезка в данные точки, то сумма этих трех отрезков даст наименьшую величину.

Эта задача была частично решена Э. Торричелли ^{[2] [3]} (1608—1647) и Б. Кавальери ^[4] (1598—1647), учениками Б. Кастелли (1577—1644), затем найденная ими конструкция была модифицирована Т. Симпсоном ^[5] (1710—1761) и окончательно уточнена Ф. Хейненом ^[6] и Ж. Бертраном (1822-1900). В результате, был получено геометрическое построение точки S, ныне называемой точкой Ферма (иногда точкой Торричелли), которая для трёх заданных точек A, B и C даёт минимально возможную сумму длин отрезков AS, BS, CS.

В 1934 году В. Ярник и O. Кесслер ^[7] сформулировали обобщение задачи Ферма, заменив три точки на произвольное конечное число. А именно, их задача состоит в описании связных плоских графов наименьшей длины, проходящих через данное конечное множество точек плоскости.

В 1941 году вышла монография Р. Куранта и Г. Роббинса «Что такое математика?»^[8], в которой авторы написали следующее:

Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни $A$, $B$, $C$ системой дорог таким образом, чтобы их общая протяженность была минимальной. Было бы естественно обобщить эту проблему на случай $n$ заданных точек $A_1, A_2, \ldots, A_n$ следующим образом: требуется найти в плоскости такую точку $P$, чтобы сумма расстояний $a_1 + a_2 + \ldots + a_n$ (где $a_i$ обозначает расстояние $PA_i$) обращалась в минимум. … Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки $P$. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной.[8]

Эта книга завоевала заслуженную популярность, в результате чего и задачу Ферма, и задачу Ярника—Кесслера сейчас принято называть проблемой Штейнера.

Основные определения

Приведем несколько современных формулировок проблемы Штейнера. В качестве объемлющего пространства вместо евклидовой плоскости рассмотрим произвольное метрическое пространство.

Минимальные деревья Штейнера

Пусть $(X,\rho)$ — метрическое пространство и $G=(V,E)$ — граф на X, то есть, $V\subset X$. Для каждого такого графа определены длины его рёбер $e=\{u,v\}\in E$ как расстояния $\rho(u,v)$ между их вершинами, а также длина $\rho(G)$ самого графа $G$ как сумма длин всех его рёбер.

Если $M$ — конечное подмножество $X$, а $G=(V,E)$ — связный граф на $X$, для которого $M\subset V$, то $G$ называется графом, соединяющим $M$. При этом граф $G$, соединяющий $M$, минимально возможной длины $\rho(G)$ является деревом, которое называется минимальным деревом Штейнера на $M$. Именно изучению таких деревьев и посвящена одна из версий проблемы Штейнера.

Отметим, что минимальные деревья Штейнера существуют не всегда. Тем не менее, точная нижняя грань величин $\rho(G)$ по всем связным графам, соединяющим $M$, всегда существует, называется длиной минимального дерева Штейнера на $M$ и обозначается через $\operatorname{smt}(M)$.

Примеры

Если $(X,\rho)$ — стандартная евклидова плоскость, т.е. расстояние $\rho$ порождается нормой $\|(x,y)\| = \sqrt{x^2+y^2}$, то получаем классическую проблему Штейнера, сформулированную Ярником и Кесслером (см. выше).

Если $(X,\rho)$ — манхэттенская плоскость^{[убрать шаблон]}, т.е. расстояние $\rho$ порождается нормой $\|(x,y)\| = |x|+|y|$, то получает прямоугольную проблему Штейнера, одним из приложений которой является проектирование разводок микросхем. Более современные разводки моделируются метрикой, порожденной λ-нормой (единичный круг — правильный 2λ-угольник; в этих терминах манхеттенская норма является 2-нормой).

Если в качестве $X$ берётся сфера (приблизительно моделирующую поверхность Земли), а за $\rho(a,b)$ — длина кратчайшей из двух дуг большой окружности, высекаемой из сферы $X$ плоскостью, проходящей через $a$, $b$ и центр сферы, то получается разновидность транспортной задачи: требуется соединить заданный набор пунктов (городов, предприятий, абонентов и т.д.) кратчайшей коммуникационной сетью (дорог, трубопроводов, телефонных линий и т.д.), минимизировав затраты на строительство (предполагается, что затраты пропорциональны длине сети).

Если в качестве $X$ берётся множество всех слов над некоторым алфавитом, а в качестве $\rho(a,b)$ — расстояние Левенштейна, то получается вариант проблемы Штейнера, который широко используется в биоинформатике, в частности, для построения эволюционного дерева.

Если в качестве $X$ берётся множество вершин $V$ связного графа $G=(V,E)$, а в качестве $\rho$ — функция расстояния, порожденная некоторой весовой функцией $\omega\colon E\to\Bbb R$, то получается проблема Штейнера в графах.

Минимальные параметрические сети

Пусть $\partial G$ — некоторое подмножество множества $V$ вершин графа $G=(V,E)$, содержащее все вершины степени 1 и 2. Пара $(G,\partial G)$ называется графом с границей $\partial G$. Если $G$ — связный граф, и $\varphi\colon\partial G\to X$ — некоторое отображение в метрическое пространство $(X,\rho)$, то каждое отображение $\Gamma\colon G\to X$, ограничение которого на $\partial G$ совпадает с $\varphi$, называется сетью типа $(G,\partial G)$ с границей $\varphi$ в метрическом пространстве $(X,\rho)$. Ограничение сети $\Gamma$ на вершины и ребра графа $G$ называются соответственно вершинами и ребрами этой сети. Длиной ребра $\Gamma\colon\{u,v\}\to X$ сети $\Gamma$ называется величина $\rho\bigl(\Gamma(u),\Gamma(v)\bigr)$, а длиной $\rho(\Gamma)$ сети $\Gamma$ — сумма длин всех ее ребер.

Обозначим через $[G,\varphi]$ множество всех сетей типа $(G,\partial G)$ с границей $\varphi$. Сеть из $[G,\varphi]$, имеющая наименьшую возможную длину, называется минимальной параметрической сетью типа $(G,\partial G)$ с границей $\varphi$.

Отметим, что, как и в случае минимальных деревьев Штейнера, минимальная параметрическая сеть существует не всегда. Тем не менее, точная нижняя грань величин $\rho(G)$ по всем сетям из $[G,\varphi]$, всегда существует, называется длиной минимальной параметрической сети и обозначается через $\operatorname{mpn}[G,\varphi]$.

Если $M$ — конечное подмножество $X$, а $\varphi$ отображает $\partial G$ на все $M$, т.е. $\operatorname{im}(\varphi)=M$, то говорят, что сеть $\Gamma\in[G,\varphi]$ соединяет $M$. Легко видеть, что $\operatorname{smt}(M)=\inf\operatorname{mpn}[G,\varphi]$ по всем $[G,\varphi]$, для которых $\operatorname{im}(\varphi)=M$. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.

Одномерные минимальные заполнения в смысле Громова

Это естественное обобщение проблемы Штейнера было предложено А. О. Ивановым и А. А. Тужилиным.^[9] Пусть $M$ — произвольное конечное множество и $G=(V,E)$ — некоторый связный граф. Будем говорить, что $G$ соединяет $M$, если $M\subset V$. Пусть теперь ${\mathcal M}=(M,\rho)$ — конечное псевдометрическое пространство (где, в отличие от метрического пространства, расстояния между разными точками могут быть равны нулю), $G=(V,E)$ — связный граф, соединяющий $M$, и $\omega\colon E\to{\Bbb R}_+$ — некоторое отображение в неотрицательные вещественные числа, называемое обычно весовой функцией и порождающее взвешенный граф $\mathcal G=(G,\omega)$. Функция $\omega$ задает на $V$ псевдометрику $d_\omega$, а именно, расстоянием между вершинами графа $\mathcal G$ назовем наименьший из весов путей, соединяющих эти вершины. Если для любых точек $p$ и $q$ из $M$ выполняется $\rho(p,q)\le d_\omega(p,q)$, то взвешенный граф $\mathcal G$ называется заполнением пространства $\mathcal M$, а граф $G$ — типом этого заполнения. Число $\operatorname{mf}(\mathcal M)$, равное $\inf\omega(\mathcal G)$ по всем заполнениям $\mathcal G$ пространства $\mathcal M$, назовем весом минимального заполнения, а заполнение $\mathcal G$, для которого $\omega(\mathcal G)=\operatorname{mf}(\mathcal M)$, — минимальным заполнением. Основная задача — научиться вычислять $\operatorname{mf}(\mathcal M)$ и описывать минимальные заполнения.

Примечания

1. ↑ Fermat P. de (1643), Ed. H.Tannery, ed., «"Oeuvres"», vol. 1, Paris 1891, Supplement: Paris 1922, сс. 153, <http://www.archive.org/details/oeuvresdefermat901ferm> 
2. ↑ G. Loria, G. Vassura (1919), «Opere de Evangelista Torriceli», vol. 1, сс. 79-97 
3. ↑ J. Krarup, S. Vajda (1997). «On Torricelli's geometrical solution to a problem of Fermat». IMA J. Math. Appl. Bus. Indust. 8 (3): 215-224. DOI:10.1093/imaman/8.3.215.
4. ↑ B. Cavalieri (1647), «Excercitationes Geometricae» 
5. ↑ T. Simpson (1750), «"The Doctrine and Application of Fluxions"» 
6. ↑ F. Heinen (1834), "«Über Systeme von Kräften»", Gymnasium zu Cleve (Essen) 
7. ↑ V. Jarník, O. Kössler (1934), "«O minimálních grafech obsahujících n daných bodu»", Ĉas, Pêstování Mat. (Essen) Т. 63: 223-235, <http://www.pdf.dml.cz/bitstream/handle/10338.dmlcz/122548/CasPestMatFys_063-1934-8_1.pdf> 
8. ↑ ^{1 2} R. Courant, H. Robbins (1941), «What Is Mathematics?», Oxford University Press 
9. ↑ A. O. Ivanov, A. A. Tuzhilin. «One-dimensional Gromov minimal filling».

Литература

• А. О. Иванов, А. А. Тужилин Теория экстремальных сетей. — Москва–Ижевск: Институт компьютерных исследований, 2003. — ISBN 5-93972-292-X
• А. О. Иванов, А. А. Тужилин Задача Штейнера на плоскости или плоские минимальные сети // Матем. сб.. — 1991. — Т. 182. — № 12. — С. 1813–1844.
• Weisstein, Eric W. Steiner Tree (англ.) на сайте Wolfram MathWorld.