Условия примитивности и оценки экспонентов множеств ориентированных графов | Прикладная дискретная математика. 2017. № 35. DOI: 10.17223/20710410/35/8

Исследованы вопросы минимизации заданного примитивного множества неотрицательных матриц порядка n (n-вершинных орграфов), где минимизация понимается как определение минимальных примитивных подмножеств. Получен универсальный критерий примитивности множества орграфов Г = {Г1,..., Г_р}, p > 1, выраженный через характеристики мультиграфа Г1 U ... U Г_р, в котором каждая дуга орграфа Г помечена символом i, i = 1, ...,p. Показано, что задача распознавания примитивности множества орграфов алгоритмически разрешима. Для частного класса множеств, когда орграфы Г₁,..., Г_р содержат общее множество контуров, получен ряд достаточных условий примитивности множества Г. Для множества орграфов Г = {Г₀,..., Г_п-1}, где Г - граф с множеством вершин {0,..., n - 1}, имеющий гамильтонов контур (0,..., n - 1) и дугу (i, (i+l) mod n), где n ^ l > 1, i = 0,... ,n - 1, уточнён критерий примитивности (множество орграфов Г примитивное тогда и только тогда, когда НОД(п,1 - 1) = 1) и в случае примитивности получены оценки экспонента: n - 1 ^ expГ ^ 2n - 2. Минимальное примитивное подмножество множества Г, на котором достигается верхняя оценка экспонента, содержит не более n/d орграфов, где d = НОД(п, l).