E-catalog        

Библиогр.: 3 назв.

Получены условия примитивности и оценки экспонентов для нескольких множеств орграфов Г = (Го,... , Гп-1} с вершинами 0, .. ., n — 1. Критерий: если Г имеет гамильтонов контур (0, . . . ,п — 1) и дугу (i, (i + 1) mod n), n ^ 1 > 1, i = 0, . . . , n — 1, то множество Г примитивное, если и только если НОД(п, 1 — 1) = 1, при этом n — 1 ^ exp Г ^ 2n — 2; если Г имеет также дугу (i, (i + Л) mod n), n ^ A > 1 > 1, i = 0, . . . , n — 1, то множество Г примитивное, если и только если НОД(п , 1 — 1, A — 1) = 1, exp Г ^ (/8n + 1 — 3)/2.
При этом если НОД(п , 1 — 1) = 1, то exp Г ^ n — 1 + max(b, n — b + 1}, где b == (Л — 1)(1 — 1)^(n)-1 mod n и <^(n) — функция Эйлера.
Пусть n чётное, орграф Г при чётных i имеет контур (0, . . . , n — 1) и дугу (i, (i+1) mod n) и при нечётных i имеет контур (n—1,... ,0) и дугу (i, (i+A) mod n).
Тогда если НОД(п , 1 — 1) = 1 или НОД(п , Л + 1) = 1, то множество Г примитивное и exp Г ^ 2n — 2.