chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2020-21-2-169-189cheb-763Research ArticleСтатьиArticleРасстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизацииGromov–Hausdorff Distances to Simplexes and Some Applications to Discrete OptimisationИвановАлександр ОлеговичIvanovAlexander Olegovich

профессор

professor

aoiva@mech.math.msu.suТужилинАлексей АвгустиновичTuzhilinAlexey Augustinovich

профессор, механико-математический факультет

professor

tuz@mech.math.msu.suМосковский государственный университет имени М. В. Ломоносова; Московский государственный технический университет имени Н. Э. БауманаРоссияLomonosov Moscow State University; Bauman Moscow State Technical UniversityRussian FederationМосковский государственный университет имени М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian Federation202007042020212169189Copyright © Иванов А.О., Тужилин А.А., 20202020Иванов А.О., Тужилин А.А.Ivanov A.O., Tuzhilin A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/763

В работе изучается взаимосвязь между расстоянием Громова — Хаусдорфа и задачами дискретной оптимизации. Расстояние Громова — Хаусдорфа до метрического пространства с одинаковыми непутевыми расстояниями используется используется для решения следующих проблем: вычисление длин ребер минимального остовного дерева для конечного метрического пространства; обобщенная пробам Борсука; вычисление хроматическогочисла и минимального размера клинкового покрытия для простого графа.

Relations between Gromov–Hausdorff distance and Discrete Optimisation problems arediscussed. We use the Gromov–Hausdorff distances to single-distance metric space for solvingthe following problems: calculation of lengths of minimum spanning tree edges of a finite metricspace; generalised Borsuk problem; chromatic number and clique cover number of a simplegraph calculation problems.

расстояние Громова — Хаусдорфаминимальное остовное деревопроблема Борсукахроматическое числоклинковое покрытиеметрическая геометриядискретная оптимизацияGromov–Hausdorff distanceMinimum spanning treeBorsuk problemchromatic numberclique coveringmetric geometrydiscrete optimisationReferences

The authors declare that there are no conflicts of interest present.