1 марта Еремин А. Ю. Формула веса минимального заполнения конечного метрического пространства
| Вид материала | Задача |
- Маттео Гарроне «гоморра», 214.71kb.
- Программа дисциплины Конечные поля Семестр, 8.97kb.
- Внастоящей работе представлены применения метрического анализа для прогнозирования, 9.88kb.
- Тематично-календарний план лекц І й з дисципліни „ в ищ а математика, 285.75kb.
- Тематико-календарный план лекций по дисциплине „ Высшая математика Ікурс, 263.63kb.
- Старинные русские меры длины, веса, объёма, 649.73kb.
- Об упрощенной системе налогообложения в отношении минимального налога, 25.36kb.
- Опубликовано 25 марта 2011, 335.67kb.
- Стандарт теория вероятностей и математическая статистика энМИ, иэт, этф, 24.95kb.
- Итоги выставки-продажи «Формула рукоделия в Украине осень 2011» Цифры и факты, 150.94kb.
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$ "--- какое-то натуральное число, называемое кратностью мультобхода. В конце доклада будет рассказано о некоторых возможных обобщениях понятия минимального заполнения на случай бесконечных метрических пространств.