Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/31

Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров

Пусть Г = {Г1,..., Гр} - множество орграфов с множеством вершин V, орграф U(p) - объединение орграфов Г1U... U Гр без учёта кратности дуг, p > 1, и множество простых контуров C = {C1,..., Cm}, m ^ 1, является общим для Г, то есть каждый орграф множества Г содержит все контуры множества C. Для случая C* U ... U Cm = V, где C* - множество вершин контура C, i = 1,..., m, получены критерии примитивности и оценки экспонентов множеств орграфов с общими контурами. При m > 1 множество орграфов Г с общим множеством контуров C примитивное, если и только если орграф U(p) примитивный, и ехрГ ^ ^ ((p - 1)h + 1)expU(p), где h - показатель Рьор-признака в полугруппе (Г(С)), Г(С) = C1 U ... U Cm (наименьшее натуральное число h, при котором (T(C)) имеет петли во всех вершинах). При m = 1 критерий примитивности и оценка экспонента уточнены: если все орграфы множества Г имеют общий гамильто- нов контур, то множество Г примитивное, если и только если НОД длин всех p простых контуров U(p) равен 1, и ехрГ ^ (2n - 1)p + ^ (F(LT)+ dT - ), T =1 где LT = {IT,..., im(T)} - множество длин всех простых контуров орграфа Гт, IT < ... < 1m(T) = n, dT = НОД^т), Lt/dT = №/dr,...,im(T)/dT}, F(Lt) = = dT$(LT/dT), $(LT/dT) - число Фробениуса, т = 1,... ,p.

