Бобильова Олена Володимирівна. Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування : дис... канд. фіз.-мат. наук: 01.05.01 / Дніпропетровський національний ун-т. - Д., 2005.
Анотація до роботи:
Бобильова О.В.: Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики, Дніпропетровський національний університет Міністерства освіти і науки України, Дніпропетровськ, 2005.
В роботі досліджені властивості канонічних передфрактальних графів, породжених повною n-вершинною затравкою, колесом, зіркою, старі ребра яких не перетинаються, і повних канонічних передфрактальних графів, старі ребра яких перетинаються. Вперше були встановлені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, у випадках, коли заміщення вершин відбувається довільним чином, або за певним правилом, а також властивості повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. Запропоновані поліноміальні алгоритми розпізнавання таких графів на передфрактальність.
Вперше досліджена складність розв’язання деяких NP-повних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах і розглянута NP-складна задача про остові дерева заданої конфігурації на довільних графах. Для цієї задачі побудовано поліноміальний алгоритм, що виділяє оптимальне діадичне дерево в заданному графі, розроблено асимптотично точний алгоритм виділення діадичного дерева в повному графі.
В результаті проведених у роботі досліджень набуло подальшого розвитку вивчення властивостей передфрактальних графів та їх застосування при розв’язанні деяких дискретних задач розпізнавання та задач дискретної оптимізації.
Основні наукові результати і висновки, що були отримані в роботі, полягають у наступному:
1. Встановлено властивості канонічних передфрактальних графів, старі ребра яких не перетинаються, породжених повною n-вершинною затравкою, колесом, зіркою. Розроблено методи та алгоритми розпізнавання довільних графів на передфрактальність і отримані верхні оцінки складності алгоритмів.
2. Вперше отримані властивості повних канонічних передфрактальних графів, старі ребра яких перетинаються і запропоновано поліноміальні алгоритми їх розпізнавання.
Вперше отримані властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, у випадках, коли заміщення вершин відбувається довільним чином або за певним правилом. Запропоновано поліноміальні алгоритми розпізнавання таких графів на передфрактальність.
Досліджені властивості неканонічних передфрактальних графів з довільною кількістю вершин, що заміщюються, старі ребра яких перетинаються. Розглянуто випадки, коли в якості затравки може виступати як одна затравка, так і їх множина. Побудовано поліноміальний алгоритм розпізнавання графів такого типу на передфрактальність. Наведено приклад застосування цього алгоритму при дослідженні певних біологічних процесів, а саме показано, що наведений алгоритм розпізнавання може застосовуватися при моделюванні росту клітин ракових пухлин.
Вперше досліджена складність розв’язання дискретних задач розпізнавання (про вершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах. Наведено теореми про поліноміальну розв‘язність цих задач на даному класі графів, доведення яких мають конструктивний характер.
Вперше розглянута NP-важка задача про остові дерева обмеженого ступеню на довільних графах. Для цієї задачі розроблено поліноміальний алгоритм, що виділяє оптимальне діадичне дерево в заданому графі і наведено обгрунтування достатніх умов його статистичної ефективності. Також було запропоновано асимптотично точний алгоритм та наведено імовірнісний аналіз обгрунтування умов його асимптотичної точності.
Результати, представлені у дисертаційній роботі, мають як теоретичний так і практичний інтерес і можуть використовуватися при подальшому вивченні передфрактальних графів.
Публікації автора:
Киселева Е.М., Бобылева Е.В. Обобщенный алгоритм распознавания предфрактального графа // Проблемы управления и информатики. – 2005. – № 2. – С. 82 – 92.
Бобылева Е.В. Алгоритмы распознавания графов на предфрактальность // Питання прикладної математики і математичного моделювання. – Д.:ДНУ, 2003. – С. 9–15.
Бобылева Е.В. О полиномиально разрешимых подклассах NP-полных задач на предфрактальных графах // Питання прикладної математики і математичного моделювання. – Д.:ДНУ, 2004. – С. 12–27.
Бобылева Е.В., Черепинский К.М. Програмная реализация алгоритмов решения задач распознавания на предфрактальных графах // Системні технології. Регіональний міжвузівський збірник наукових праць. – Дніпропетровськ, 2004. – № 4. – С. 17 – 24.
Бобылева Е.В. Алгоритмы с оценками для задачи о диадическом дереве // Вісник запорізького державного університету. – Запоріжжя: ЗДУ, 2004. – № 2. – С. 5-9.
Киселева Е.М., Бобылева Е.В. Задача распознавания неканонического предфрактального графа // Тези доповідей IІ Міжнародної науково-практичної конференції ”Математичне та програмне забеспечення інтелектуальних систем”. – Д.: ДНУ, 2004. – С. 54 – 55.
Бобылева Е.В. Исследование неканонических предфрактальных графов // Материалы VIII-го международного семинара ”Дискретная математика и ее приложения”. (2–6 февраля, 2004) – М: МГУ, 2004. – С. 326–329.
Бобылева Е.В. Распознавание пространственных графов на предфрактальность // Тези доповідей I Всеукраїнської науково-практичної конференції ”Математичне та програмне забеспечення інтелектуальних систем”. – Д.: ДНУ, 2003. – С. 12.
