CC..png

16plus.png

Юридический и почтовый адрес учредителя и издателя: САФУ им. М.В. Ломоносова, наб. Северной Двины, д. 17, г. Архангельск, Россия, 163002
Адрес редакции: «Вестник САФУ. Серия "Гуманитарные и социальные науки"», ул. Урицкого, 56, г. Архангельск

Тел: (818-2) 21-61-00, вн. 18-20 
Сайт: https://vestnikgum.ru
e-mail: vestnik_gum@narfu.ru              

о журнале

Применение алгоритмов проверки изоморфизма графов в теории полугрупп. C. 69–74

 Версия для печати

Рубрика: Физика, Математика, Информатика

Скачать статью (pdf, 1.5MB )

УДК

519.178; 512.53

Сведения об авторах

Л.В. Зяблицева*, С.А. Пестов*
*Северный (Арктический) федеральный университет имени М.В. Ломоносова

Аннотация

Одной из наиболее интересных проблем теории полугрупп является проблема изоморфизма для данного класса полугрупп, состоящая в существовании алгоритма (отличающегося от алгоритма полного перебора), распознающего для любых двух полугрупп из данного класса, изоморфны они или нет. Аналогичная проблема есть и в теории графов, причем для некоторых классов графов этот вопрос решен. В статье рассмотрены полугруппы, являющиеся полурешетками, для проверки изоморфизма которых можно применить известные алгоритмы проверки изоморфизма графов. Описано, как для таких полугрупп можно найти соответствующий им граф. Этот граф может оказаться деревом, и в этом случае для проверки изоморфизма полугрупп можно применить известные алгоритмы проверки изоморфизма деревьев. Сформулирован и доказан критерий того, в каком случае граф полурешетки является деревом. Далее обосновывается выбор алгоритма проверки изоморфизма деревьев, описан этот алгоритм, представлена программа, написанная на языке Haskell, реализующая его. чтобы применить выбранный алгоритм для проверки изоморфизма полурешеток, необходимо сначала полурешетке сопоставить дерево. Для этого авторами разработан и реализован также на языке Haskell необходимый алгоритм. Созданная в итоге программа для двух полурешеток, заданных таблицами Кэли, работает следующим образом: она выводит структуру соответствующих полурешеткам деревьев, каноническое имя полученных деревьев, проверяет изоморфизм деревьев, а значит, и полурешеток. При этом выбор и реализация алгоритмов являются эффективными, программа в течение нескольких секунд определяет изоморфизм полурешеток с трехзначным числом элементов.

Ключевые слова

полугруппы; полурешетки; графы; деревья; изоморфизм полугрупп; изоморфизм графов; алгоритмы проверки изоморфизма полугрупп, графов, деревьев

Список литературы

  1. Зяблицева Л.В., Корабельщикова С.Ю., Попов И.Н. Некоторые специальные полугруппы и их гомоморфизмы. Архангельск, 2013. 128 с. 
  2. Артамонов В.А., Салий В.Н., Скорняков Л.А. Общая алгебра. Т. 2. М., 1991. 480 с. 
  3. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов. М., 1979. 521 с. 
  4. Пономаренко И.Н. Проблема изоморфизма графов: Алгоритмические аспекты. СПб., 2010. 57 с. URL: http:// logic.pdmi.ras.ru/csclub/sites/default/files/graph_isomorphism_ponomarenko_lecture_notes.pdf (дата обращения: 06.12.2016). 
  5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: учеб. пособие. М., 2006. 416 с. 
  6. Smal A. Explanation for «Tree isomorphism” talk. Saint-Petersburg, 2008. 10 p. URL: http://logic.pdmi.ras. ru/~smal/files/smal_jass08.pdf (дата обращения: 06.12.2016).