Дата публикации: 2018

Дата публикации в реестре: 2020-03-03T18:38:14Z

Аннотация:

Пусть Г = {Г! ,. .. , Гр} — множество орграфов с множеством вершин V, орграф U(p) — объединение орграфов Г U... U Гр без учёта кратности дуг, p > 1, и множество простых контуров C = {Ci ,..., Cm}, m ^ 1, является общим для Г, то есть каждый орграф множества Г содержит все контуры множества C. Для случая C U ... U Cm = V, где C* — множество вершин контура Cj, i = 1 ,..., m, получены критерии примитивности и оценки экспонентов множеств орграфов с общими контурами. При m > 1 множество орграфов Г с общим множеством контуров C примитивное, если и только если орграф U(p) примитивный, и exp Г ^^ ((p — 1)h + 1) exp U(p), где h — показатель Иоор-признака в полугруппе (Г(С)), Г(С) = Ci U ... U Cm (наименьшее натуральное число h, при котором (Г(С)) имеет петли во всех вершинах). При m = 1 критерий примитивности и оценка экспонента уточнены: если все орграфы множества Г имеют общий гамильтонов контур, то множество Г примитивное, если и только если НОД длин всех„ p простых контуров U(p) равен 1, и ехрГ ^ (2n — 1)p + ^ (F(LT) + dT — l), T =1

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2018. № 11. С. 102-104