About one heritage character in cyclic semigroups of graphs.pdf Введение Важной задачей в криптографических приложениях является определение экспонента системы орграфов Г = {Г1,..., Гт}, обозначаемого exp Г (равносильное определение экспонента системы матриц дано в [1, с. 202]). Один из способов получения оценки exp Г основан на построении примитивного орграфа Г', являющегося словом в алфавите Г, то есть элементом полугруппы (Г), и оценке exp Г', где, согласно универсальному критерию примитивности [2], орграф Г' примитивный, если и только если он сильносвязный и имеет простые контуры взаимно простых длин. Примитивный орграф Г' может быть получен как произведение непримитивных орграфов, составляющих некоторую систему. Одно из условий примитивности орграфа Г' связано, в частности, с наличием петель в определённом подмножестве вершин орграфа Г при некотором j G {1,... ,m} и некотором натуральном t. В частности, пример такой системы Г из двух графов рассмотрен в [3]. Настоящая работа посвящена исследованию свойства орграфа, связанного с наличием петель в определённом подмножестве вершин. 1. Полугрупповой признак наличия петель в заданном подмножестве вершин орграфов Подмножество H полугруппы G, состоящее из всех элементов G, обладающих определённым свойством, называется признаком H (H-признаком) в полугруппе G. Если H ^ G - подполугруппа, то H называется полугрупповым признаком в G [1, с. 178]. Пусть G - полугруппа орграфов с множеством вершин V = {1,... ,n}, 0 = P С V. В полугруппе G полугрупповым признаком (обозначим его Pi00p) является, в частности, множество всех орграфов, имеющих петли в каждой вершине множества P. Пусть Г G G. Обозначим (Г) циклическую полугруппу, порождённую орграфом Г. Показателем Pi^-признака в полугруппе (Г) называется наименьшее натуральное t, при котором Г* G Pi00p (обозначается pok Pi00p или кратко lP). Заметим, что lV = ord g, если Г - граф подстановки g множества V. Утверждение 1. Признак Pi00p в полугруппе (Г) не пуст, если и только если каждая вершина из P является циклической. 2. Оценки показателя признака наличия петель в заданном подмножестве вершин орграфов Рассмотрим орграф Г, все вершины которого из множества P являются циклическими. Обозначим в Г: C = {C1,... , Ck} -множество k простых контуров; l(C) - длина контура C; V(C) -множество вершин контура C; L(i) -множество длин контуров, проходящих через вершину i; L[m](i) -множество не превосходящих натурального числа m длин контуров, проходящих через вершину i; Л^) -множество длин простых контуров, проходящих через вершину i; Cmini - кратчайший простой контур, проходящий через вершину i, i G V. Утверждение 2. Показатель признака Pi00p равен Ip = min P| L(i). (1) ieP Поскольку через каждую вершину i G P проходит бесконечно много контуров, применение (1) для вычисления точного значения показателя признака Pi00p затруднительно. Для уточнения формулы получим ряд оценок 1р. Запишем, что система контуров C = {C1,...,Ck} содержит множество P, если P С V(Ci) U ... U V(Ck). Систему контуров C = {C1,... , Ck} назовём связной, если связной является часть графа Г, совпадающая с C1 U ... U Ck. Связную систему контуров, содержащую множество P, назовём P-сокращённой, если после удаления любого контура оставшаяся подсистема либо не является связной, либо не содержит множество P. P-сокращённую систему С = {(!,...,(} назовём минимальной в Г, если сумма длин её контуров принимает наименьшее значение. Заметим, что P-сокращённых и минимальных систем в орграфе Г может быть несколько. Далее полагаем P = {1,... ,p}. Лемма 1. Пусть орграф Г содержит связную систему контуров С = {C1,... , Ck}, k ^ 1. Тогда в Г имеется контур длины /((С) = /(С1) + ... + /(Ck), обходящий однократно каждый контур системы С. Теорема 1. Если в орграфе Г связная система контуров С = {C1,... , Ck} содержит множество P, то верны оценки max{/(Cmini): i G P} ^ /P ^ /(С) (2) Верхняя оценка (2) принимает наименьшее значение, если система С P-сокращён-ная и минимальная. Теорема 2. Для любого разбиения множества P = P1 U ... U Pr выполнено /р ^ НОК(/р,...,/рг). (3) Следствие 1 (для минимального разбиения множества P). Верна оценка /p ^ min{HOK{(Ab..., Ap) G Л(1) х ... х Л(р)}}. (4) Оценка (4) позволяет уточнить (1), заменив бесконечные множества конечными. Следствие 2. При m = НОК{(А1,..., Ap) G Л(1) х ... х Л(р)} выполнено /р = min П L[m](i). (5) ieP Уточним равенство (5) с использованием верхней оценки (2). Следствие 3. Если в Г связная система контуров (7 содержит множество P, то формула (5) верна при m = min{/(C7), min{HOK{(A1,..., Ap) G Л(1) х ... х Л(р)}}}. Следствие 4. Пусть орграф Г содержит компоненты сильной связности Г1,... , Гг с множествами вершин V1,... , V соответственно и P^ = P П Vi, i = 1,...,r. Тогда верна оценка (3). Проиллюстрируем примером полученные результаты для показателя Pio0p. Пример 1. Граф Г (рис. 1) состоит из компонент сильной связности Г1 и Г2. Компонента сильной связности Г1 представляет собой связную систему простых контуров С1 = (1, 2, 3), С2 = (3, 4) и С3 = (4, 5, 6, 7, 8) длин 3, 2 и 5 соответственно. Компонента сильной связности Г2 есть связная система простых контуров С4 = (9,10), С5 = (10,11) и С6 = (10,11,12) длин 2, 2 и 3 соответственно. Для орграфа Г при некоторых P посчитаны оценки показателя /р с помощью оценок (2) и (4) (табл. 1 и 2), а также точное значение показателя /р (табл. 3) с помощью (5) или следствия 3. Рис. 1. Орграф Г Таблица 1 Верхняя оценка (2) показателя lp для различных P P Минимальная связная система, содержащая P Оценка (2) {1, 5} {Cb C2, C3 } lP < 3 + 2 + 5 = 10 {1, 4} {Ci,C2} lP < 3 + 2 = 5 {9,11} {C4, C5} lP < 2 + 2 = 4 Таблица 2 Верхняя оценка (4) показателя 1р для различных P P Л(г), i € P Оценка (4) {1, 5} Л(1) = {3}, Л(5) = {5} lP < НОК(3, 5) = 15 {1, 4} Л(1) = {3}, Л(4) = {2, 5} lP < тт{НОК(3, 2), НОК(3, 5)} = 6 {9,11} Л(9) = {2}, Л(11) = {2, 3} lP < тт{НОК(2, 2), НОК(2, 3)} = 2 {1,4, 9,11} Л(1) = {3}, Л(4) = {2, 5}, Л(9) = {2}, Л(11) = {2, 3} lP < тт{НОК(3, 2, 2, 2), НОК(3, 5, 2, 2)}, НОК(3, 2, 2, 3), НОК(3, 5, 2, 3)} = 6 Таблица 3 Показатель 1р для различных P, посчитанный с помощью (5) P m L[m] (i), i € P IP (5) {1, 5} 10 L[10](1) = {3, 5, 6, 7, 8, 9,10}, L[10] (5) = {5, 7, 9,10} Ip = min L[10] (1) n L[10](5) = 5 {1,4} 5 L[5](1) = {3, 5}, L[5](4) = {2,4, 5} lP = minL[5](1) П L[5](4) = 5 {9,11} 2 L[2] (9) = L[2](11) = {2} lP = 2 {1, 4, 9,11} 6 L[6](1) = {3, 5, 6}, L[6] (4) = {2, 4, 5, 6}, i[6] (9) = {2, 4, 5, 6}, L[6] (11) = {2, 3,4, 5, 6} lP = min{5, 6} = 5 Из табл. 1 следует, что для P = {1,5} и {1,4} оценка (2) точнее оценки (4), а для P = {9,11} соотношение обратное. Для P = {1, 4,9,11} с помощью следствия 3 получаем оценку lp ^ НОК(2, 5) = 10; величина оценки (4) более точная (см. табл. 2), но превышает точное значение, посчитанное в табл. 3. Результаты показывают, что в некоторых случаях оценки (2) и (4) достижимы. Для многих орграфов с большим числом вершин сложность вычисления оценок показателя lp по предварительным оценкам меньше, чем сложность определения точного значения. Однако для вычисления по формуле (5) точного значения lp необходимо вычислить параметр m, являющийся верхней оценкой lp, и затем построить пересечение множеств Ь^(1),..., L[m](p). Перспективное направление дальнейших исследований связано с алгоритмическими вопросами вычисления показателя Pioop-признака в полугруппе (Г). Выводы Доказанные оценки показателя Pioop-признака могут быть использованы для оценки экспонентов некоторых примитивных систем орграфов. Полученные условия существенно расширяют область систем орграфов, для которой удаётся получить оценки экспонентов.

Скачать электронную версию публикации