Анотація до роботи:

Шулінок І.Е. Розв’язання задач оптимального представлення числових графів та дослідження умов побудови на них ефективних алгоритмів. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2004.

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

У дисертаційній роботі отримані важливі наукові результати, які закономірно й послідовно поєднують теоретичні дослідження властивостей числових графів з практичними розробками відносно застосування цих графів для побудови досконалих алгоритмів на графах загального типу.

Основні здобутки роботи полягають в наступному.

1. Вперше грунтовно описано структуру однорідних натуральних арифметичних графів. За допомогою спеціально побудованого графа розкладу твірних доведено, що одна множина натуральних арифметичних графів шляхом багаторазового застосування операції радіального гомоморфізму зводиться до іншої. Складено декілька таблиць, що дозволяють відтворити за даними параметрами відповідні однорідні натуральні арифметичні графи.

2. Розв’язана задача оптимального представлення дерев першого рангу в класі арифметичних графів. Для цього було побудовано спеціальний двоїстий граф несуміжності, який дозволив звести задачу до розв’язування серії рівнянь у класі лишків за різними модулями, залежними від кількості вершин. Розв’язок цих рівнянь дав можливість перелічити всі можливі оптимальні представлення зазначених дерев.

3. Вперше зформульована загальна задача про оптимальне представлення довільних графів у класі арифметичних графів і пов’язана з нею проблема універсального кодування цих графів. Отримані позитивні результати вирішення першої задачі для нових типів графів і доведено, що кожний розв’язок відомої задачі про різниці є оптимальним розв’язком проблеми про універсальне кодування.

4. Започатковано дослідження такого підкласу числових графів як модульні графи. Вперше отримані важливі результати про структурні властивості цих графів такі як зв’язність графа, цикломатичне число, про існування гамільтонового та ейлерового циклу. Повністю описана якісна структура множини натуральних модульних графів з двома твірними.

5. З практичних міркувань запропоновано загальне, більш розширене визначення числових графів і показано, що багато графів, які застосовуються в галузі розпізнавання образів, математичного моделювання паралельних процесів, теоретичних основ створення інформаційних технологій, можна представити у класі числових графів за розширеним визначенням.

6. Вперше доведено, що такі базові алгоритми теорії графів як пошук в глибину, або в ширину при застосуванні їх до модульних графів мають кращі показники відносно обсягу комп’ютерної пам’яті та швидкодії, ніж при застосуванні їх до традиційних графів.

7. Доведено, що для числових графів можливо створити такі алгоритми, які на відміну від традиційних алгоритмів зводяться лише до видачі відповіді у вигляді списку. Це продемонстровано на двох алгоритмах пошуку в глибину для зв’язаних модульних графів з двома та з довільною кількістю твірних.