|
ПДМ, 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Я. Э. Авезова, “О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований”, ПДМ. Приложение, 2017, № 10, 60–62
-
В. М. Фомичёв, Я. Э. Авезова, А. М. Коренева, С. Н. Кяжин, “Примитивность и локальная примитивность орграфов и неотрицательных матриц”, Дискретн. анализ и исслед. опер., 25:3 (2018), 95–125
; 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 -
Я. Э. Авезова, “Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров”, ПДМ. Приложение, 2018, № 11, 102–104
-
Я. Э. Авезова, “Свойства примитивных множеств ориентированных графов с общим множеством контуров”, ПДМ, 2019, № 43, 101–114
|
Просмотров: |
Эта страница: | 162 | Полный текст: | 54 | Литература: | 22 |
|