The criterion of primitivity and exponent bounds for a set of digraphs with common cycles.pdf Введение Пусть Г = {Г1,..., Гр} -множество орграфов с множеством вершин V = {0,... , n - 1}, все дуги орграфа Гт помечены числом т, т = 1,... ,p, p > 1. Множеству Г соответствует мультиграф Г(р) = Г1U... U Гр, в котором любой путь длины s помечен непустым множеством слов длины s. Орграф, полученный из Г(р) удалением всех меток и отождествлением кратных дуг, будем обозначать U(p). Если множество Г примитивное, то мультиграф Г(р) и орграф U(p) сильносвязные [1, 2]. Множество Г примитивное, если и только если при некотором натуральном s существует метка w1... ws (слово длины s в алфавите {1,... ,p}), такая, что имеется путь из i в j с этой меткой при любых i, j G V [3]. Наименьшее такое s называется экспонентом множества Г и обозначается exp Г. Примитивность множества орграфов - одно из обобщений понятия примитивности, которое является ключевым в матрично-графовом подходе к исследованию перемешивающих свойств итеративных блочных шифров и генераторов гаммы. Оценка экспонента произвольного множества орграфов является сложной задачей. В [3,4] получены условия примитивности и оценки экспонентов некоторых частных классов множеств перемешивающих орграфов регистровых преобразований. Особенностью таких орграфов является наличие гамильтонова контура. В данной работе представлено обобщение результатов [3, 4], в частности получены критерий примитивности и универсальная оценка экспонента для множества орграфов с общим гамильтоновым контуром, а также критерий примитивности и оценка экспонента множества орграфов с общим множеством контуров. 1. Критерий примитивности множества орграфов с общим гамильтоновым контуром Введем обозначения: (X) -подполугруппа, порождённая подмножеством X мультипликативной полугруппы; если L = {l1,... , lm} С N, то НОД(Ь) = (l1,... , lm) = d - наибольший общий делитель чисел l1,... , lm; при d =1: $(L) = Ф(11,..., lm) -число Фробениуса, т. е. наибольшее целое число, не принадлежащее аддитивной полугруппе (L); при d > 1: L/d = {h/d,... , lm/d}, F(L) = dФ(L/d) (F(L) = Ф(Ь) при d = 1). Контур C называется общим контуром множества Г, если каждый орграф этого множества имеет контур C. Установлен критерий примитивности множества Г с общим гамильтоновым контуром. Теорема 1. Пусть Г = {Г1,..., Гр} - множество орграфов с общим гамильтоновым контуром, p > 1. Множество Г примитивное, если и только если НОД длин всех простых контуров орграфа U(p) равен 1. Для экспонента примитивного множества орграфов Г верна оценка exp Г ^ (2n - 1)p + Е (F(Lt) + dT - ). (1) т =1 2. Критерий примитивности множества орграфов с общим множеством контуров При исследовании примитивности множества орграфов с общим множеством контуров обратимся к понятию признака наличия петель в орграфе в вершинах из заданного множества [5]. Подмножество H полугруппы G, состоящее из всех элементов G, обладающих определённым свойством, называется признаком H (H-признаком) в полугруппе G [1, с. 178]. В мультипликативной полугруппе всех n-вершинных орграфов признаком (обозначается Pi00p) является, в частности, множество всех орграфов, имеющих петли в каждой вершине множества P, 0 = P С V. Показателем P^^-признака в циклической полугруппе (Г) называется наименьшее натуральное h, при котором Г" Е Pi00p. Оценки и точное значение показателя Pi00p-признака получены в [5]. В орграфе Г обозначим C* -множество вершин контура C; C7 = {C1,... , Cm} - множество простых контуров, m > 1; Г((7) = C1 U ... U Cm - часть орграфа Г. Теорема 2. Пусть Г = {Г1,..., Гр} - множество орграфов с общим множеством контуров C = {C1,... , Cm}, p, m > 1, C*U.. .UCm = V. Множество Г примитивное, если и только если орграф U(p) примитивный. Для экспонента примитивного множества орграфов Г верна оценка exp Г ^ ((p - 1)h +1) exp U(p), (2) где h - показатель V100p-признака в полугруппе (Г(С)). Пример 1. На рис.1 представлено множество орграфов Г = {Гх, Г2} с общим множеством контуров при n = 6. В таблице приведены оценки exp Г. На рис. 1, а Г(С) сильносвязный, на рис. 1, б Г(С) не является сильносвязным, в обоих случаях орграфы Гх и Г2 непримитивные. Множество Г примитивное по теоремам 1 и 2. а б Рис. 1. Множество Г = {Гх, Г2} и соответствующий орграф U(2) Г Общее множество простых контуров C h exp U(2) exp Г Оценка (1) Оценка (2) Рис. 1, а {(0,1,..., 5)} 6 9 11 17 63 Рис. 1, б {(0,1, 2, 3), (0, 3), (1, 2), (4, 5)} 2 6 8 - 18 Выводы Критерий примитивности множества орграфов с общим гамильтоновым контуром (теорема 1) уточняет критерий примитивности множества орграфов с общим множеством контуров (теорема 2). Если общее множество контуров орграфов содержит га-мильтонов контур, оценка (1) существенно улучшает оценку (2). Как видно из примера, оценка (2) для экспонента множества орграфов на рис. 1, а имеет значение exp Г ^ 63, что существенно больше, чем по оценке (1). Перспективным направлением дальнейшей работы является исследование условий примитивности и оценка экспонента множества орграфов с общим множеством контуров в случае, когда C U ... U C^ С V.

Ключевые слова

exponent of digraphs set, exponent of digraph, loop-character index, primitivity of digraphs set, Hamiltonian cycle, экспонент множества орграфов, примитивность множества орграфов, экспонент орграфа, показатель признака, гамильтонов контур

Авторы

ФИООрганизацияДополнительноE-mail
Авезова Яна ЭдуардовнаНациональный исследовательский ядерный университет МИФИаспиранткаavezovayana@gmail.com
Всего: 1

Ссылки

Авезова Я. Э., Фомичев В. М. Об одном наследственном признаке в циклических полугруппах графов // Прикладная дискретная математика. Приложение. 2016. №9. С. 105-109.
Авезова Я. Э. О примитивности некоторых множеств перемешивающих орграфов регистровых преобразований // Прикладная дискретная математика. Приложение. 2017. № 10. С. 60-62.
Авезова Я. Э., Фомичев В. М. Условия примитивности и оценки экспонентов множеств ориентированных графов // Прикладная дискретная математика. 2017. №135. С. 89-101.
Фомичев В. М., Мельников Д. А. Криптографические методы защиты информации. В 2 ч. Ч. 1. Математические аспекты. М.: Юрайт, 2016. 209 с.
Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.
 Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/31

Критерий примитивности и оценки экспонентов множества орграфов с общим множеством контуров | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/31