Распознавание и проверка изоморфизма циклических турниров за полиномиальное время

Турниром называется ориентированный граф, любая пара вершин которого соединена точно одним направленным ребром; турнир является циклическим, если его группа автоморфизмов содержит перестановку, циклическое разложение которой состоит из единственного цикла, включающего все вершины. В настоящей работе описывается алгоритм, распознающий изоморфизм циклических турниров. Этот алгоритм получает на вход произвольный турнир. Для этого турнира за время полиномиально зависящее от числа его вершин определяется его цикличность, а при её наличии строится канонический вид турнира и образующие его группы автоморфизмов.
Самостоятельный интерес представляет процедура, которая за полиномиальное время для заданной группы перестановок нечетного порядка строит множество всех несопряженных гамильтоновых перестановок. Техника построения основного алгоритма использует как классические результаты теории сложности вычислений с группами перестановок, так и метод $S$-колец Шура. Библ. – 12 назв.