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

Фундамент. и прикл. матем., 2015, том 20, выпуск 2, страницы 89–103 (Mi fpm1642)

Минимальные остовные деревья на бесконечных множествах

А. О. Иванов, А. А. Тужилин

Московский государственный университет им. М. В. Ломоносова

Аннотация: В работе изучаются минимальные остовные деревья на бесконечных множествах вершин. Получен критерий минимальности остовного дерева конечной длины, обобщающий классический результат для конечных множеств. Дано аналитическое описание множества всех бесконечных метрических пространств, для которых существуют минимальные остовные деревья. Получено достаточное условие существования минимального остовного дерева в терминах достижимости расстояния между элементами разбиения метрического пространства. Кроме того, вводится понятие локально минимального остовного дерева, изучаются свойства таких деревьев и их связь с (глобально) минимальными остовными деревьями.

Ключевые слова: минимальные остовные деревья, бесконечные графы, метрические пространства, расстояния между множествами.

УДК: 519.176+514.77+519.168


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2017, 223:6, 711–719

Реферативные базы данных:


© МИАН, 2024