Бобильова О.В.: Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування. - Рукопис. Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики, Дніпропетровський національний університет Міністерства освіти і науки України, Дніпропетровськ, 2005. В роботі досліджені властивості канонічних передфрактальних графів, породжених повною n-вершинною затравкою, колесом, зіркою, старі ребра яких не перетинаються, і повних канонічних передфрактальних графів, старі ребра яких перетинаються. Вперше були встановлені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, у випадках, коли заміщення вершин відбувається довільним чином, або за певним правилом, а також властивості повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. Запропоновані поліноміальні алгоритми розпізнавання таких графів на передфрактальність. Вперше досліджена складність розв'язання деяких NP-повних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах. Також розглянута NP-складна задача про остові дерева заданої конфігурації на довільних графах. Для цієї задачі побудовано поліноміальний алгоритм, що виділяє оптимальне дідичне дерево в заданному графі, розроблено асимптотично точний алгоритм виділення діадичного дерева в повному графі. Ключові слова: передфрактальний граф, канонічний і неканонічний передфрактальні графи, затравка, операція заміщення вершини затравкою, діадичне дерево, остовний підграф.