Вычислительная сложность задачи распознавания изоморфных графов М. Х. Дудов

Проблема распознавания изоморфизма является одной из важнейших в теории графов и принадлежит к классу W-полных задач, включающему в себя задачи, для которых неизвестны полиномиальные алгоритмы. Несмотря на многочисленные попытки решения, задача проверки изоморфизма графов принадлежит к тем задачам, которые до сих пор не удается классифицировать по сложности. В работе предлагается и обосновывается метод распознавания изоморфных графов, вычислительная сложность которого полиномиальна. Это и многое другое вы найдете в книге Вычислительная сложность задачи распознавания изоморфных графов (М. Х. Дудов)