Бобильова О. В. Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування

Дисертаційна работа присвячена вивченню передфрактальних графів. Отримані властивості канонічних передфрактальних графів, що породжені повною n-вершинною затравкою, колесом, зіркою. Досліджені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, з заданою кількістю вершин, що заміщуються, і повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. На основі отриманих властивостей розроблено методи і поліноміальні алгоритми розпізнавання графів на передфрактальність. Вперше побудовані поліноміальні алгоритми розв’язання деяких NP-повних задач на передфрактальних графах (про вершинне покриття, про домінуючу множину, задачі розбиття на ліси, задачі виділення гамільтонового циклу). Розроблено статистично точний та асимптотично ефективний алгоритми виділення діадичного дерева обмеженого ступеню.