Задача Штейнера о минимальном дереве: различия между версиями

 

=== Одномерные минимальные заполнения в смысле [[Громов, Михаил Леонидович|Громова]] ===

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