WikiSort.ru - Не сортированное

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

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

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

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