Донец Г. . Числовой подход к решению некоторых задач теории графов

Объект исследования: Арифметические графы и проблема раскраски плоских графов. Цель исследования: Исследование нумерации графов, которая дает возможность для создания более совершенных алгоритмов, применение теории конечных полей к решению проблемы раскраски плоских графов. Методы исследования и аппаратура: Теория графов, комбинаторика, теория кодирования, теория конечных полей. Теоретические результаты и новизна: Разработаны новые методы исследования арифметических графов, найдены оптимальные представления некоторых классов арифметических графов; разработан новый подход к решению проблемы четырех красок с помощью систем уравнений и неравенств в полях из двух и трех элементов. Практические результаты и новизна: Представления графов в классе арифметических графов дает возможность усовершенствовать алгоритмы на графах; разработаны два алгоритма раскраски плоских графов четырьмя красками, которые являются лучшими в настоящее время в мировой литературе. Предмет и степень внедрения: Методы кодирования графов и алгоритмы раскраски плоских графов. Эффективность внедрения: Расчеты и тестовые примеры показали явное преимущество разработанных алгоритмов раскраски плоских графов по сравнению с известными. Сфера (область) использования: Математическое обеспечение для задач теории графов и вузы с математическим уклоном.