О вычислительной эффективности алгоритма спектрального расщепления проверки изоморфизма графов

Мы рассматриваем эвристический алгоритм проверки изоморфизма графов. Алгоритм основан на последовательном расщеплении кратных собственных значений матриц, сопоставленных графам: матрицы, с которыми работает алгоритм, представляют собой модификации матриц смежности графов. Алгоритм строится на последовательном возмущении матриц и решении связанных с ними систем линейных алгебраических уравнений. Матрицы видоизменёны до положительно определенных, что позволяет решать системы линейных уравнений, связанные с ними. Доказывается вычислительная эффективность алгоритма в одной из принципиально тяжелых для решения задачи проверки изоморфизма графов ситуаций.