Задача Штейнера о минимальном дереве: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
Нет описания правки |
||
Строка 117:
Если <math>M</math> — конечное подмножество <math>X</math>, а <math>\varphi</math> отображает <math>\partial G</math> на все <math>M</math>, т.е. <math>\operatorname{im}(\varphi)=M</math>, то говорят, что сеть <math>\Gamma\in[G,\varphi]</math> ''соединяет'' <math>M</math>. Легко видеть, что <math>\operatorname{smt}(M)=\inf\operatorname{mpn}[G,\varphi]</math> по всем <math>[G,\varphi]</math>, для которых <math>\operatorname{im}(\varphi)=M</math>. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.
=== Одномерные минимальные заполнения в смысле Громова ===▼
Это естественное обобщение проблемы Штейнера было предложено А.О.Ивановым и А.А.Тужилиным.▼
Пусть <math>M</math> — произвольное конечное множество и <math>G=(V,E)</math> — некоторый связный граф. Будем говорить, что <math>G</math> ''соединяет <math>M</math>'', если <math>M\subset V</math>. Пусть теперь <math>\cal M=(M,\rho)</math> — конечное псевдометрическое пространство (в отличие от метрики, расстояния между разными точками могут быть равны нулю), $G=(V,E)$ — связный граф, соединяющий $M$, и
$\om\:E\to\R_+$ — некоторое отображение в неотрицательные вещественные
числа, называемое обычно {\em весовой функцией} и порождающее {\em
взвешенный граф\/} $\cG=(G,\om)$. Функция $\om$ задает на $V$
псевдометрику $d_\om$, а именно, расстоянием между вершинами графа $\cG$
назовем наименьший из весов путей, соединяющих эти
вершины. Если для любых точек $p$ и $q$ из $M$ выполняется $\r(p,q)\le
d_\om(p,q)$, то взвешенный граф $\cG$ называется {\em заполнением\/}
пространства $\cM$, а граф $G$ — {\em типом\/} этого {\em заполнения}.
Число $\mf(\cM)$, равное $\inf\om(\cG)$ по всем заполнениям $\cG$
пространства $\cM$, назовем {\em весом минимального заполнения}, а
заполнение $\cG$, для которого $\om(\cG)=\mf(\cM)$, --- {\em минимальным
заполнением}. Основная задача — научиться вычислять $\mf(\cM)$ и
описывать минимальные заполнения.
<!--
▲=== Одномерные минимальные заполнения в смысле Громова ===
▲Это естественное обобщение проблемы Штейнера было предложено А.О.Ивановым и А.А.Тужилиным
=== Минимальные взвешенные параметрические сети ===
| |||