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

  Скачати повний текст