Registration Number
0822U100874, PhD dissertation
Status
Доктор філософії
Date
23-06-2022
popup.evolution
.
Title
Metric dimension of finite ultrametric and metric spaces
Author
Ponomarchuk Bogdan Serhiovych,
popup.head Oliinyk Bohdana Vitaliivna
popup.opponent Bondarenko Yevhen Volodymyrovych
popup.opponent Varbanets Serhii Pavlovych
popup.review Malaschonok Gennady I.
popup.review Kriukova Galyna V.
popup.rada
National University of Kyiv-Mohyla Academy
Description
У дисертаційній роботі розглянуто задачу пошуку метричної розмірності для скінченних ультраметричних просторів, а також описано метричну розмірність для деяких конструкцій метричних просторів з умовами скінченності.
Визначення метричної розмірності метричного простору було запропоноване Блюменталем в 1953 році.20 років потому Харарі та Мелтер у своїй роботі застосували це визначення до метричних просторів визначених графами. Після чого, концепт метричної розмірності знайшов широке коло застосувань: комбінаторний аналіз, робототехніка, біологія, хімія та інші.
У 2013 році С. Бау та Ф. Беардон продовжили ідеї Блументаля щодо дослідження метричної розмірності метричних просторів. Вони вивчали метричну розмірність підпросторів Евклідового простору. Пізніше, М. Хейдарпур та С. Магсауді підрахували метричну розмірність геометричних просторів.
Відомо що, пошук метричної розмірності метричного простору є NP-складною задачею. Є декілька шляхів дослідження метричної розмірності. Один з них – дослідження метричної розмірності для певних родин метричних просторів чи графів. Другим підходом є дослідження метричної розмірності конструкцій метричних просторів, що побудовані на основі метричних просторів, метрична розмірність яких вже відома.
У дисертаційній роботі дослідження здійснюються в обох описаних вище напрямках. А саме повністю охарактеризовано метричну розмірність скінченних ультраметричних або неархімедових просторів. Показано, що для довільного скінченного ультраметричного простору його метрична розмірність може бути знайдена за поліноміальний час. Наведено поліноміальний алгоритм знаходження метричної розмірності для довільного ультраметричного простору. Для побудови цього алгоритму було використано ізометричне зображення ультраметричних просторів деревами. Показано, що складність побудови такого зображення дорівнює О(n5), де n – кількість точок ультраметричного простору. Також доведено, що метрична розмірність ультраметричного простору, який визначається на кореневому дереві, або дорівнює метричній розмірності цього дерева як графа, або на одиницю менше. В роботі також повністю описано ультраметричні простори метрична розмірність яких дорівнює одиниці.
Окрім ультраметричних просторів в дисертаційній роботі розглянуто метричну розмірність різних конструкцій метричних просторів. Зокрема показано, що для довільної шкали трансформації метрична розмірність метричного простору дорівнює метричній розмірності його трансформації.
Наведено формулу для підрахунку метричної розмірності вінцевого добутку скінченного метричного простору і рівномірно дискретного метричного простору. У випадку коли метрична розмірність рівномірно дискретно метричного простору дорівнює нескінченності, метрична розмірність конструкції також дорівнює нескінченності. Крім того, для прямої суми метричних просторів скінченого діаметра показано, що її метрична розмірність дорівнюватиме сумі метричних розмірностей цих просторів. Показано, що для довільних метричних просторів скінченного діаметра метрична розмірність їх прямої суми дорівнює двом тоді і тільки тоді коли метрична розмірність кожного з просторів дорівнює 1. В останньому розділі також розглянуто метричну розмірність прямого добутку еквідистантних метричних просторів з метриками d1, d2 та d∞. Показано, що хоча ці метрики є топологічно еквівалентними, відповідні метричні простори мають різну метричну розмірність.
Таким чином, в дисертаційній роботі містяться наступні нові наукові результати:
1. Наведено алгоритм зображення ультраметричного простору кореневим деревом, часова складність якого О(n5).
2. Для довільного скінченного ультраметричного простору показано, що існує поліноміальний алгоритм обчислення його метричної розмірності.
3. Охарактеризовано всі ультраметричні простори розмірність яких дорівнює одиниці.
4. Отримано формулу для обчислення метричної розмірності вінцевого добутку скінченного метричного та рівномірно дискретного просторів.
5. Охарактеризовано метричну розмірність прямої суми метричних просторів скінченного діаметра.
6. Описано метричну розмірність прямого добутку еквідистантних метричних просторів з метриками d1, d2 та d∞.
Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії графів, робототехніці, теорії метричних просторів.
Дисертація може бути використана для читання спецкурсів з теорії графів для студентів математичних спеціальностей.
Ключові слова: метричний простір, ультраметричний простір, метричний базис, метрична розмірність, кореневе дерево, часова складність, поліноміальний алгоритм.
Registration Date
2022-07-19
popup.nrat_date
2022-07-19 / 2026-07-01
