RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2019, номер 43, страницы 115–123 (Mi pdm656)  

Прикладная теория графов

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

В. М. Фомичев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$. Доказана оценка $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$.

Ключевые слова: число Фробениуса, примитивный граф, экспонент орграфа.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-01-00226_а
Работа поддержана грантом РФФИ № 16-01-00226.


DOI: https://doi.org/10.17223/20710410/43/8

Полный текст: PDF файл (688 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.17

Образец цитирования: В. М. Фомичев, “Об улучшенной универсальной оценке экспонентов орграфов”, ПДМ, 2019, № 43, 115–123

Цитирование в формате AMSBIB
\RBibitem{Fom19}
\by В.~М.~Фомичев
\paper Об улучшенной универсальной оценке экспонентов орграфов
\jour ПДМ
\yr 2019
\issue 43
\pages 115--123
\mathnet{http://mi.mathnet.ru/pdm656}
\crossref{https://doi.org/10.17223/20710410/43/8}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm656
  • http://mi.mathnet.ru/rus/pdm/y2019/i1/p115

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:58
    Полный текст:26
    Литература:5
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020