О примитивных наборах натуральных чисел | ПДМ. 2012. № 2(16).

О примитивных наборах натуральных чисел

Описано строение множества примитивных наборов натуральных чисел и установлены их основные свойства. С использованием понятий тупиковости и k-минимальности построен алгоритм перечисления примитивных наборов чисел, не ревышающих заданного числа m. Предложены алгоритмы определения показателя примитивности ориентированного конечного графа с помощью поиска в глубину на графе и возведения в степень матрицы смежности вершин и оценена их вычислительная сложность.

About primitive systems of natural numbers.pdf ВведениеМатрица M называется положительной (неотрицательной), если положительны(неотрицательны) все её элементы; этот факт обозначается M > 0 (M ^ 0). Неотрица-тельная квадратная матрица называется примитивной, если M4 > 0 при некоторомнатуральном t, а наименьшее натуральное Y, при котором M7 > 0, называется экс-понентом (показателем примитивности) матрицы M и обозначается exp M. Еслитакого t не существует, то exp M = то. Если для неотрицательной матрицы M выпол-нено соотношение M + M2 + . . . + M4 > 0, то наименьшее такое t называется субэкс-понентом матрицы M.Сильносвязный орграф Г называется примитивным, если при некотором натураль-ном m для любой пары вершин (i, j) в Г существует путь из i в j длины т. Наимень-шее такое m называется экспонентом графа Г. Под субэкспонентом орграфа Г пони-мается субэкспонент матрицы смежности его вершин. Субэкспонент сильносвязногоn-вершинного графа не превышает n (он равен диаметру графа).Одной из важных задач при изучении перемешивающих свойств преобразованийявляется определение экспонентов перемешивающих матриц и соответственно пере-мешивающих графов [1, 2]. При исследовании экспонентов матриц и графов частоиспользуется эпиморфизм мультипликативного моноида неотрицательных матриц по-рядка n на моноид n-вершинных орграфов, где умножение орграфов определено какумножение бинарных отношений [3]. Матрица положительна, если и только если соот-ветствующий граф полный. Отсюда следует, что орграф и его матрица смежности Mодновременно примитивны или не примитивны, в случае примитивности экспонентыих равны.Критерий примитивности орграфа определяется длинами его простых контуров [2](контур простой, если проходит через любую вершину не более одного раза). ЕслиC 1 , . . . , Ck суть все простые контуры орграфа длин l\,... , lk соответственно, то орграфпримитивный, если и только если числа li, . . . , lk взаимно просты.Набор взаимно простых в совокупности натуральных чисел A = (ai,... ,ak), где1 < ai < ... < ak, называется примитивным. Заметим, что множество всех примитив-ных наборов натуральных чисел совпадает с областью определения функции Фробе-ниуса f (ai,... ,ak) [4].Распознавание примитивности орграфа может быть выполнено как определениедлин всех его простых контуров и распознавание примитивности набора всех различ-ных длин этих контуров. Другой подход заключается в определении показателя при-митивности графа с помощью возведения в степень матрицы смежности его вершин.Распознавание примитивности набора чисел ( a i , . . . , ak) можно выполнить, приме-нив k - 1 раз алгоритм Евклида к элементам набора. Можно также воспользоватьсязаранее составленными таблицами примитивных наборов.В п. 1 работы описана связь экспонента и субэскпонента матрицы и ее полугруп-повых характеристик, в п. 2 представлены основные свойства примитивных набо-ров натуральных чисел, в п. 3 сформулированы и доказаны критерии тупиковости иk-минимальности наборов, в п. 4 описан алгоритм перечисления k-минимальных тупи-ковых примитивных наборов, в п. 5 оценена вычислительная сложность определениядлин простых циклов графа с помощью поиска в глубину, а в п. 6 - вычислительнаясложность определения экспонента матрицы (и соответствующего графа) с помощьювозведения матрицы в степень.1. О связи экспонента и субэкспонента матрицы с её полугрупповымихарактеристикамиОбозначим через A = (aj) матрицу смежности вершин орграфа Г и черезA = ( a j ) - степень матрицы A. Периодом вершины орграфа называется наибольшийобщий делитель (НОД) всех длин контуров, содержащих данную вершину. Заметим,что при подсчёте достаточно учитывать только простые контуры, так как любой кон-тур представляет собой соединение нескольких простых контуров и его длина кратнаНОД длин всех составляющих его простых контуров. Если орграф сильно связен (мат-рица A является неразложимой [2, гл. VI, § 2]), то все его вершины имеют одинаковыйпериод, называемый также к-периодом матрицы A (орграфа Г).Носителем неотрицательной матрицы B = (bij) называется 0,1-матрицаv(B) = (vbij), где {1, если bij > 0,0, если 7b ij = 0.Множество 0,1-матриц размера n х n образует полугруппу Gn относительно опера-ции *, где A * B = v(AB).У т в е р ж д е н и е 1 [2, гл. VI, теорема 2.2]. Пусть к-период сильносвязного оргра-фа Г равен q > 0. Тогда для любых вершин i,j существует единственное число r(i,j),0 ^ r(i,j) < q, такое, что1) если aj > 0, то t = r(i, j ) ( m o d q);2) существует число k(i, j) > 0, такое, что akjq+r > 0 для любого k ^ k(i, j).Следовательно, множество вершин V графа Г разбивается на q блоков:V = Co U . . . U Ca-i,при этом имеется единственная упорядоченная последовательность этих блоков сосвойством: если (i, j) -дуга графа Г и i G Cs , где s G { 0 , . . . , q - 1}, то j G C(s + 1 )modq.Отсюда Akq+r + Akq+r+l + . . . + Akq+r+q~l > 0 для любого k ^ max{k(i, j ) } .i,jУ т в е р ж д е н и е 2. Пусть неразложимая матрица A = ( a j ) с к-периодом q имееттип (d, т) в полугруппе Gn , где d - циклическая глубина и т - период матрицы A.Тогда1) т = q;2) если матрица A примитивная, то d = exp A и T = 1;3) если A не примитивная, то T > 1 и субэкспонент матрицы A не превышаетd + т - 1.Доказательство. Из определения типа матрицы следуетAd = Ad+T. (1)Если матрица A примитивная, то q = 1 в силу критерия примитивности сильно-связного орграфа. Пусть 7 = exp A, то есть A7 > 0, тогда в полугруппе Gn выполненыусловия A7 = A7 + 1 и A7 = A 7 - 1 . Следовательно, (1) выполняется при d = 7, т = 1. Суб-экспонент матрицы не превышает 7.Если A не примитивная, то q > 1. Из утверждения 1 следует, что в полугруп-пе Gn имеет место Akq+r = Ak q + r + q для любого k ^ max{k(i, j ) } и Akq+r = Ak q+r -qi,jпри k < max{k(i, j ) } . Следовательно, (1) выполняется при т = q и d ^ k(i, j ) q + r. Изi,jутверждения 1 также следует, что Akq+r + Ak q + r + 1 + . . . + A k q + r + q - 1 > 0 для любогоk ^ max{k(i, j ) } . Значит, субэкспонент матрицы A не превышает d + т - 1. i,j2. Определяющие свойства примитивных наборов натуральных чиселИсследуем свойства примитивных наборов.У т в е р ж д е н и е 3. Если A - примитивный набор чисел, то примитивен любой на-бор, полученный из A добавлением любого натурального числа или (при |A| > 1) уда-лением числа a, кратного одному из остальных чисел набора.С л е д с т в и е 1. Набор примитивен, если содержит пару взаимно простых чисел.Определение 1. Набор из Nk назовем приведённым, если в нём любое число некратно любому другому числу.Иначе говоря, приведённый набор (а1 , . . . , ak) является антицепью в решётке на-туральных делителей числа k^ = lcm(a1 , . . . , ak), обозначаемой D(k^), где lcm(a1,. . . , ak) -наименьшее общее кратное чисел a 1 , . . . , ak.Любому примитивному набору A размера k ^ 1 однозначно соответствует приве-дённый набор n(A) размера l, где 1 ^ l ^ k: если в наборе A число aj кратно a^, тонабор n(A) не содержит aj.Определение 2. Примитивный набор A размера k ^ 1 назовем тупиковым, ес-ли A = (1) или при k > 1 удаление из набора любого элемента нарушает его прими-тивность.Все примитивные наборы длины 2, не содержащие 1, являются тупиковыми, таккак при удалении одного из элементов набора остается число, отличное от 1. В со-ответствии с утверждением 3 примитивный тупиковыйнабор является приведённымнабором.Определение 3. Примитивный набор A размера k > 1 назовем r-примитивным,где 0 ^ r ^ k - 1, если после удаления из A любого подмножества порядка r прими-тивность получившегося набора сохраняется.Тупиковый набор 0-примитивен, но не 1-примитивен.Далее полагаем, что A = ( a i , . . . , ak) Е Nk - приведённый набор, элементы которо-го не превышают числа m. Пусть 2A - булеан множества { a i , . . . , ak}; P ( A , r) - множе-ство всех примитивных наборов (упорядоченных по возрастанию) размера (порядка)r, P ( A ) = U P(A, r). Заметим, что если A - примитивный приведённый набор, то всенаборы из P ( A ) также приведённые.На множестве P(A) определим отношение частичного порядка: (bi,...,bi) ^^ ( a i , . . . , ak), если и только если l ^ k и найдется бесповторная упорядоченная вы-борка ( i i , . . . ,il) из ( 1 , . . . , k), такая, что ii < . . . < il и bj делит aij, j = 1 , . . . , l.Определение 4. Тупиковый набор B Е P(A) назовем минимальным в P(A), ес-ли не существует другого набора B' Е P(A), такого, что B' ^ B.Для любого набора B из P(A) имеется хотя бы один минимальный тупиковыйнабор ©(B), такой, что ©(B) ^ B.Определение 5. Тупиковый набор B Е P(A) назовем r-минимальным в P(A),если не существует другого набора B' Е P(A) размера r, такого, что B' ^ B.У т в е р ж д е н и е 4. Если A - примитивный приведённый набор, то (P(A), -верхняя полурешётка, в которой максимальный элемент есть A и любой минималь-ный элемент - это тупиковый минимальный набор.Доказательство. Если наборы Ai , A2 Е P(A) имеют размеры соответственно lи r, то их верхняя грань sup{Ai , A 2 } определена как набор размера t упорядоченныхпо возрастанию элементов множества Ai U A2 , где max { l , r } ^ t ^ r + l. В соответ-ствии с утверждением 3, sup{Ai , A 2 } также есть примитивный набор из P ( A ) , то есть( P ( A ) , -верхняя полурешётка.Утверждения о максимальном и минимальных элементах полурешётки вытекаютиз определений множества P ( A ) и тупикового минимального набора. Для набора A рассмотрим наибольший общий делитель как функцию, определён-ную на 2A. При B = {ai1,..., a i ; } Е 2A обозначим gcd(B) = g c d ( a i 1 , . . . , ai ; ), если B = 0,и g c d ( 0 ) = l c m ( a i , . . . , ak), где g c d ( a i 1 , . . . , ai ; ) - наибольший общий делитель чисел ai 1,. . . , ail; D(A) = {gcd(B) : B Е 2A } . Множество D ( A ) частично упорядочено по отноше-нию делимости: gcd(B) ^ gcd(B') для B , B ' Е 2A, если и только если gcd(B) делитgcd(B').У т в е р ж д е н и е 5. Если A - примитивный тупиковый набор, то D ( A ) -решётка,антиизоморфная решетке 2A.Доказательство. Установим биективность функции gcd: 2A ^ D(A), для этогодостаточно убедиться в её инъективности.Предположим, что функция gcd не инъективна, то есть найдутся множестваBi , B 2 Е 2A, Bi = B2 , такие, что gcd(Bi ) = gcd(B2 ) = d. Заметим, что gcd(Bi U B2)делит d в соответствии с определением функции gcd. Вместе с тем d делит каждое изчисел множества Bi U B2 . Значит, gcd(Bi U B2 ) = d.Так как Bi = B2 , то одно из этих множеств не включено в другое, пусть для опреде-лённости B2 \ Bi = 0. Обозначим B3 = A \ (Bi U B2 ) . В соответствии с определениемфункции gcd имеем цепочку равенств1 = gcd(A) = gcd(B1 U B2 U B3) = gcd(gcd(B1 U B2), B3) == gcd(d, B3) = gcd(gcd(B1), B3) = gcd(B1 U B3).Следовательно, множество B1 U B3 примитивное, где B1 U B3 С A, так какB2 \ B1 = 0. Отсюда получаем противоречие с тупиковостью набора A.В соответствии с определением функции gcd если B С B', то gcd(B') делит gcd(B),значит, биекция 2A о D(A) антиизотонна. 3. Критерии тупиковости и k-минимальности наборов натуральных чиселОбозначим через Ai коатомы решётки 2A и через ^ - атомы решётки D(A): Ai == { a 1 , . . . , ak} \ { a i } , ^ = gcd(Ai), i = 1 , . . . , k.Т е о р е м а 1. Набор A примитивный тупиковый, если и только если ( ^ 1 , . . . , ^k) -набор попарно взаимно простых чисел, отличных от 1. При этомCi . . . ^kai = , (2)где ( c 1 , . . . , c k ) есть 1-примитивный набор натуральных чисел и gcd(ci,^i ) = 1 дляi = 1 , . . . , k.Доказательство. Пусть набор A примитивный тупиковый. Если = 1 принекотором i G { 1 , . . . , k}, то множество Ai примитивное, что противоречит тупиковостинабора A. Если gcd(^i,^j -) = d > 1 при i = j, то d делит все числа множеств Ai и Aj,значит, d делит все числа набора A, что противоречит его примитивности.Докажем достаточность. Если набор A не примитивный, то gcd(A) = d > 1. Отсюдаd делит при любом i = 1 , . . . , k, значит, числа ,... , ^k не являются попарно вза-имно простыми, то есть имеем противоречие. Если набор A не тупиковый, то = 1при некотором i G { 1 , . . . , k } , что противоречит условию.По определению чисел ... число ai делится на каждое из чисел множества{ ^ 1 , . . . , } \ {^i } , следовательно, для i = 1 , . . . , k верно (2), где ( c 1 , . . . , ck) G Nk.Заметим, что набор ( c 1 , . . . , ck) примитивный, так как иначе набор A не примитив-ный в силу (2). Если gcd(ci,^i ) = d > 1 при некотором i G { 1 , . . . , k } , то d делит всечисла набора A в соответствии с (2) и с определением чисел ... , что противо-речит примитивности набора A. Следовательно, gcd(ci , = 1 при любом i = 1 , . . . , k.Из (2) и определения чисел ..., следует также, что^i = gcd ({c1^2 . . . ^ k , . . . , c k . . . ^ k - 1 } \ { ( c i ^ 1 . . . ^ k ) / M ) .Значит, g c d ( { c 1 , . . . , c k } \ { c i } ) = 1 для i = 1 , . . . , k, и ( c 1 , . . . , ck) есть 1-примитивныйнабор. С л е д с т в и е 2. Пусть B = { a i x , . . . , a i l } G 2A и B = A \ B, тогдаg c d ( B ) = g c d ( { c i i , . . . , c i i } ) П_ ^ j .j €BДоказательство. Если c1 , . . . , ck, x 1 , . . . , x k G N, то gcd(c1x1 , . . . , c kxk ) де-лится на g c d ( { c 1 , . . . , ck } ) g c d ( x 1 , . . . , Xk). Отсюда, положив xi = . . . )/^i,i = 1 , . . . , k, в соответствии с (2) получаем, что gcd(B) делится на g c d ( { c i x , . . . , c i l } ) хx g c d ( { x i x , . . . , x i l } ) , где из теоремы 1 следует, что g c d ( { x i x , . . . , x i l } ) = П ^j.j €BБез ущерба для общности положим B = { a i , . . . , ai}, где 1 ^ l ^ k, и обозначимс' = g c d ( c i , . . . , q ) , x' = g c d ( x i , . . . ,xl ) . В этих условиях множества C' = { c i / c / , . . . , q / c ' }и X' = { x i / x / , . . . , x l / x ' } примитивные.Пусть gcd(B) = d d x' при натуральном d> 1, тогда gcd(B') = d, где B' == { a i / c / x ' , . . . , a l / c / x ' } . Следовательно, d делит c rxr / c ' x ' при r = 1 , . . . , l, отсюдаd = d(cr ) d ( x r ) , (3)где d(cr ) делит c r / с ' и d(xr ) делит x r / x ' . В силу примитивности множества C' найдетсяномер r Е { 1 , . . . , l } , такой, что d(xr ) > 1. Тогда, учитывая, что x i / x / = . . . )/^i,i = 1 , . . . , l, и числа ^ i , . . . , ^l попарно взаимно простые, найдется номер j Е { 1 , . . . , l } ,такой, что g c d ( d ( x r ) = drj- > 1, значит, drj- делит d. Из того, что g c d ( x j / x ' , ^ j ) = 1,следует gcd(xj/x',dr j - ) = 1, отсюда в силу (3) drj- делит d(cj), поэтому drj- делит c c j / с '.Вместе с тем в соответствии с теоремой 1 g c d ( c j ) = 1, тогда gcd(d(cj),dr j -) = 1.Имеем противоречие. Следовательно, d = 1. Представление целого числа n произведением степеней простых чисел n == е p?1 . . . p?8, где е = ± 1 , ki > 0 - кратность числа pi , называется каноническимразложением числа n, при этом множество чисел { p i , . . . , p s } называется факторнойбазой числа n и обозначается F(n).Определение 6. Факторной базой набора A = ( a i , . . . , ak) назовем множествочисел F ( A ) = F ( a i ) U . . . U F(ak).Докажем критерий k-минимальности тупикового примитивного набора.С л е д с т в и е 3. Примитивный тупиковый набор A является k-минимальным, еслии только если ..., - простые числа и ci = 1, i = 1 , . . . , k.Доказательство. Пусть A есть k-минимальный набор и каноническое разло-жение при некотором i Е { 1 , . . . , k} имеет вид = p?1 . . . p?8. Рассмотрим на-бор B, состоящий из чисел ..., ^ i - i , ^ i + i , . . . , , ^ i = p?1 . . . p ? 8 - 1 . Согласно (2),B ^ A, причём его размер равен k. Тогда A не является k-минимальным. Еслиd > 1 при некотором i Е { 1 , . . . , k}, то существует набор B', которому соответствуютс 1 , . . . , c i - 1 , Ci+i,... , с?, ci = 1. Согласно (2), B' ^ A, что противоречит k-минимально-сти A. Следовательно, ..., - простые числа и ci = 1, i = 1 , . . . , k.Если набор A не является k-минимальным, то существует набор A' = ( a i , . . . , a?),такой, что A' ^ A. Согласно (2), ai = ( с ^ . . . )/^i, i = 1 , . . . , k, причём ci де-лит ci или ^j- делит при некоторых i , j Е { 1 , . . . , k } . Тогда ci > 1 или составноесоответственно. С л е д с т в и е 4. Факторной базой k-минимального тупикового набора являетсямножество { ^ 1 , . . . , }.Примеры k-минимальных тупиковых примитивных наборов:1) 3-минимальные наборы A = (6,10,15), F ( A ) = {2, 3, 5}; B = (10,14, 35), F ( B ) == {2, 5, 7};2) 4-минимальный набор C = (30, 42, 70,105), F ( C ) = {2, 3, 5, 7}.4. Перечисление k-минимальных примитивных наборов натуральныхчиселПо утверждению 3 любой примитивный набор A можно получить из соответству-ющего тупикового набора A' добавлением любого числа. По следствию 3 любой ту-пиковый набор A' можно получить из соответствующего k-минимального набора Л"умножением элемента набора a на число, взаимно простое с i . { 1 , . . . , k}.Построим алгоритм перечисления множества всех k-минимальных примитивныхнаборов, состоящих из чисел, не превышающих m (обозначим его PRm ) .Пусть P(ж) -множество простых чисел, не больших ж. Известно [5], чтоп(ж) = |P(ж)| ~ ж/lnж. Набор размера 2 является 2-минимальным, если и только еслион представляет собой пару различных простых чисел. Число таких наборов равноn(m)(n(m) - 1)/2. Задача перечисления 2-минимальных примитивных наборов реша-ется, в частности, с использованием «решета Эратосфена».При k > 2 в соответствии с теоремой 1 и следствием 3 k-минимальный тупико-вый примитивный набор A = ( a i , . . . , ak) состоит из чисел aj = (^i . . . где( ^ i , . . . , ) -набор различных простых чисел. Тогда если < . . . < , то достаточноперечислить все наборы ( ^ 1 , . . . , ^) со свойством . . . ^ m. Заметим, что при1данных ограничениях < m k - 1 .Пусть n-е простое число есть pn . Тогда p1 = 2 ^ р2 = 3 ^ Для k > 2 обо-значим Фд = р3 . . . рд и положим Ф2 = 1. Значения Фд для k = 3 , . . . , 8 приведеныв табл. 1.Т а б л и ц а 1Значения функции Фдk 3 4 5 6 7 8Фд 5 35 385 5005 85085 1616615Для любого подходящего набора ( ^ 1 , . . . , ) из неравенства . . . ^ m приik > 2 следует, что р2 ^ ^ m k - 1 и для s = 3 , . . . , kim \ k - s +1где при s < k неравенство строгое.Алгоритм перечисления при k > 2 состоит в следующем. В качестве ^ переби-раем все простые числа в пределах, указанных двусторонним неравенством (4). При3 ^ s < k и каждом фиксированном наборе чисел ..., ) в качестве перебира-ем все простые числа в пределах, указанных в (4). При каждом фиксированном наборечисел ( ^ 3 , . . . , ) перебираем все простые числа и где 2 ^ < < m ъ- 1 .Оценим вычислительную сложность алгоритма, измеренную числом построен-ных наборов различных простых чисел ). Из алгоритма следует, что приs = 3 , . . . , k число различных значений не больше п ^(m/ (3Ф5 - 1 ) ) fc-s+^ (приs < k строго меньше). Число различных пар (^1 , ^ 2 ) не больше п(ж)(п(ж) - 1)/2 приiж = m k - 1 . Тогда общее количество искомых наборов оценивается величинойп ( m ^ ) ( п ( m ^ ) - 1 ) k / П п , ч 1 s=33 .k-s + 1При больших m и k эта величина имеет порядок не болееk 1О (kmk-1 ( m / 3 ) H ( k - 1 ) ) / ln2 m Д Фj =2где H(k - 1) = 1 + 1 + . . . + сумма первых (k - 1) членов гармоническо-2 3 k 2( ( k- 1 \\го ряда. Порядок последней величины не превышает O I ш1п к / I ln Ф^ I ) ПриV V j=2 ))k > 2 для оценки величин Фк можно использовать оценку [6]: рк > k ln k. Тогдаk! кф к > - П ln j 2 j=3Пусть теперь числа а 1 , . . . , ак не ограничены. Тогда наибольшее число в k-мини-мальном тупиковом примитивном наборе равно max(a1 , . . . , ак) = ... ^к С исполь-зованием точных значений простых чисел вычислены достижимые нижние оценки длянаибольших чисел в k-минимальных тупиковых примитивных наборах при k = 3 , . . . , 8(табл. 2).Т а б л и ц а 2Числовые границы для наборов длины kРазмер набора k 3 4 5 6 7 8Нижняя граница max(a1 , . . . , ак) 15 105 1155 15015 255255 48498455. Определение длин простых циклов с помощью поиска в глубинуДля определения длин простых циклов используем известный алгоритм поискав глубину [7].Пусть дан граф G = (V, E), где V - множество вершин графа, а E - множество егонеориентированных рёбер либо ориентированных дуг. Опишем алгоритм обхода всехрёбер графа. В качестве начальной выбираем произвольную вершину и двигаемся порёбрам, пока не встретится тупик (вершина, не имеющая исходящих рёбер, ведущихв непосещённые вершины). После попадания в тупик возвращаемся назад по прой-денному пути, пока не встретится вершина, у которой есть исходящие ребра, ведущиев непосещённые вершины, и из неё двигаемся дальше по одному из таких рёбер. Ал-горитм обхода рёбер завершает работу, когда встречается начальная вершина и все еёсоседние вершины уже посещены. Если после этого остаются непосещённые вершины,то повторяется поиск из одной из них в соответствии с вышеописанным алгоритмом.Алгоритм завершается, когда обнаружены все вершины графа.Для наглядности считаем, что в ходе работы алгоритма вершины графа могут бытьбелыми, серыми и чёрными. Изначально все вершины помечены белым цветом. Впер-вые обнаружив вершину v, красим её серым цветом. По окончании обработки всехисходящих рёбер красим вершину v в чёрный цвет. Таким образом, белый цвет соот-ветствует тому, что вершина ещё не обнаружена, серый - что вершина обнаружена, нопросмотрены ещё не все исходящие из неё ребра, чёрный - что вершина обнаруженаи все исходящие из неё рёбра просмотрены.Оценим вычислительную сложность реализацииалгоритма на однопроцессорнойсистеме. В качестве элементарных операций выберем прохождение ребра графа и срав-нение двух чисел. Так как каждое ребро проходится не более одного раза в прямоми обратном направлении, то время работы алгоритма поиска в глубину оцениваетсявеличиной O(n2).Модифицируем данный алгоритм поиска в глубину с целью определения длин всехпростых циклов. В частности, переходя в вершину u из вершины v по ребру (v,u),будем запоминать предшественника u, записывая p[u] = v. Для вершин, у которыхпредшественников нет, положим p[u] = -1.Рёбра ориентированного графа можно разделить на несколько категорий в зави-симости от их роли при поиске в глубину. Рёбра деревьев - это ребра, входящие в леспоиска в глубину. Обратные рёбра - это рёбра, соединяющие вершину c её предкомв дереве поиска в глубину. Прямые ребра - это рёбра, соединяющие вершину с её по-томком, но не входящие в лес поиска в глубину. Перекрёстные ребра -все остальные.Они могут соединять две вершины из одного дерева поиска в глубину, если ни однаих этих вершин не является предком другой, или же вершины из разных деревьев.Тип ребра (v,u) можно определить по цвету вершины u в момент, когда ребропроходится в первый раз: белый цвет означает ребро дерева ((v, u) войдёт в лес поискав глубину); серый (u является предком v) - обратное ребро; чёрный (ни одна из вершинне является предком другой) - прямое или перекрёстное ребро.Для каждой вершины v в процессе поиска в глубину запомним ещё два параметра:в d[v] запишем «время» i-го попадания в вершину, а в f [v] - «время» (i + 1)-го попада-ния. Здесь под «временем» понимается номер шага алгоритма. Если вершина u серая,то это означает, что последнее ребро - обратное и получен цикл, содержащий u. Еслиd[u] = 0, то данный цикл является простым, так как вершина u встретилась второйраз. Длина цикла равна разности f [u] - d[u].Вычисление длин простых циклов реализуется в ходе алгоритма поиска в глубинуи имеет порядок временной сложности O(n).Из полученного набора длин циклов необходимо выделить множество всех различ-ных длин с помощью упорядочивания чисел [8]. Сложность увеличится не более чемв O(log n) раз, то есть вычислительная сложность алгоритма определения длин всехпростых циклов графа оценивается величиной O(n2 log n).Ёмкостная сложность алгоритма определяется размером памяти, необходимым дляхранения матрицы смежности вершин графа, то есть составляет O(n2 ) битов.6. Определение экспонента графа с помощью возведения в степеньматрицы смежности вершинОпределение экспонента графа связано с возведением в степень матрицы M смеж-ности вершин графа и с проверкой положительности её элементов.Известна [9, 10] достижимаяоценка экспонента матрицы exp M ^ n2 - 2n + 2, гдеn - порядок матрицы. То есть если матрица M* имеет при t > n2 - 2n + 2 хотя бы одиннулевой элемент, то соответствующий граф не примитивен. Если M1 > 0, то матрицаи граф примитивны и exp M = exp Г ^ t.Для оценки вычислительной сложности алгоритма рассмотрим однопроцессорнуювычислительную модель. Элементарными операциями считаем сложение и умножениев кольце целых чисел. Рассмотрим операцию умножения в полугруппе Gn . Размернеобходимой памяти оценим в битах.Сложность умножения квадратных матриц размера n имеет порядок O(n3 ) . Приэтом для распознавания примитивности достаточно возвести матрицу в степень не вы-ше 2r , где r = |~log2(n2 - 2n + 2)]. С помощью алгоритма быстрого возведения в сте-пень [8] потребуется O(rn3 ) = O(n3 log2 n) операций для определения примитивностиматрицы.Опишем подробнее алгоритм быстрого возведения в степень для точного вычисле-ния экспонента матрицы. Возведем матрицу M в квадрат. Полученную после первоговозведения матрицу M2 ещё раз возведем в квадрат, получим M4 и т. д. Пусть матрицаMk положительна. Тогда вернемся к матрице Mk / 2 и умножим её на матрицу Mk / 4,и далее будем делить пополам отрезок, содержащий значение exp M, пока не опреде-лится наименьшая степень t, при которой матрица M1 положительна.Оценим ёмкостную сложность алгоритма. В памяти достаточно хранить матри-цы M г д е t = 20, 2 1 , . . . , 2 r - 1 . Таким образом, ёмкостная сложность алгоритма состав-ляет O(n2 log2 n).Сравним эти значения с оценками сложности алгоритма распознавания примитив-ности n-вершинного ориентированного графа с помощью поиска в глубину, получен-ными в п. 5. Результаты сравнения приведены в табл. 3.Т а б л и ц а 3Сложность алгоритмов распознавания примитивности графаАлгоритм Временная сложность Емкостная сложностьПоиск в глубину O(n2 log n) обращений к памяти O(n2) битВозведение в степень матрицысмежностиO(n3 log n) сложений и умноженийединиц и нулейO(n2log2 n) битОтметим, что, в отличие от первого алгоритма, второй определяет значение пока-зателя примитивности.

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

примитивный набор натуральных чисел, примитивный граф, примитивная матрица, экспонент, субэкспонент, primitive system of natural numbers, primitive matrix, primitive graph, exponent, subexponent

Авторы

ФИООрганизацияДополнительноE-mail
Кяжин Сергей НиколаевичНациональный исследовательский ядерный университет МИФИ, г. Москвастудент факультета кибернетики и информационной безопасностиlitota975@mephist.ru
Фомичев Владимир МихайловичНациональный исследовательский ядерный университет МИФИ, г. Москвадоктор физико-математических наук, профессор кафедры криптологии и дискретной математикиfomichev@nm.ru
Всего: 2

Ссылки

Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(11). С. 101-112.
Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000.
Биркгоф Г. Теория решеток. М.: Наука, 1984.
Арнольд В. И. Экспериментальное наблюдение математических фактов. М.: МЦНМО, 2006.
Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001.
Rosser B. The n-th prime is greater than n logn // Proc. London Math. Soc. 1939. V. 45. P.21-44.
Лахно А. П. Поиск в глубину и его применение // Московские олимпиады по информатике. М.: МЦНМО, 2006.
Порублев И. Н., Ставровский А. Б. Алгоритмы и программы. Решение олимпиадных задач. М.: Вильямс, 2007
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. S. 642-648.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. №2. С. 150-159.
 О примитивных наборах натуральных чисел | ПДМ. 2012. № 2(16).

О примитивных наборах натуральных чисел | ПДМ. 2012. № 2(16).

Полнотекстовая версия