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

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

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



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






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


ПДМ, 2016, номер 3(33), страницы 78–84 (Mi pdm551)  

Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

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

Новая универсальная оценка экспонентов графов

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

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

Аннотация: Получена новая универсальная оценка экспонентов $n$-вершинных примитивных орграфов через характеристики содержащихся в орграфе контуров $C_1,…,C_k$ длины $l_1,…,l_k$ соответственно, где $(l_1,…,l_k)=1$. Показано, что $\exp\Gamma\leq n(r+1)+g(l_1,…,l_k)+L$, где $r$ – число компонент связности орграфа $C_1\cup…\cup C_k$; $g(l_1,…,l_k)$ – число Фробениуса; $L$ – линейная комбинация длин определённых контуров орграфа $\Gamma$. Дано уточнение оценки для некоторых частных случаев. Приведены примеры оценок экспонентов орграфов. Полученная универсальная оценка для многих $n$-вершинных примитивных орграфов улучшает известные оценки. Порядок её величины варьируется от $\mathrm O(n)$ до $\mathrm O(n^2)$. Оценка принимает наибольшие значения порядка $\mathrm O(n^2)$, только если кратчайший контур примитивной системы имеет длину порядка $\mathrm O(n)$. На графах Виландта полученная оценка совпадает с оценкой Виландта.

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

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


DOI: https://doi.org/10.17223/20710410/33/6

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

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

Образец цитирования: В. М. Фомичев, “Новая универсальная оценка экспонентов графов”, ПДМ, 2016, № 3(33), 78–84

Цитирование в формате AMSBIB
\RBibitem{Fom16}
\by В.~М.~Фомичев
\paper Новая универсальная оценка экспонентов графов
\jour ПДМ
\yr 2016
\issue 3(33)
\pages 78--84
\mathnet{http://mi.mathnet.ru/pdm551}
\crossref{https://doi.org/10.17223/20710410/33/6}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm551
  • http://mi.mathnet.ru/rus/pdm/y2016/i3/p78

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. С. Н. Кяжин, “О применении условий локальной примитивности и оценок локальных экспонентов орграфов”, ПДМ, 2016, № 4(34), 81–98  mathnet  crossref
    2. Я. Э. Авезова, В. М. Фомичев, “Условия примитивности и оценки экспонентов множеств ориентированных графов”, ПДМ, 2017, № 35, 89–101  mathnet  crossref
    3. А. М. Коренева, “О примитивности перемешивающих орграфов регистров сдвига с двумя обратными связями”, ПДМ, 2017, № 37, 32–51  mathnet  crossref
    4. В. М. Фомичёв, Я. Э. Авезова, А. М. Коренева, С. Н. Кяжин, “Примитивность и локальная примитивность орграфов и неотрицательных матриц”, Дискретн. анализ и исслед. опер., 25:3 (2018), 95–125  mathnet  crossref  elib; V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Industr. Math., 12:3 (2018), 453–469  crossref
    5. В. М. Фомичев, “Улучшенная формула универсальной оценки экспонента орграфа”, ПДМ. Приложение, 2018, № 11, 16–20  mathnet  crossref
    6. В. С. Григорьев, “О перемешивающих графах нелинейных подстановок двоичных регистров сдвига”, ПДМ. Приложение, 2018, № 11, 6–9  mathnet  crossref
    7. Я. Э. Авезова, “Свойства примитивных множеств ориентированных графов с общим множеством контуров”, ПДМ, 2019, № 43, 101–114  mathnet  crossref
    8. В. М. Фомичев, “Об улучшенной универсальной оценке экспонентов орграфов”, ПДМ, 2019, № 43, 115–123  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:134
    Полный текст:61
    Литература:17
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020