Олійник, БогданаПономарчук, Богдан2022-07-242022-07-242021Пономарчук Б. С. Метрична розмірність метричних та ультраметричних просторів з умовами скінченності : дисертація на здобуття наукового ступеня доктора філософії / Пономарчук Богдан Сергійович ; наук. керівник Олійник Богдана Віталіївна ; Національний університет "Києво-Могилянська академія". - Київ : НаУКМА, 2021. - 129 с.https://ekmair.ukma.edu.ua/handle/123456789/23482У дисертаційній роботі розглянуто задачу пошуку метричної розмірності для скінченних ультраметричних просторів, а також описано метричну розмірність для деяких конструкцій метричних просторів з умовами скінченності. Визначення метричної розмірності метричного простору було запропоноване Блюменталем в 1953 році. 20 років потому Харарі та Мелтер у своїй роботі застосували це визначення до метричних просторів визначених графами. Після чого, концепт метричної розмірності знайшов широке коло застосувань: комбінаторний аналіз, робототехніка, біологія, хімія та інші. У 2013 році С. Бау та Ф. Беардон продовжили ідеї Блюменталя щодо дослідження метричної розмірності метричних просторів. Вони вивчали метричну розмірність підпросторів Евклідового простору. Пізніше, М. Хейдарпур та С. Магсауді підрахували метричну розмірність геометричних просторів. Відомо що, пошук метричної розмірності метричного простору є NP-складною задачею. Є декілька шляхів дослідження метричної розмірності. Один з них — дослідження метричної розмірності для певних родин метричних просторів чи графів. Другим підходом є дослідження метричної розмірності конструкцій метричних просторів, що побудовані на основі метричних просторів, метрична розмірність яких вже відома. У дисертаційній роботі дослідження здійснюються в обох описаних вище напрямках. А саме повністю охарактеризовано метричну розмірність скінченних ультраметричних або неархімедових просторів. Показано, що для довільного скінченного ультраметричного простору його метрична розмірність може бути знайдена за поліноміальний час. Наведено поліноміальний алгоритм знаходження метричної розмірності для довільного ультраметричного простору. Для побудови цього алгоритму було використано ізометричне зображення ультраметричних просторів деревами. Показано, що складність побудови такого зображення дорівнює O(n5), де n — кількіств точок ультраметричного простору. Також доведено, що метрична розмірність ультраметричного простору, який визначається на кореневому дереві, або дорівнює метричній розмірності цього дерева як графа, або на одиницю менше. В роботі також повністю описано ультраметричні простори метрична розмірність яких дорівнює одиниці. Окрім ультраметричних просторів в дисертаційній роботі розглянуто метричну розмірність різних конструкцій метричних просторів. Зокрема показано, що для довільної шкали трансформації метрична розмірність метричного простору дорівнює метричній розмірності його трансформації. Наведено формулу для підрахунку метричної розмірності вінцевого добутку скінченного метричного простору і рівномірно дискретного метричного простору. У випадку коли метрична розмірність рівномірно дискретно метричного простору дорівнює нескінченності, метрична розмірність конструкції також дорівнює нескінченності. Крім того, для прямої суми метричних просторів скінченого діаметра показано, що її метрична розмірність дорівнюватиме сумі метричних розмірностей цих просторів. Показано, що для довільних метричних просторів скінченного діаметра метрична розмірність їх прямої суми дорівнює двом тоді і тільки тоді коли метрична розмірність кожного з просторів дорівнює 1. В останньому розділі також розглянуто метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, та dTO. Показано, що хоча ці метрики є топологічно еквівалентними, відповідні метричні простори мають різну метричну розмірність. Таким чином, в дисертаційній роботі містяться наступні нові наукові результати: 1. Наведено алгоритм зображення ультраметричного простору кореневим деревом, часова складність якого O(n5). 2. Для довільного скінченного ультраметричного простору показано, що існує поліноміальний алгоритм обчислення його метричної розмірності. 3. Охарактеризовано всі ультраметричні простори розмірність яких дорівнює одиниці. 4. Отримано формулу для обчислення метричної розмірності вінцевого добутку скінченного метричного та рівномірно дискретного метричного просторів. 5. Охарактеризовано метричну розмірність прямої суми метричних просторів скінченного діаметра. 6. Описано метричну розмірність прямого добутку еквідистантних метричних просторів з метриками di, d2 та dTO. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії графів, робототехніці, теорії метричних просторів. Дисертація може бути використана для читання спецкурсів з теорії графів для студентів математичних спеціальностей.In the thesis, the problem of finding of metric dimension for finite ultrametric spaces and for some constructions of metric spaces with conditions of finiteness is described. The definition of the metric dimension for metric spaces was firstly introduced by Blumenthal in 1953. 20 years later Harari and Melter in their paper applied it to the metric spaces defined on graphs. After that, the metric dimension concept found a range of applications, like in combinatorial analysis, robotics, biology, chemistry, etc. In 2013 S. Bau and F. Beardon proceeded with the research of Blumenthal’s ideas about the metric spaces metric dimension. They have studied the metric dimension of the subspaces of the Euclidean space. Later, M. Heydarpour and S. Maghsoudi calculated the metric dimensions of geometric spaces. It is known, that finding the metric dimension of a metric space is an NP-hard problem. There are several ways of conducting metric dimension research. One of those is researching the metric dimension of some specific families of metric spaces or graphs. Second one is metric dimension research of constructions of metric spaces, which is being created using metric spaces for which metric dimension is known. In thesis research is being conducted in both mentioned ways. Namely, the metric dimension of finite ultrametric spaces or non-archimed spaces is completely characterized. It is shown that for an arbitrary finite ultrametric space its metric dimension can be found in polynomial time. Polinomial algorithm for finidng metric dimension for any ultrametric space is described. To do this, isometric image of ultrametric spces to trees was used. It was shown that complexity of such image is O(n5), where n — the number of points of ultrametric space. It is also shown that the metric dimension of the ultrametric space, that is defined on the rooted tree is either equal to the metric dimension of this tree as a graph, or is lesser by one. The paper also fully characterizes ultrametric spaces whose metric dimension is equal to one. In addition to ultrametric spaces, the thesis considers the metric dimension of different constructions of metric spaces. In particular, it is shown that for an arbitrary transform scale the metric dimension of the metric space is equal to metric dimension of its metric transform. A formula for calculating the metric dimension is given for the wreath product of finite metric space and uniformly discrete metric space. When metric dimension of uniformly discrete metric space is equal to inififnity, than metric dimension of its construct is equal to infinity. Besides, for the direct sum of metric spaces of finite diameter, it is shown that its metric dimension will be equal to the sum of the metric dimensions of these spaces. It is shown that for any uniformly discrete metric space metric dimension of their direct sum is equal to two, if, and only if metric dimension of each space is equal to one. The last section also considers the metric dimension of the direct product of equidistant metric spaces with dp d2 та dTO metrics.lt is shown that although these metrics are topologically equivalent, the corresponding metric spaces have different metric dimensions. Thus, the thesis contains the following new scientific results: 1. The algorithm of constructing isometric tree to the ultrametric space by a rooted tree with time complexity O(n5) is given. 2. For an arbitrary finite ultrametric space, it is shown that there is a polynomial algorithm for calculating its metric dimension. 3. All ultrametric spaces whose dimension is equal to one are characterized. 4. The metric dimension of the wreath product of a finite metric space and uniformly discrete metric space is described. 5. The metric dimension of the direct sum of metric spaces of finite diameter is described. 6. Describes the metric dimension of the direct product of equidistant metric spaces with metrics dp d2 and dTO. The practical significance of the results. The results of this work are mainly theoretical. They can be used in graph theory, robotics, theory of metric spaces. The thesis can be used for lecturing special courses of the graph theory for students learning at mathematical specialties.ukметричний простірультраметричний простірметричний базисметрична розмірністькореневе деревочасова складністьполіноміальний алгоритмдисертаціяmetric spaceultrametric spacemetric basismetric dimensionrooted treetime complexitypolynomial algorithmThesis