Структурные свойства минимальных примитивных орграфов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/7

Структурные свойства минимальных примитивных орграфов

Описаны классы n-вершинных минимальных примитивных орграфов с числом дуг (n + 3), приведены их степенные структуры. Установлена зависимость структурных свойств n-вершинных минимальных примитивных орграфов от числа дуг. В частности, получена оценка количества классов таких графов с (n + k) дугами.

Structural properties of minimal primitive digraphs.pdf Введение Зачастую криптографические преобразования представляют собой систему булевых функций, заданную координатными функциями f (жl,..., xm),... , fn(x l,... , xm). Особенность такой системы в том, что её надёжность напрямую зависит от перемешивания входов. Чем больше существенных переменных у каждой координатной функции системы, тем она надёжнее. Наилучший эффект достигается тогда, когда каждая координатная функция существенно зависит от каждой переменной, в таком случае имеется так называемое полное перемешивание входов. Перемешивание входов можно охарактеризовать с помощью ориентированного графа, которому можно сопоставить неотрицательную матрицу, называемую матрицей смежности графа, поэтому для исследования связей между элементами удобно применять матрично-графовый подход [1]. Обзор известных результатов по этому направлению дан в [2]. Сложность реализации системы характеризуется, в частности, числом связей (дуг орграфа Г). Минимальные примитивные матрицы (МПМ) и орграфы (МПО) представляют интерес с точки зрения экономной реализации коммуникативной системы. Результаты исследования МПО содержатся в [3], где описаны структурные свойства n-вершинных МПО с (n +1) и (n + 2) дугами. В данной работе проведено исследование структурных свойств n-вершинных МПО с (n + 3) дугами, что является расширением известных результатов и логическим продолжением [3]. Основные обозначения, используемые в работе: - Гр(n,m) -множество минимальных примитивных орграфов с числом вершин n и числом дуг m; - K* - система контуров; - D(r) - степенная структура орграфа Г; - nr,s - количество вершин с полустепенью захода r и полустепенью исхода s; - pi - полустепень захода вершины i; - qi - полустепень исхода вершины i; - [i, j] -простой путь в орграфе Г из вершины i в вершину j. 1. Подход к описанию структурных свойств минимальных примитивных орграфов Заметим, что матрица и соответствующий ей граф одновременно либо примитивны, либо непримитивны, поэтому в работе используется язык теории графов. В [3] вводится понятие степенной структуры орграфа - таблицы положительных чисел nr,s при всех допустимых значениях r и s, описывающих количество заходящих и исходящих дуг вершины n. В [3] также впервые вводятся понятия примитивной (минимальной примитивной) системы контуров - такой, что натянутый на неё подграф примитивен, и K *-изолированной дуги - не принадлежащей ни одному из контуров системы K *. В [3] доказаны теоремы, являющиеся основными в области изучения структурных свойств МПО. Теорема 1 [3]. Если граф Г G Гр (n, m) при некоторых натуральных n и m, K* - примитивная (минимальная примитивная) система контуров в Г ив Г имеется K *-изолированная дуга, то при любом натуральном к имеется орграф Гк из Гр(п + к,m + к), являющийся к-расширением графа Г и содержащий систему K*. Если при этом орграф Г минимальный, то имеется к-расширение Гд, являющееся минимальным примитивным графом. Теорема 2 [3]. При n ^ 3 орграф Г e Гр(п, n + 1) тогда и только тогда, когда Г есть объединение простых контуров взаимно простых длин l и Л, общая часть которых есть путь длины q, где 1>Л; l + Л - q = n +1; 0 ^ q ^ n - 2; при q = 2 общая часть контуров есть вершина. Классы n-вершинных МПО с (n + k) дугами можно описать системой из двух уравнений, одно из которых перечисляет удвоенное число дуг в графе (в соответствии с теоремой Эйлера [4]), а другое - число вершин в данном графе: 2n1,1 + 3n1,2 + 3n2,1 + 4n1,3 + 4n2,2 + 4n31 + ... + nnn-1,1 = 2(n + k); (1) n1,1 + n1,2 + n2,1 + п1,З + n2,2 + пЗ,1 + nM + п2,З + пЗ,2 + n4,1 + ... + п„-1Д = n. (2) Систему, состоящую из уравнений (1) и (2), обозначим (*). Решив её, можно описать все классы минимальных примитивных орграфов, принадлежащие Гр(n, n + k). Заметим, что уравнения системы (*) относятся к классу диофантовых уравнений, описанных в [5], однако интерес представляют только неотрицательные решения, поскольку они являются количественными характеристиками графа. Вычитая из уравнения (1) удвоенное уравнение (2), получим n1,1 + n2,1 + 2n1,3 + 2n2,2 + 2Пз,1 + 3n1,4 + 3n2,3 + 3n3,2 + 3n4,1 +... + (n - 2)n„-1,1 = 2k. (3) При k =1 уравнение (3) имеет вид n1,2 + n2,1 + 2n1,3 + 2n2,2 + 2n3,1 = 2. (4) Уравнение (4) описывает случай, когда число дуг превосходит число вершин орграфа на единицу и имеет два решения в целых неотрицательных числах, соответственно имеется два класса Гр (n, n +1). 1 класс: n1,2 = n2,1 = n1,3 = n3,1 = 0, n2,2 = 1. Пример графа приведен на рис. 1. Рис. 1. Граф Г, n = 3, D(r) = {(1,1)2, (2, 2)1} В соответствии с теоремой 1 степенная структура графов первого класса имеет следующий вид: D(rfc) = {(1,1)k+2, (2, 2)1}. 2 класс: n1,2 = n2,1 = 1, n1,3 = n3,1 = 0. Пример графа представлен на рис. 2. Степенная структура графов второго класса имеет вид D(rk) = {(1,1)k+2, (1, 2)1, (2,1)1}. Применяя данный подход к исследованию структурных свойств МПО, приведём ещё одну формулировку теоремы 2. Теорема 3. Если минимальный примитивный орграф Г e Гр(n, n + 1), то D(r) принадлежит классам, описанным в табл. 1. Рис. 2. Граф Г, n = 4, D(r) = {(1,1)2, (1, 2)1, (2,1)1} Таблица 1 Классы минимальных примитивных орграфов Г е rp(n,n + 1) № п/п n D(r) 1 > 3 {(1,1)n-1, (2, 2)1} 2 > 4 {(1,1)n-2, (1, 2)1, (2,1)1} Данный подход впервые предложен в [3] и отражён в теореме 4. Теорема 4. Если минимальный примитивный орграф Г е Гр(n, n + 2), то D(r) принадлежит классам, описанным в табл. 2. Та б л и ц а 2 Классы минимальных примитивных орграфов Г е Гр(п, n + 2) № п/п n D(r) 1 > 5 {(1,1)n-1, (3, 3)1} 2 > 5 {(1,1)n-2, (2,1)1, (2, 3)1} 3 > 5 {(1,1)n-2, (1, 2)1, (3, 2)1} 4 > 5 {(1,1)n-2, (2, 2)2} 5 > 4 {(1,1)n-3, (3,1)1, (1, 3)1} 6 > 6 {(1,1)n-3, (1, 3)1, (2,1)2} 7 > 6 {(1,1)n-3, (1, 2)2, (3,1)1} 8 > 6 {(1,1)n-3, (2,1)1, (1, 2)1, (2, 2)1} 9 > 6 {(1,1)n-4, (2,1)2, (1, 2)2} Заметим, что с ростом разницы числа дуг и вершин количество решений значительно увеличивается, соответственно сложность описания классов МПО возрастает. Так как в любом графе сумма всех полустепеней исхода равна сумме всех полустепеней захода, можно сказать, что числа nr,s связаны следующим равенством: Е kri,Si ri = Е kri,Si si, (5) где kri,Si -коэффициент при nri,Si, kri,Si = ri + si - 2. 2. Структурные свойства n-вершинных МПО с (n + 3) дугами Теорема 5. Если минимальный примитивный орграф Г е Гр(n, n + 3), то D(r) принадлежит классам, приведённым в табл. 3. Таблица 3 Классы минимальных примитивных орграфов Г е Гр(п, n + 3) № п/п n D(r) 1 > 6 {(1,1)n-1, (4, 4)1} 2 > 6 {(1,1)n-2, (2,1)1, (3,4)1} 3 > 6 {(1,1)n-2, (1, 2)1, (4, 3)1} 4 > 6 {(1,1)n-2, (2, 2)1, (3, 3)1} 5 > 7 {(1,1)n-3, (2,1)1, (1, 2)1, (3, 3)1} 6 > 5 {(1,1)n-2, (1, 3)1, (4, 2)1} 7 > 7 {(1,1)n-3, (1, 2)2, (4, 2)1} 8 > 6 {(1,1)n-2, (3,1)1, (2,4)1} 9 > 7 {(1,1)n-3, (2,1)2, (2,4)1} 10 > 6 {(1,1)n-3, (2, 2)1, (1, 2)1, (3, 2)1} 11 > 8 {(1,1)n-4, (2,1)1, (1, 2)2, (3, 2)1} 12 > 6 {(1,1)n-2, (2, 3)1, (3, 2)1} 13 > 7 {(1,1)n-3, (1, 3)1, (2,1)1, (3, 2)1} 14 > 6 {(1,1)n-3, (2, 2)1, (2,1)1, (2, 3)1} 15 > 8 {(1,1)n-4, (1, 2)1, (2,1)2, (2, 3)1} 16 > 7 {(1,1)n-3, (3,1)1, (1, 2)1, (2, 3)1} 17 > 7 {(1,1)n-4, (2,1)3, (1,4)1} 18 > 7 {(1,1)n-3, (2,1)1, (3,1)1, (1,4)1} 19 > 7 {(1,1)n-4, (1, 2)3, (4,1)1} 20 > 7 {(1,1)n-3, (1, 2)1, (1, 3)1, (4,1)1} 21 > 6 {(1,1)n-3, (2, 2)3} 22 > 7 {(1,1)n-4, (2, 2)2, (1, 2)1, (2,1)1} 23 > 5 {(1,1)n-4, (2, 2)2, (1, 3)1, (3,1)1} 24 > 7 {(1,1)n-5, (2, 2)1, (1, 2)2, (2,1)2} 25 > 7 {(1,1)n-4, (2, 2)1, (1, 3)1, (2,1)2} 26 > 7 {(1,1)n-4, (2, 2)1, (3,1)2, (1, 2)2} 27 > 7 {(1,1)n-5, (3,1)1, (2,1)1, (1, 2)3} 28 > 6 {(1,1)n-4, (1, 3)1, (3,1)1, (2,1)1, (1, 2)1} 29 > 8 {(1,1)n-5, (1, 3)1, (1, 2)1, (2,1)3} 30 > 9 {(1,1)n-6, (1, 2)3, (2,1)3} Доказательство. Если сильносвязный орграф Г е Гр (n, n + 3), то числа nr,s связаны системой (*) при k = 3. Составим уравнение, описывающее данные классы МПО, аналогично уравнению (4): П1,2 + П2,1 + 2ni,3 + 2n2,2 + 2пз,1 + 3ni,4 + 3n2,3 + 3Пз,2 + 3П4,1 + ... + (n - 2)пп-1,1 = 6. (6) Определим решения уравнения (6) относительно целых неотрицательных чисел nr,s и укажем примитивные графы без петель, соответствующие полученным решениям. Заметим, что nr,s = 0 при r + s > 8, следовательно, уравнение (6) равносильно следующему упрощённому уравнению: n1,2 + n2,1 + 2n1,3 + 2n2,2 + 2Пз,1 + 3n1,4 + 3n2,3 + 3n3,2 + 3n4,1 + 4n1,5 + 4n2,4 + +4n3,3 + 4n4,2 + 4n5,1 + 5n1,6 + 5n2,5 + 5n3,4 + 5n4,3 + 5n5,2 + 5n6,1 + 6n1,7+ (7) +6n2,6 + 6n3,5 + 6n4,4 + 6n5,3 + 6n6,2 + 6n7,1 = 6. Пусть nr,s = 1, а все остальные переменные равны нулю, тогда в Г имеется вершина i, гдеp = r, qj = s, то есть имеются дуги (i, a), (i, b),..., (i, r), где i, a, b,..., r различны. Орграф Г - сильносвязный, значит, в Г имеются простые пути [a, i], [b, i],... , [r, i]. Так как pi = s, эти пути сходятся в s путей, при этом в Г имеется вершина j = i, где pj = s. Тогда при некоторых r и s имеем противоречие. Таким образом описываются классы МПО в [4]. Имеется 30 классов решения уравнения (7). 1-й класс. Положим n4,4 = 1. В этом случае Г есть объединение четырёх контуров, пересечение множеств вершин которых состоит из единственной вершины, а любая другая вершина принадлежит только одному из контуров. Пример графа приведён на рис. 3. Рис. 3. Граф Г, n = 6, D(r) = {(1,1)5, (4, 4^} Степенная структура данного класса МПО имеет вид D(rk) = {(1,1)k+5, (4, 4^}. Если n3,5 = 1, то все остальные переменные в уравнении (7) равны нулю, следовательно, необходима ещё хотя бы одна вершина, чтобы уравнять количество входящих и исходящих дуг в графе. Отсюда следует, что если ni,j = 1, i + j = 8, i = j, то уравнение (7) не имеет решений. Рассмотрим упрощённое уравнение nl,2 + n2,l + 2nl,3 + 2n2,2 + 2n3,l + 3nM + 3n2,3 + 3n3,2 + 3n4,l + 4nl,5 + 4n2,4 + (8) +4n3,3 + 4n4,2 + 4n5,l + 5nl,6 + 5n2,5 + 5пз,4 + 5П4,з + 5n5,2 + 5n6,l = 6, оно имеет ещё 29 решений. Путём аналогичных рассуждений получаем оставшиеся 29 классов. ■ 3. Зависимость структурных свойств n-вершинных МПО от числа дуг Определение 1. Назовём вершину, у которой полустепень исхода совпадает с полустепенью захода и равна 1, моновершиной. Утверждение 1. Если существует решение уравнения (5) вида ni1,i2 = al, ..., nim,im+l = am, то ni2,i1 = al,..., nim+Mm = am также является решением уравнения (5). Следствие 1. Графы, соответствующие таким решениям, изоморфны. Утверждение 2. Класс МПО Гр(n+p, n+p+k) образуется добавлением p вершин и (p +1) дуг в соответствующие множества класса Гр(n, n + k - 1). Доказательство. Количество вершин в полученном графе составит (n + p), а количество дуг - (n + k - 1 + p + 1) = n + k + p, отсюда следует, что количество дуг превышает количество вершин на k. ■ Рис. 4. Граф Г1 е Гр(5, 7), D(ri) = {(1,1)4, (3, 3)1} Рис. 5. Граф Г2 е Гр(6, 9), D(r) = {(1,1)5, (4, 4)1} Как видно из рис. 4 и 5, графы Г1 и Г2 принадлежат множествам МПО, у которых разница между количеством дуг и вершин равна двум и трём соответственно, однако граф Г2 имеет на одну вершину больше. Заметим, что изменение степенной структуры говорит об увеличении количества вершин на 1 и количества дуг на 2. Далее под типом вершины понимается характеристика вершины, описывающая количество заходящих и исходящих дуг данной вершины. Важно отметить, что в степенной структуре орграфа описываются все его типы вершин. Пример 2. Рассмотрим степенную структуру орграфа Г, принадлежащего 28-му классу Гр(n, n + 3), D(r) = {(1,1)3, (1, 3)1, (3,1)1, (2,1)1, (1, 2)1}. Граф Г имеет пять типов вершин: (1,1), (1, 3), (3,1), (2,1), (1, 2). Утверждение 3. Степенные структуры графов из множества Гр (n, n + k) с точностью до количества моновершин определяются степенными структурами графов из множества Гр (n - 1, n + k - 2). Доказательство. Пусть a и b - вершины графа Г1 е Гр(п - 1,n + k - 2), при этом допустимо a = b. Так как добавляются две новые дуги (обозначим их A и B) и одна новая вершина (обозначим её d), то одна дуга является исходящей из этой вершины, а другая заходящей в неё, значит, (pd,qd) = (1,1). Пусть дуга A исходит из а и заходит в d, а дуга B исходит из d и заходит в b, следовательно, степенная структура графа изменится и будет известна с точностью до количества моновершин в силу теоремы 1. ■ Пример 1. На рис.4 изображён граф Г1 е Гр(5,7) со степенной структурой D(ri) = {(1,1)4, (3, 3)1}. Добавим одну вершину и две дуги в соответствующие множества графа Г1 так, чтобы получить граф Г2, изображённый на рис. 5. Утверждение 4. Степенная структура графа Г Е Гр(п, n + k) может быть получена из различных степенных структур графов множества Гр(n - 1, n + k - 2). Пример 3. Рассмотрим МПО Г1, Г2 Е Гр(n,n + 2), которые представлены на рис. 6, и их степенные структуры для n = 5: D(r1) = {(1,1)3, (2,1)1, (2, 3)1}, D(r2) = = {(1,1)3, (1, 2)1, (3, 2)1}. Рис. 6. Г1, Г2 Е Гр(5, 7) Добавив к графу Г1 одну вершину и две дуги, можно получить граф Г3, такой, что D(r3) = {(1,1)3, (3,1)1, (2, 3)1}. Также, определённым образом добавив к графу Г2 одну вершину и две дуги, можно получить граф Г4, такой, что D(r4) = = {(1,1)3, (2, 3)1, (3, 2)1}. Заметим, что степенные структуры графов Г3 и Г4, которые представлены на рис. 7, совпадают. Рис. 7. Г3, Г4 Е Гр(6, 9), D(r3) = ДГ4) = {(1,1)3, (2, 3)1, (3, 2)1} Отметим, что графы Г3 и Г4 изоморфны и являются частными случаями графов 12-го класса n-вершинных МПО с количеством дуг (n + 3) для n = 6. Утверждение 5. Количество классов Гр(n, n + k) можно оценить с помощью степенных структур классов Гр(n - 1, n + k - 2) и количества решений уравнения n1,2 + n2,1 + 2n1,3 + 2n3,1 + 3n1,4 + 3n4,1 + 4n1,5 + 4n5,1 + ... + kn!,fc+1 + knfc+1,1 = 2k. (9) Доказательство. Пусть Sfc-1,i - число типов вершин i-го класса из Гр (n - 1, n + k - 2), тогда £ Sfc-1,i является оценкой сверху количества новых классов, не со-i держащих вершин, имеющих либо одну заходящую дугу, либо одну исходящую, за исключением моновершин. С другой стороны, графы Г Е Гр(n, n + k) такого вида описываются уравнением (9). Пусть - количество решений уравнения (9), Nk - количество классов Гр (n, n + k). Зная степенные структуры классов Гр (n, n + k - 1), по утверждению 3 можно получить степенные структуры всех классов Гр(n, n + k), при этом процесс подсчёта новых классов усложняется согласно утверждению 4. Отсюда следует, что Nfc ^ £ sfc_ 1 ,i + tfc. ■ i Пример 4. Рассмотрим классы Гр(n, n + 2). Согласно теореме 4, имеется 9 классов с различными степенными структурами и 26 типов вершин различных классов, описанных в табл. 2. Имеется 8 классов n-вершинных МПО с (n + 3) дугами, приведённых в табл. 3 и удовлетворяющих уравнению n 1,2 + n2, 1 + 2n 1 ,3 + 2пз, 1 + 3n 1 ,4 + 3n4, 1 = n. (10) Данные классы описаны в табл. 4. Таблица 4 Классы минимальных примитивных орграфов Г Е Гр(п,п + 3), удовлетворяющих уравнению (10) № п/п n D(r) 1 > 7 {(1,1)n-4, (2,1)3, (1,4)1} 2 > 7 {(1,1)n-3, (2,1)1, (3,1)1, (1,4)1} 3 > 7 {(1,1)n-4, (1, 2)3, (4,1)1} 4 > 7 {(1,1)n-3, (1, 2)1, (1, 3)1, (4,1)1} 5 > 8 {(1,1)n-5, (3,1)1, (2,1)1, (1, 2)3} 6 > 7 {(1,1)n-4, (1, 3)1, (3,1)1, (2,1)1, (1, 2)1} 7 > 8 {(1,1)n-5, (1, 3)1, (1, 2)1, (2,1)3} 8 > 9 {(1,1)n-6, (1, 2)3, (2,1)3} Оценим количество классов Гр(n, n + 3), зная степенные структуры классов Гр (n, n+2): по утверждению 5 верно N3 ^ 26+8 = 34; и количество классов Гр (n, n+2), зная степенные структуры классов Гр(n, n+1): по утверждению 5 верно N2 ^ 5+4 = 9. Заметим, что в данном случае полученная оценка полностью совпадает с количеством классов Гр (n, n + 2).

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

примитивная матрица, примитивный орграф, сильносвязный орграф, primitive matrix, primitive digraph, strongly connected digraph

Авторы

ФИООрганизацияДополнительноE-mail
Лебедев Филипп ВладимировичООО «АСП Лабс»специалист по информационной безопасности компанииplebedev@asplabs.ru
Всего: 1

Ссылки

Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.
Когос К. Г., Фомичев В. М. Положительные свойства неотрицательных матриц // Прикладная дискретная математика. 2012. №4 (18). С. 116-121.
Фомичев В. М. Свойства минимальных примитивных орграфов // Прикладная дискретная математика. 2015. №2 (28). С. 86-96.
Харари Ф. Теория графов. М.: Едиториал УРСС, 2003. 296с.
Бухштаб А. А. Теория чисел. СПб.: Лань, 2008. 384 с.
 Структурные свойства минимальных примитивных орграфов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/7

Структурные свойства минимальных примитивных орграфов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/7