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

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

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

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

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

Основні здобутки:

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

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

3. Досліджена структура та властивості однорідних NM-графів. Досліджені однорідні натуральні модульні графи, які складаються з композиції гамільтонівських циклів, а також з комбінації гамільтонівських циклів і фактор-графів. Визначені підмножини натуральних модульних графів, які не мають собі ізоморфних.

4. Уперше повністю розв’язана задача знаходження ізоморфізму однорідних NM-графів з кількістю твірних, яка не перевищує 5. На основі теорії розв’язання квадратичних рівнянь в скінченних полях розроблено метод розв’язання задачі ізоморфізму для однорідних NM-графів.

5. Уперше побудовано поліноміальний алгоритм визначення ізоморфізму довільних однорідних NM-графів.

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

7. Визначені нижні та верхні оцінки хроматичного числа натуральних модульних графів, які не залежать від кількості вершин графа. Розроблено метод розфарбування NM-графів, який дозволяє ефективно розфарбовувати граф довільною кількістю кольорів.

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