Эта публикация цитируется в
1 статье
Прикладная теория графов
Об улучшенной универсальной оценке экспонентов орграфов
В. М. Фомичевabc a Финансовый университет при Правительстве Российской Федерации, г. Москва, Россия
b Национальный исследовательский ядерный университет «МИФИ», г. Москва, Россия
c Институт проблем информатики ФИЦ ИУ РАН, г. Москва, Россия
Аннотация:
Способ универсальной оценки экспонента
$n$-вершинного примитивного орграфа, предложенный А. Далмэджем и Н. Мендельсоном (1964), сохранял до настоящего времени статус наилучшего среди всех известных универсальных оценок. Этот способ использует множество контуров
$\hat{C}$ орграфа, длины которых равны
$l_1,\ldots,l_m$, где НОД
$(l_1,\ldots,l_m)=1$, и множество длин кратчайших путей
$\{r_{i,j}(\hat{C}): 1\leq i,j\leq n\}$, проходящих из вершины
$i$ в вершину
$j$ через множество контуров
$\hat{C}$.
Улучшение этого способа использует множество контуров
$\hat{C}$, где НОД
$(l_1,\ldots,l_m)=d\geq 1$, и множество длин кратчайших путей $\{r_{i,j}^{s/d}(\hat{C}): s=0,\ldots,d-1; 1\leq i,j\leq n\}$ из вершины
$i$ в вершину
$j$, проходящих через множество контуров
$\hat{C}$ и образующих полную систему вычетов по модулю
$d$. Доказана оценка $\text{exp}\,\Gamma\leq 1+\hat{F}(L(\hat{C}))+R(\hat{C})$, где
$\hat{F}(L)=d\cdot F(l_1/d,\ldots, l_m/d)$;
$F(a_1,\ldots,a_m)$ — число Фробениуса; $R(\hat{C})=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat{C})\}$. Построен класс орграфов с множеством вершин
$\{0,\ldots,2k-1\}$,
$k>2$, для которых новая оценка принимает значение
$2k$ при чётных
$k$ и
$2k-1$ при нечётных
$k$, в то время как оценка Далмэджа и Мендельсона принимает значение
$3k-2$ при чётных
$k$ и
$3k-3$ при нечётных
$k$.
Ключевые слова:
число Фробениуса, примитивный граф, экспонент орграфа.
УДК:
519.17
DOI:
10.17223/20710410/43/8