Algorithms for the graph isomorphism problem based on graph deregularisation.pdf В задаче проверки изоморфизма графов (задача ИГ) даны два обыкновенных графас одинаковым числом вершин и ребер. Необходимо ответить на вопрос, существуетли такое биективное отображение (изоморфизм) множества вершин одного графана множество вершин второго, которое сохраняло бы смежность соответствующихвершин?По причине неопределенности своего положения в иерархии теории сложности, задачаИГ имеет большое теоретическое значение, а также часто возникает и в приложениях.Алгоритмы решения задачи ИГ используются при решении многих прикладныхзадач: в задачах распознавания образов, в протоколах доказательства с нулевым разглашением;к задаче ИГ может быть сведена и вычислительно-эффективно решеназадача дешифрования шифра двойной перестановки [1]. Поскольку для вычислительносложных случаев задачи ИГ не разработано полиномиальных алгоритмов решения,возможно построение криптографических схем, основанных на вычислительной сложностирешения для них задачи ИГ, например, как в [2].Под последовательной согласованной дерегуляризацией пары графов мы понимаемтакое последовательное изменение элементов матриц смежности графов (весов вершини ребер), вследствие которого понижается мощность групп автоморфизмов графов присохранении равенства некоторых вычисляемых в ходе дерегуляризации инвариантныххарактеристик графов. В докладе рассматриваются полиномиальные схемы алгоритмовдля задачи ИГ, основанные на таком подходе и в качестве инварианта использующиеэлементы обратной матрицы к модифицированной матрице смежности.Предложенные алгоритмы протестированы на библиотеке задач [3]. Не найденопримеров неправильного решения или невозможности нахождения решения представленнымиалгоритмами задачи ИГ для деревьев, случайных, планарных графов, регулярныхk-мерных сеток (k ^ 4) и некоторых других классов графов. Установлено, чтоалгоритм решает и те задачи изоморфизма графов из библиотеки, на которых времяработы алгоритмов Ullman и NAUTY - наиболее эффективных алгоритмов решенияобщего случая задачи ИГ - становится экспоненциальным при некоторой нумерациивершин [4]. Кроме этого, задачаИГ успешно решается предложенными алгоритмами идля сильно регулярных графов из наиболее обширной их библиотеки [5] - эти графыпредставляют собой класс, для которого задача проверки изоморфизма графов имеет наибольшую вычислительную сложность. Получены орбиты групп автоморфизмоввсех графов, представленных в библиотеке [5], что также свидетельствует об эффективностипредложенного подхода.

Скачать электронную версию публикации