E-catalog        

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

Способ универсальной оценки экспонента n-вершинного примитивного орграфа, предложенный А. Далмэджем и Н. Мендельсоном (1964), сохранял до настоящего времени статус наилучшего среди всех известных универсальных оценок. Этот способ использует множество контуров C орграфа, длины которых равны l1, . . . , lm, где НОД(@, . . . , lm) = 1, и множество длин кратчайших путей {ri,j((C) : 1 @ i ,j @ n}, проходящих из вершины i в вершину j через множество контуров C. Улучшение этого способа использует множество контуров C, где НОД(11, . .., lm) = d @ 1, и множество длин кратчайших путей {rs/jd(C) : s = = 0, . . . , d—1; 1 @ i, j @ n} из вершины i в вершину j, проходящих через множество контуров C и образующих полную систему вычетов по модулю d. Доказана оценка exp Г @ 1 + F(L(C)) + R(C), где F(L) = d ■ F(l1/d, . . . , lm/d); F(a1, . .., am) — число Фробениуса; R(C) = maxmax{r//jd(C')}. Построен класс орграфов с множеством вершин {0, . . . , 2k — 1}, k > 2, для которых новая оценка принимает значение 2k при чётных k и 2k — 1 при нечётных k, в то время как оценка Далмэджа и Мендельсона принимает значение 3k — 2 при чётных k и 3k — 3 при нечётных k.