Год выпуска: 2012 Автор: М. Х. Дудов Издательство: LAP Lambert Academic Publishing Страниц: 60 ISBN: 9783847376750
Описание
Проблема распознавания изоморфизма является одной из важнейших в теории графов и принадлежит к классу NP-полных задач, включающему в себя задачи, для которых не известны полиномиальные алгоритмы. Несмотря на многочисленные попытки решения, задача проверки изоморфизма графов принадлежит к тем задачам, которые до сих пор не удается классифицировать по сложности. В данной работе предлагается и обосновывается метод распознавания изоморфных графов, вычислительная сложность которого полиномиальна.