Проблема распознавания изоморфизма является одной из важнейших в теории графов и принадлежит к классу W-полных задач, включающему в себя задачи, для которых неизвестны полиномиальные алгоритмы. Несмотря на многочисленные попытки решения, задача проверки изоморфизма графов принадлежит к тем задачам, которые до сих пор не удается классифицировать по сложности. В работе предлагается и обосновывается метод распознавания изоморфных графов, вычислительная сложность которого полиномиальна.
Problema raspoznavanija izomorfizma javljaetsja odnoj iz vazhnejshikh v teorii grafov i prinadlezhit k klassu W-polnykh zadach, vkljuchajuschemu v sebja zadachi, dlja kotorykh neizvestny polinomialnye algoritmy. Nesmotrja na mnogochislennye popytki reshenija, zadacha proverki izomorfizma grafov prinadlezhit k tem zadacham, kotorye do sikh por ne udaetsja klassifitsirovat po slozhnosti. V rabote predlagaetsja i obosnovyvaetsja metod raspoznavanija izomorfnykh grafov, vychislitelnaja slozhnost kotorogo polinomialna.
