Третья Всероссийская научная конференция "Омские научные чтения-2019" - Математика

РЕШЕНИЕ ЗАДАЧИ ПРОВЕРКИ ИЗОМОРФИЗМА ГРАФОВ СВЕДЕНИЕМ ЕЁ К ЗАДАЧЕ ПРОВЕРКИ РАВЕНСТВА МОДИФИЦИРОВАННЫХ ХАРАКЕТРИСТИЧЕСКИХ ПОЛИНОМОВ

Пролубников А. В.

Аннотация

Рассматривается задача проверки изоморфизма графов. Графам сопоставляются модифицированные характеристические полиномы и задача сводится к следующей. Необходимо определить, существует ли такая нумерация вершин графов, при которой их модифицированные характеристические полиномы равны. Представлены алгоритмы решения задачи проверки изоморфизма графов, использующие такое сведение. Показано, что можно сравнивать значения полиномов в заданных точках без прямого вычисления значений полиномов, которое имеет экспоненциальную вычислительную сложность.

Комментарии

Комментарии отсутствуют

Вопросы по докладу

Вопросы отсутствуют