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

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

История

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

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.

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

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

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

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

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

Алгоритм решения

Эффективного (сложность выражается функцией, ограниченной сверху некоторым полиномом от параметра задачи, в данном случае число вершин графа) алгоритма, дающего точное решение проблемы Штейнера, не существует при условии неравенства классов P и NP , так как проблема является NP-полной . Доказать это несложно через редукцию к задаче о вершинном покрытии .

Несмотря на ограничения, задачу можно решить приближенно, что и делает алгоритм Коу, Марковского и Бергмана. Идея такого подхода заключается в том, что нижняя граница стоимости соединения двух вершин (терминалов) - кратчайший путь между ними, а множество путей минимальной стоимости, соединяющих все терминалы дает 2-аппроксимированное решение, как будет доказано далее. Таким образом алгоритм будет выглядеть следующим образом:

1. Даны граф ${\displaystyle G=(V,E)}$ , множество терминалов ${\displaystyle T\subset V}$ и функция стоимости ${\displaystyle c\colon E\to \mathbb {Q} }$ .
2. Найди клику ${\displaystyle G_{D}=(T,F)}$ и ${\displaystyle c\colon F\to \mathbb {Q} }$ такую, что ${\displaystyle c_{D}(\{a,b\})=\operatorname {dist} _{G}(a,b)}$ .
3. Найди минимальное остовное дерево ${\displaystyle S_{D}=(T,F')}$ графа ${\displaystyle G_{D}}$ .
4. Для каждого ребра ${\displaystyle e\in F'}$ определи ${\displaystyle W_{e}=(V_{e},F_{e})}$ как путь длины ${\displaystyle c_{D}(e)}$ в графе ${\displaystyle G}$ .
5. Вычисли подграф ${\displaystyle H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})}$ .
6. Найди минимальное оставное дерево ${\displaystyle S_{H}}$ подграфа ${\displaystyle H}$ .
7. Удали из ${\displaystyle S_{H}}$ листья, не содержащиеся в ${\displaystyle T}$ .
8. Выведи результат.

Доказательство фактора аппроксимации сводится к оценке результата алгоритма и точного решения: ${\displaystyle c(S_{D})\leqslant 2\cdot c(S^{*})}$ . Если удвоить все рёбра оптимального решения, мы получим цикл ${\displaystyle Z}$ , содержащий все вершины ${\displaystyle T}$ . ${\displaystyle Z}$ же определяет остовное дерево ${\displaystyle T_{Z}}$ на графе ${\displaystyle G_{D}}$ , состоящее только из терминальных вершин. Таким образом ${\displaystyle c(S_{D})\leqslant c(T_{Z})\leqslant c(Z)=2\cdot c(S^{*})}$ . В качестве алгоритма поиска минимальных остовных деревьев можно использовать эффективный алгоритм Краскала .

Однако такая оценка аппроксимации не является пределом и возможно улучшить алгоритм, достигнув оценки ${\displaystyle 11/6}$ .

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• А. О. Иванов, А. А. Тужилин. Теория экстремальных сетей. — Москва–Ижевск: Институт компьютерных исследований, 2003. — ISBN 5-93972-292-X .
• А. О. Иванов, А. А. Тужилин. // Матем. сб.. — 1991. — Т. 182 , № 12 . — С. 1813—1844 .
• Протасов В. Ю. . — М. : МЦНМО. — 56 с. — (Библиотека «Математическое просвещение», выпуск 31).
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .