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

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