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

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

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



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






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


ПДМ, 2017, номер 35, страницы 89–101 (Mi pdm570)  

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

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

Условия примитивности и оценки экспонентов множеств ориентированных графов

Я. Э. Авезоваa, В. М. Фомичевabc

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

Аннотация: Исследованы вопросы минимизации заданного примитивного множества неотрицательных матриц порядка $n$ ($n$-вершинных орграфов), где минимизация понимается как определение минимальных примитивных подмножеств. Получен универсальный критерий примитивности множества орграфов $\hat\Gamma=\{\Gamma_1,…,\Gamma_p\}$, $p>1$, выраженный через характеристики мультиграфа $\Gamma_1\cup…\cup\Gamma_p$, в котором каждая дуга орграфа $\Gamma_i$ помечена символом $i$, $i=1,…,p$. Показано, что задача распознавания примитивности множества орграфов алгоритмически разрешима. Для частного класса множеств, когда орграфы $\Gamma_1,…,\Gamma_p$ содержат общее множество контуров, получен ряд достаточных условий примитивности множества $\hat\Gamma$. Для множества орграфов $\hat\Gamma=\{\Gamma_0,…,\Gamma_{n-1}\}$, где $\Gamma_i$ – граф с множеством вершин $\{0,…,n-1\}$, имеющий гамильтонов контур $(0,…,n-1)$ и дугу $(i,(i+l)\mod n)$, где $n\geq l>1$, $i=0,…,n-1$, уточнён критерий примитивности (множество орграфов $\hat\Gamma$ примитивное тогда и только тогда, когда НОД$(n,l-1)=1$) и в случае примитивности получены оценки экспонента: $n-1\leq\exp\hat\Gamma\leq 2n-2$. Минимальное примитивное подмножество множества $\hat\Gamma$, на котором достигается верхняя оценка экспонента, содержит не более $n/d$ орграфов, где $d=НОД(n,l)$.

Ключевые слова: граф Виландта, примитивное множество матриц (графов), экспонент графа.

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

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

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

Образец цитирования: Я. Э. Авезова, В. М. Фомичев, “Условия примитивности и оценки экспонентов множеств ориентированных графов”, ПДМ, 2017, № 35, 89–101

Цитирование в формате AMSBIB
\RBibitem{AveFom17}
\by Я.~Э.~Авезова, В.~М.~Фомичев
\paper Условия примитивности и оценки экспонентов множеств ориентированных графов
\jour ПДМ
\yr 2017
\issue 35
\pages 89--101
\mathnet{http://mi.mathnet.ru/pdm570}
\crossref{https://doi.org/10.17223/20710410/35/8}


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

    ОТПРАВИТЬ: 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. Я. Э. Авезова, “О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований”, ПДМ. Приложение, 2017, № 10, 60–62  mathnet  crossref
    2. В. М. Фомичёв, С. Н. Кяжин, А. М. Коренева, Я. Э. Авезова, “Примитивность и локальная примитивность орграфов и неотрицательных матриц”, Дискретн. анализ и исслед. опер., 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
    3. Я. Э. Авезова, “Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров”, ПДМ. Приложение, 2018, № 11, 102–104  mathnet  crossref
    4. Я. Э. Авезова, “Свойства примитивных множеств ориентированных графов с общим множеством контуров”, ПДМ, 2019, № 43, 101–114  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:145
    Полный текст:52
    Литература:22
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019