2016 г., Том 21, № 6, с.71-88

Обоснована возможность численной реализации проверки изоморфизма графов с помощью сведения ее к проверке равенства модифицированных характеристических полиномов графов. Показано, что при достаточно больших значениях параметра алгоритма, использующего такое сведение, вероятность ошибки при решении им задачи проверки изоморфизма графов пренебрежимо мала. Доказано, что для графов на n вершинах необходимое для численной реализации сравнение значений их модифицированных характеристических полиномов, имеющих экспоненциальное от n количество коэффициентов, может быть проведено за время O(n ⁴ ) при растущей как O(n ² ) длине мантиссы используемых машинных чисел.