Улучшенная формула универсальной оценки экспонента орграфа

Улучшена формула универсальной оценки экспонента $n$-вершинного примитивного орграфа, данная А. Далмэджем и Н. Мендельсоном (1964) с использованием множества контуров, длины которых взаимно простые. Предложенная формула использует в орграфе множество контуров $\hat C$ с множеством длин $L(\hat C)=\{l_1,\dots,l_m\}$, где $d=(l_1,\dots,l_m)\geq1$, и множество длин кратчайших путей $\{r_{i,j}^{s/d}(\hat C)\colon s=0,\dots,d-1\}$ из вершины $i$ в вершину $j$, проходящих через множество контуров $\hat C$ и образующих полную систему вычетов по модулю $d$. Показано, что $\exp\Gamma\leq1+\hat F(L(\hat C))+R(\hat C)$, где $\hat F(L)=d\cdot F(l_1/d,\dots,l_m/d)$; $F(a_1,\dots,a_m)$ – число Фробениуса; $R(\hat C)=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat C)\}$. Указан класс орграфов с множеством вершин $\{0,\dots,2k-1\}$, $k>2$, для которых предложенные оценки экспонентов лучше известных на величину $k-2$.