RUS  ENG
Полная версия
ЖУРНАЛЫ // Компьютерные исследования и моделирование // Архив

Компьютерные исследования и моделирование, 2012, том 4, выпуск 2, страницы 241–251 (Mi crm484)

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

Равномерные вложения графа в метрические пространства

А. В. Коганов

Научно-исследовательский институт системных исследований (НИИСИ РАН), Россия, 117218, г. Москва, Нахимовский п., 36, к. 1

Аннотация: Рассмотрена задача вложения бесконечного счетного графа в непрерывное метрическое пространство. Введено понятие равномерного вложения, при котором не возникает точек накопления на множестве образов вершин и образы ребер имеют ограниченную длину. Найдены необходимые и достаточные условия в терминах структуры графа для возможности равномерного вложения в пространства с метриками Эвклида и Лоренца. Доказано, что деревья с конечным ветвлением имеют равномерное вложение в пространство с метрикой модуля метрики Минковского.

Ключевые слова: метрическое пространство, бесконечный граф, факторграф, метрика Минковского, метрика Лоренца, метрика Эвклида.

УДК: 519.1,514.8

Поступила в редакцию: 28.02.2012

DOI: 10.20537/2076-7633-2012-4-2-241-251



© МИАН, 2025