Задача Штейнера о минимальном дереве

Пусть ${\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|}$, то получает прямоугольную проблему Штейнера, одним из приложений которой является проектирование разводок микросхем[11]. Более современные разводки моделируются метрикой, порожденной λ-нормой (единичный круг — правильный 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}$. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.

Это естественное обобщение проблемы Штейнера было предложено А. О. Ивановым и А. А. Тужилиным[12]. Пусть ${\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}})}$ и описывать минимальные заполнения.