НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o280.pdf (440.15Кб)

УДК 519.176+514.76+519.23

Россия,  Московский Государственный Университет им. М.В.Ломоносова

В данной работе рассматриваются свойства минимальных деревьев Штейнера для случая манхеттенской плоскости в контексте введения вероятностной меры. Данная проблема является важной, так как точные алгоритмы решения задачи Штейнера имеют повышенную вычислительную сложность (NP-трудные), а результат ее решения (в особенности для большого числа соединяемых точек) имеет множество практических применений. В связи с этим в работе рассматривается возможность ранжирования возможных топологий минимальных деревьев с учетом вероятности их применения. Для этого проведен анализ известных фактов о структуре минимальных деревьев для выбранной метрики с целью оценки их полезности для названной задачи. Предложен вариант введения вероятностной меры для случая небольшого числа граничных (заданных) вершин как иллюстрация доказанной теоремы о структуре минимальных деревьев.
Данная работа рассматривается как продолжение предыдущей аналогичной деятельности для задачи поиска минимальных заполнений и представляет собой первый шаг в решении более общей (сложной) задачи. Изложенный метод демонстрирует возможность доведения всех вычислений до конца аналитически, что позволяет надеятся на возможность его расширения для большего числа граничных точек (возможно с применением вычислительной техники).
Благодаря введению понятия существенной точки Штейнера, удалось существенно ограничить неоднозначность решения исходной задачи одновременно сравнив такой подход с более классическими работами в данной области. Указаны основные проблемы, препятствующие применению классических подходов для задачи введения вероятностной меры.
В перспективе предполагается попытка расширения области применения описанного подхода как в плане увеличения размеров системы (количество граничных точек), так и выбранной метрики (особенный интерес представляет Евклидова метрика). В особенности представляет интерес возможность выделения классов топологий с существенно большей/меньшей вероятностью с целью принципиального ограничения количества вариантов проверяемых топологий.

1. Karp Richard M. Reducibility among combinatorial problems // Complexity of Computer Computations: Proc. of a Symp. on the Complexity of Computer Computations / ed. by R.E. Miller, J.W. Thatcher. New York, NY: Plenum Press, 1972. P. 85-103. (The IBM Research Symposia Series).
2. Garey M.R., Graham R.L., Johnson D.S. The Complexity of Computing Steiner Minimal Trees // Siam Journal on Applied Mathematics. 1977. Vol. 32, no. 4. P. 835-859. DOI: 10.1137/0132072
3. Hwang F.K., Richards D.S., Winter P. The Steiner Tree Problem. North-Holland, New York, 1992. (Annals of Discrete Mathematics; vol. 53).
4. Salnikov V. Probabilistic properties of topologies of finite metric spaces’ minimal fillings // Journal of Mathematical Sciences. 2014, Vol. 203, iss. 6. P. 873-883. DOI: 10.1007/s10958-014-2179-2
5. Ivanov A.O., Tuzhilin A.A. One-dimensional Gromov minimal filling problem // Sbornik Mathematics. 2012. Vol. 203, no. 5. P. 677-726. DOI: 10.1070/SM2012v203n05ABEH004239
6. Hanan M. On Steiner’s problem with rectilinear distance // Siam Journal on Applied Mathematics. 1966. Vol. 14, no. 2. P. 255 - 265. DOI: 10.1137/0114025
7. Gromov M. Filling Riemannian manifolds // Journal of Differential Geometry. 1983. Vol. 18. P. 1-147.
8. Ivanov A.O., Tuzhilin A.A. Gromov minimal fillings for finite metric spaces // Publications de l’Institut Mathematique. 2013. Vol. 94, iss. 108. P. 3-15. DOI: 10.2298/PIM1308003I
9. Ivanov A.O., Tuzhilin A.A. Minimal fillings of finite metric spaces: The state of the art // In: Discrete Geometry and Algebraic Combinatorics / ed. by A. Bark, O. Musin. AMS, Providence, RI, US, 2014. P. 9–35. (Contemporary Mathematics; vol. 625). DOI: 10.1090/conm/625
10. Gilbert E.N. Random minimal trees // Journal of the Society for Industrial and Applied Mathematics. 1965. Vol. 13, no. 2. P. 376-387. DOI: 10.1137/0113021