Реєстраційний номер
0405U003434, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
02-09-2005
Статус
Захищена
Назва роботи
Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування
Здобувач
Бобильова Олена Володимирівна,
Керівник Кісельова Олена Михайлівна
Опонент Перепелиця Віталій Опанасович
Опонент Канаєва Наталія Миколаївна
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Дніпропетровський національний університет імені Олеся Гончара
Опис
Дисертаційна работа присвячена вивченню передфрактальних графів. Отримані властивості канонічних передфрактальних графів, що породжені повною n-вершинною затравкою, колесом, зіркою. Досліджені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, з заданою кількістю вершин, що заміщуються, і повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. На основі отриманих властивостей розроблено методи і поліноміальні алгоритми розпізнавання графів на передфрактальність. Вперше побудовані поліноміальні алгоритми розв’язання деяких NP-повних задач на передфрактальних графах (про вершинне покриття, про домінуючу множину, задачі розбиття на ліси, задачі виділення гамільтонового циклу). Розроблено статистично точний та асимптотично ефективний алгоритми виділення діадичного дерева обмеженого ступеню.
Дата реєстрації
2005-09-19
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-30