Почтовый адрес: САФУ, Редакция «Arctic Environmental Research», наб. Северной Двины, 17, г. Архангельск, Россия, 163002
Местонахождение: Редакция «Arctic Environmental Research», наб. Северной Двины, 17, ауд. 1410а, г. Архангельск

Тел: (818-2) 21-61-21 
Сайт: http://aer.narfu.ru/
e-mail: vestnik_est@narfu.ru;
            vestnik@narfu.ru

О журнале

Алгоритм проверки изоморфизма полурешеток с использованием инвариантов теории графов. С. 368–375

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

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

УДК

519.178:512.53

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

Л.В. Зяблицева*, С.А. Пестов*
*Северный (Арктический) федеральный университет имени М.В. Ломоносова (г. Архангельск)
Контактное лицо: Зяблицева Лариса Владимировна, адрес: 163002, г. Архангельск, ул. Урицкого, д. 68, корп. 3; e-mail: zlarisav@yandex.ru

Аннотация

Изоморфизм двух коммутативных идемпотентных полугрупп (полурешеток) можно устанавливать с помощью алгоритмов теории графов. Для этого полурешеткам сопоставляется граф, и в том случае, когда полученный граф является деревом, для проверки изоморфизма таких полурешеток применяются известные алгоритмы проверки изоморфизма деревьев. Еще один из видов графов, для которых существует алгоритм проверки изоморфизма (отличающийся от алгоритмов полного перебора), – планарные графы. В статье решен вопрос о том, является ли граф произвольной полурешетки деревом, планарным графом. Реализован алгоритм, с помощью которого можно выяснить, изоморфны ли полурешетки, графы которых являются деревьями. Данный алгоритм может быть применен и для произвольных полурешеток, но в этом случае для изоморфных полурешеток ответ будет верным, а для неизоморфных может быть ошибочным. В статье показано, какое кодовое слово выдается произвольной полурешетке; и то, что это кодовое слово может служить инвариантом для проверки изоморфизма такой полурешетки. Далее рассмотрены другие инварианты теории графов, которые можно успешно применить для полурешеток, а также решен вопрос о полноте представленной системы инвариантов. Созданная в итоге программа для двух произвольных полурешеток, заданных таблицами Кэли, дает информацию о графах (их инварианты), определяет, изоморфны ли они; в случае изоморфизма выдается биективное отображение элементов этих полурешеток. С помощью программы были проанализированы все полугруппы от первого до восьмого порядков, для каждого порядка найдено число полурешеток, графы которых являются деревьями; показано, что для полурешеток не выше восьмого порядка совокупность предложенных инвариантов является полной системой инвариантов.

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

полугруппы, графы, изоморфизм графов, изоморфизм полугрупп, полурешетки, деревья, планарные графы
Скачать статью (pdf, 2.4MB )

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

  1. Зяблицева Л.В., Пестов С.А. Применение алгоритмов проверки изоморфизма графов в теории полу- групп // Вестн. Сев. (Арктич.) федер. ун-та. Сер.: Естеств. науки. 2016. № 4. С. 69–74. 
  2. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. Т. 1. М.: Мир, 1972. 285 с. 
  3. Оре О. Теория графов. М.: Наука, 1968. 352 с. 
  4. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с. 
  5. Пономаренко И.Н. Проблема изоморфизма графов: Алгоритмические аспекты. СПб., 2010. 57 с. URL: http:// logic.pdmi.ras.ru/csclub/sites/default/files/graph_isomorphism_ponomarenko_lecture_notes.pdf (дата обращения: 18.09.2015). 
  6. Smal А. Explanation for “Tree isomorphism” talk. Saint-Petersburg, 2008. 10 p. URL: http://www14. informatik. tumuenchen.de/konferenzen/Jass08/courses/1/smal/Smal_Paper.pdf (дата обращения: 10.09.2015). 
  7. Хопкрофт Дж.Е., Тарьян Р.Е. Изоморфизм планарных графов // Кибернетический сборник: сб. переводов. Новая серия. Вып. 12. М.: Мир, 1975. С. 39–61. 
  8. Таран И.А., Корабельщикова С.Ю. Построение диаграммы подполей конечного поля // Современные исследования в области естественных и технических наук: Междисциплинарный поиск и интеграция: материалы II науч.-практ. всерос. конф. (школы-семинара) молодых ученых (Тольятти, 1–3 декабря 2015 г.). Тольятти, 2015. С. 122–125. 
  9. Корабельщикова С.Ю., Мельников Б.Ф. Максимальные префиксные коды и подклассы класса контекстно-свободных языков // Вестн. Сев. (Арктич.) федер. ун-та. Сер.: Естеств. науки. 2015. № 1. С. 121–129.