The improvement of exponent's estimates for primitive graphs.pdf Матрицу A = (a^j) порядка n > 1 над полем действительных чисел называютнеотрицательной (положительной) и пишут A ^ 0 (A > 0), если a^j ^ 0 (a^j > 0)для всех i , j G { 1 , . . . , n } . Неотрицательную матрицу A называют примитивной, ес-ли A* > 0 при некотором натуральном t, а наименьшее натуральное Y, при которомAY > 0, называют экспонентом, или показателем примитивности матрицы A, иобозначают exp A.В ряде задач, в том числе криптографических, требуется определить экспонентыразличных матриц. Для решения таких задач на языке теории графов часто использу-ется эпиморфизм ^ мультипликативного моноида неотрицательных матриц порядка nна моноид n-вершинных орграфов, где умножение орграфов определено как умно-жение бинарных отношений [1, с. 212]. При эпиморфизме ^ матрице A соответствуеторграф Г с множеством вершин { 1 , . . . , n} и с множеством дуг U, где (i, j) G U, если итолько если a^j > 0, при этом матрица смежности вершин графа Г называется носи-телем матрицы A. Очевидно, 0, если и только если орграф Г =

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