• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

О связи строения стационарных подгрупп группы графа и эффективности учёта симметрии при решении переборных задач структурного анализа

Незнанов А. А., Кохов В. А.

Рассматривается один из универсальных методов повышения эффективности решения переборных задач структурного анализа — метод точного учёта симметрии структур, обладающих нетривиальной группой автоморфизмов. Анализируется связь между строением стационарных подгрупп группы автоморфизмов, накладными расходами на учёт симметрии и общей эффективностью решения задачи. В качестве примера рассматривается задача поиска максимального общего фрагмента пары графов. Приводятся наиболее интересные семейства графов с точки зрения учёта симметрии.