Primitiveness conditions for systems of two graphs.pdf Пусть S = {A, B} - система двух неотрицательных матриц порядка n. Получим условия, при которых система S является примитивной. По определению система S примитивная, если мультипликативная полугруппа (A, B) содержит положительную матрицу. Длина наименьшего слова в алфавите S, соответствующего положительной матрице, называется экспонентом системы S, обозначается exp S. Далее слово w = = C1 • ... • Ci в алфавите S (то есть Ci G S, i = 1,... ,l) отождествляется с матрицей, равной произведению C1 • ... • Ci. Один из способов получения оценки exp S состоит в построении примитивного слова w. Если длина слова w равна l, то exp S ^ l • exp w. Получим условия на матрицы A и B, при которых слово AB примитивное. Воспользуемся аппаратом теории графов, что при исследовании примитивности равносильно. Если Г1 есть часть графа Г2, то обозначим это Г1 ^ Г2. Обозначим Г(А) n-вершинный орграф с матрицей смежности A. Пусть орграф Г(А) не содержит ациклических вершин, то есть состоит из k непересекающихся компонент сильной связности, 1 ^ k ^ n. Лемма 1. Если r(B) имеет петли в каждой вершине, то r(A) ^ T(AB). Следствие 1. В условиях леммы множество простых контуров орграфа r(AB) содержит все простые контуры орграфа r(A). Для орграфа r(A), не содержащего ациклических вершин, построим k-вершинный орграф Ta(B) с помощью отождествления некоторых вершин орграфа r(B): вершины i и j орграфа r(B) отождествляются, если и только если эти вершины принадлежат одной компоненте сильной связности орграфа r(A). Лемма 2. Если орграф Ta(B) сильносвязный, то орграф T(AB) тоже сильносвязный. В соответствии с универсальным критерием примитивности [1], орграф Г примитивный, если и только если Г сильносвязный и длины его простых контуров взаимно просты. Используя универсальный критерий, получим достаточные условия примитивности орграфа Г(АВ). Теорема 1. Пусть орграф Г(А) содержит контуры длин /i,..., , (/i,... , ) = 1, орграф Г(В) имеет петли в каждой вершине, орграф Га(В) сильносвязный. Тогда орграф Г(АВ) примитивный и exp S ^ 2exp(AB). Пусть орграф Г(А) гамильтонов. Не ограничивая общности, положим, что полный цикл есть (1, 2,..., n). Тогда в орграфе Г(В) вершине i с полустепенью исхода q^ соответствует множество дуг {(i, bi,i),... , (i, )}, i = 1,..., n. Обозначим de = НОД(р(^ bi,j): i = 1,... , n, j = 1,... ,q;), где p(i, j) = i - j, если i ^ j, и p(i, j) = n + i - j, если i < j. Теорема 2. Пусть орграф Г(А) содержит гамильтонов цикл (1,2, ...,n), орграф Г(В) имеет петли в каждой вершине и (n,de) = 1. Тогда орграф Г(АВ) примитивный и exp S ^ 2exp(AB). Пример 1. На рис. 1 иллюстрируется теорема 1 для матриц порядка 6 (6-вер-шинных графов). При отождествлении вершинам 1, 2, 3 орграфов Г(А) и Г(В) соответствует вершина а в Га(В), вершинам 4, 5 - вершина в, вершине 6 - вершина y. f 0 1 0 0 0 0 > f 1 0 0 1 0 0 > f 0 1 0 0 0 01 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 AB = 1 0 0 1 0 0 B = 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 ч 0 0 0 0 0 1V ч 0 0 1 0 0 1V ч 0 0 1 0 0 1V Н ж ш Г(В) Рис. 1. Пример, иллюстрирующий теорему 1 Г(АБ) Г(А) Полученные результаты могут быть использованы для оценки перемешивающих свойств итеративных функций, построенных на основе разветвления преобразования на два заданных преобразования [2].

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