1 марта Еремин А. Ю. Формула веса минимального заполнения конечного метрического пространства




Скачать 12.66 Kb.
Дата 03.10.2016
Размер 12.66 Kb.
1 марта
Еремин А.Ю.

Формула веса минимального заполнения конечного метрического пространства

 

Задача о минимальном заполнении конечного метрического пространства впервые была поставлена Ивановым и Тужилиным в статье <<�Одномерная проблема Громова о минимальном заполнении>>. Она возникла на стыке двух классических проблем: проблемы Штейнера о кратчайшей сети и проблемы Громова о минимальном заполнении гладкого многообразия.



Пусть дано конечное метричесое пространство $M$.Рассматриваются всевозможные связные взвешенные графы, такие что множество их вершин содержит $M$ и для любых двух точек из $M$ вес любого пути, соединяющего их в графе, не меньше расстояния между ними в метрическом пространстве (такие взвешенные графы называются заполнениями данного метрического пространства). Задача состоит в поиске минимального заполнения, то есть заполнения наименьшего веса.

В упомянутой статье было введено понятие планарного обхода "--- замкнутого пути по графу, проходящего через каждое ребро дважды.



Для каждого планарного обхода определяется периметр этого обхода. Ивановым и Тужилиным была высказана гипотеза о том, что вес минимального заполнения может быть вычислен по формуле $\mathop{\mathrm{mf}}(\mathcal M) = \min\limits_G\max\limits_\pi p(\mathcal M,\,\pi)$, где $G$ "--- всевозможные бинарные деревья, затягивающие $\mathcal M$, $\pi$ "--- их планарные обходы, $p(\mathcal M,\,\pi)$ "--- соответствующие периметры. Оказывается, данная гипотеза неверна (пример соответствующего 6-ти точечного метрического пространства будет приведен), но становится верной при замене обходов на мультобходы "--- замкнутые пути, проходящие через каждое ребро $2k$ раз, где $k$ "--- какое-то натуральное число, называемое кратностью мультобхода. В конце доклада будет рассказано о некоторых возможных обобщениях понятия минимального заполнения на случай бесконечных метрических пространств.


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница