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

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

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



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






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


ПДМ. Приложение, 2018, выпуск 11, страницы 16–20 (Mi pdma380)  

Теоретические основы прикладной дискретной математики

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

В. М. Фомичевabc

a Финансовый университет при Правительстве Российской Федерации, г. Москва
b НИЯУ МИФИ, г. Москва
c ФИЦ ИУ РАН, г. Москва

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

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

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


DOI: https://doi.org/10.17223/2226308X/11/5

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

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

Образец цитирования: В. М. Фомичев, “Улучшенная формула универсальной оценки экспонента орграфа”, ПДМ. Приложение, 2018, № 11, 16–20

Цитирование в формате AMSBIB
\RBibitem{Fom18}
\by В.~М.~Фомичев
\paper Улучшенная формула универсальной оценки экспонента орграфа
\jour ПДМ. Приложение
\yr 2018
\issue 11
\pages 16--20
\mathnet{http://mi.mathnet.ru/pdma380}
\crossref{https://doi.org/10.17223/2226308X/11/5}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdma380
  • http://mi.mathnet.ru/rus/pdma/y2018/i11/p16

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика. Приложение
    Просмотров:
    Эта страница:71
    Полный текст:20
    Литература:10
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020