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$ "--- какое-то натуральное число, называемое кратностью мультобхода. В конце доклада будет рассказано о некоторых возможных обобщениях понятия минимального заполнения на случай бесконечных метрических пространств.
|