Реєстраційний номер
0597U000227, Докторська дисертація
На здобуття
д.ф.-м.н.
Дата захисту
23-05-1997
Статус
Захищена
Назва роботи
Числовой подход к решению некоторых задач теории графов
Здобувач
Донец Г.А.,
Керівник Шор Н.З.
Опонент Андон Ф.И.
Опонент Летичевский А.А.
Опонент Перепелица В.А.
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Институт программных систем НАН Украины
Опис
Объект исследования: Арифметические графы и проблема раскраски плоских графов. Цель исследования: Исследование нумерации графов, которая дает возможность для создания более совершенных алгоритмов, применение теории конечных полей к решению проблемы раскраски плоских графов. Методы исследования и аппаратура: Теория графов, комбинаторика, теория кодирования, теория конечных полей. Теоретические результаты и новизна: Разработаны новые методы исследования арифметических графов, найдены оптимальные представления некоторых классов арифметических графов; разработан новый подход к решению проблемы четырех красок с помощью систем уравнений и неравенств в полях из двух и трех элементов. Практические результаты и новизна: Представления графов в классе арифметических графов дает возможность усовершенствовать алгоритмы на графах; разработаны два алгоритма раскраски плоских графов четырьмя красками, которые являются лучшими в настоящее время в мировой литературе. Предмет и степень внедрения: Методы кодирования графов и алгоритмы раскраски плоских графов. Эффективность внедрения: Расчеты и тестовые примеры показали явное преимущество разработанных алгоритмов раскраски плоских графов по сравнению с известными. Сфера (область) использования: Математическое обеспечение для задач теории графов и вузы с математическим уклоном.
Дата реєстрації
1997-12-22
Додано/оновлено в НРАТ
2020-05-18 / 2026-06-30
