Сложность задачи о существовании сюръективного гомоморфизма на смешанно-ориентированные рефлексивные циклы

Корчагин Н. П.
Корчагин Никита Павлович
выпускник аспирантуры каф. математической теории интеллектуальных систем мех.-мат. ф-та МГУ

Получена: 25.03.2026

Опубликована: 2025 год, том 29, выпуск 4, С. 102–134

Скачать полный текст

Аннотация

Для графа \(H\) в задаче \(Surj-Hom(H)\) по данному графу \(G\) требуется определить, существует ли сюръективный гомоморфизм из \(G\) на \(H\). В данной работе мы изучаем сложность задачи \(Surj-Hom\) для графов, которые получаются из неориентированных циклов добавлением ориентации некоторым рёбрам, и в которых каждая вершина содержит петлю. Мы рассматриваем задачу \(Surj-Hom\) как частный случай массовой задачи сюръективного удовлетворения ограничениям \(SCSP\). Мы вводим свойство, которое позволяет определять сложность \(SCSP\) с помощью сведения. Мы используем это свойство и определяем сложность \(Surj-Hom\) для всех рассматриваемых циклов, кроме трёх циклов длины \(4\), \(5\) и \(6\).

Ключевые слова: cюръективный гомоморфизм графов, сложность вычислений, удовлетворение ограничениям, полиморфизм.

BibTeX 
@article{IS-Korchagin2025,
  author  = {Корчагин, Никита Павлович},
  title   = {{Сложность задачи о существовании сюръективного гомоморфизма на
смешанно-ориентированные рефлексивные циклы}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2025},
  volume  = {29},
  number  = {4},
  pages   = {102--134},
}
AMSBIB 
\RBibitem{IS-Korchagin2025}
\by Н.\,П.~Корчагин
\paper Сложность задачи о существовании сюръективного гомоморфизма на
смешанно-ориентированные рефлексивные циклы
\jour Интеллектуальные системы. Теория и приложения
\yr 2025
\vol 29
\issue 4
\pages 102--134
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover