Аннотация:
В цикле работ А.О.Иванова и А.А.Тужилина изучается связь между расстоянием Громова–Хаусдорфа и различными комбинаторными и геометрическими оптимизационными задачами. В частности, рассмотрены проблема Борсука о наименьшем числе частей, на которые можно разрезать ограниченное подмножество евклидова пространства так, чтобы все части имели меньший диаметр, чем исходное подмножество; о наименьшем числе цветов, необходимых для правильной раскраски вершин графа; о наименьшем числе клик, вершины которых покрывают множество вершин графа. Во всех этих задачах искомые количества найдены в терминах расстояния Громова–Хаусдорфа между подходящими конечными метрическими пространствами с одним или двумя ненулевыми расстояниями. Аналогичным образом вычислены длины ребер минимального основного дерева во взвешенном графе. В данном докладе мы расскажем об аналогичном решении задачи о вычислении так называемой $\ell_1$-размерности, т.е\. наименьшей размерности пространства с манхеттенской ($\ell_1$-) нормой, в которое изометрично вкладывается данное конечное метрическое пространство.
|
