Аннотация:
В работе изучается взаимосвязь между расстоянием Громова — Хаусдорфа и задачами дискретной оптимизации. Расстояние Громова — Хаусдорфа до метрического пространства с одинаковыми непутевыми расстояниями используется используется для решения следующих проблем: вычисление длин ребер минимального остовного дерева для конечного метрического пространства; обобщенная пробам Борсука; вычисление хроматического числа и минимального размера клинкового покрытия для простого графа.
Ключевые слова:
расстояние Громова — Хаусдорфа, минимальное остовное дерево, проблема Борсука, хроматическое число, клинковое покрытие, метрическая геометрия, дискретная оптимизация.
УДК:514.7+519.17+519.8
Поступила в редакцию: 08.12.2019 Принята в печать: 11.03.2020
Полный текст:
PDF файл (690 kB)