On estimations for exponents of digraphs using frobenius's numbers.pdf Введение Одним из основных направлений в исследовании экспонентов примитивных неотрицательных матриц (примитивных сильносвязных графов) является уточнение известных оценок экспонентов для различных частных классов матриц (графов), важных для тех или иных приложений. Абсолютная оценка экспонента n-вершинного орграфа Г дана в [1]: ехрГ ^ ^ n2 - 2n + 2. Последующие результаты уточнили абсолютную оценку. Если длина кратчайшего простого контура в Г равна l [2, с. 227], то ехрГ ^ n + l(n - 2). Если, в частности, в орграфе Г имеется d петель [2, с. 408], то ехр Г ^ 2n - d - 1. Пусть в орграфе Г известны длины l и Л двух простых контуров C и Z [3], где (l,A) = 1, 1 < Л < l ^ n, n> 2 и h - число общих вершин контуров C и Z. Тогда ехр Г ^ lA - 2l - 3A + 3n, если h = 0, и ехр Г ^ lA - l - 3Л + h + 2n, если h > 0. Оценки экспонентов других частных классов графов имеются в работах [2,4-6]. Обзор результатов в этом направлении, полученных до 2012г., дан в [7]. Для новых частных классов n-вершинных орграфов приводятся достаточные условия примитивности и оценки экспонентов с использованием чисел Фробениуса. 1. Оценки экспонентов орграфов Пусть C = {C1,... , Ck} - система контуров в n-вершинном орграфе Г, длины контуров равны l1,...,lk соответственно, где k ^ 2 и l1 < ••• < lk. Систему C назовём примитивной, если (l1, . . . , lk) = 1. Тогда универсальный критерий примитивности орграфа Г [2, с. 226] допускает следующую формулировку: сильносвязный орграф Г примитивный, если и только если в Г имеется примитивная система контуров. Систему C назовем i-связанной, если каждый из контуров C1,...,Ck содержит вершину i, где i Е {1,... ,n}. В частности, система контуров перемешивающего графа биективного регистра левого (правого) сдвига длины n является n-связанной (1-связанной). Через g(l1,...,lk) обозначим число Фробениуса для натуральных аргументов l1,... , lk. Теорема 1. Пусть в сильносвязном орграфе Г имеется примитивная i-связанная система контуров C = {C1,... , Ck}, i Е {1,... ,n}, состоящая из q вершин орграфа. Тогда ехрГ ^ g(lb... ,lk) + 2(n - q + lk) - 1. Обозначим через [i, j]c простой путь, проходящий через вершины i, j и являющийся частью простого контура C. Длину пути w в Г, равную числу дуг, составляющих путь, обозначим l (w). Символом • обозначим конкатенацию путей графа Г. Пусть в орграфе Г контур C длины t, где 4 ^ t ^ n, содержит различные вершины i, j и r, тогда возможны два варианта: C = [i,r]c • [r,j]с • [j, i]c, (1) в этом случае положим l([i, j]C) = h > 2, l([i, r]C) = т < h; C =[i,j]с • [j,r]c • [r, i]c, (2) в этом случае положим l([i, j]c) = h < t - 2, l([j, r]c) = в < t - h. Теорема 2. 1) Пусть (i,r) и (r, j) -дуги орграфа Г, тогда Г - примитивный: - в случае равенства (1), если (t - h + 2, t - т + 1, t - h + т + 1) = 1, при этом exp Г < $(t - h + 2, t - т + 1, t - h + т + 1) + 2(n - t + тах{т, h - т}) - 1; - в случае равенства (2), если (9 + 1, t - h - 9 + 1, t) = 1, при этом exp Г < $(9 + 1,t - h - 9 + 1,t) + 2n - 1. 2) Пусть (r, i) и (j,r) -дуги орграфа Г, тогда Г - примитивный: - в случае равенства (1), если (т + 1 , h - т + 1 , t) = 1 , при этом exp Г < $(т + 1,h - т + 1,t) + 2n - 1; - в случае равенства (2), если (t - 9 + 1, h + 2, h + 9 + 1) = 1, при этом exp Г < $(t - 9 + 1,h + 2,h + 9 + 1) + 2(n - t + max{9,t - h - 9}) - 1. Примеры. Пусть n = 100, C = (1,..., 80), t = 80, i = 1, j = 41, тогда h = 40. 1) Пусть r = 33, (1, 33) и (33, 41) - дуги орграфа Г, тогда т = 32 и (t - h + 2, t - т + 1,t - h + т + 1) = (42,49, 73) = 1, то есть по п. 1 теоремы 2 орграф Г примитивный и exp Г < $(42, 49, 73) + 103. Используя обозначения работы [8], определим $(42,49,73). Вычисляем: d = = (42,49) = 7, z = 7 ■ 29 = 203, тогда | | = |C(42, 49)| = 30/2 = 15, (42, 49) = 7 ■ {0, 6, 7,12,13,14,18,19, 20, 21, 24, 25, 26, 27, 28}, C(42, 49) = 7 ■ {1, 2, 3, 4, 5,8, 9,10,11,15,16,17, 22, 23, 29}, S(73) = 0, $(42,49, 73) = z + (d - 1)73 = 203 + 6 ■ 73 = 641 и exp Г < 744. Оценки exp Г по формулам работ [1, 2, 3] равны 9802, 4216 и 3109 соответственно. 2) Пусть r = 55, (1,55) и (55, 41) - дуги орграфа Г, тогда 9 =14 и (9 + 1,t - h - 9 + 1,t) = (15, 27,80) = 1, то есть по п. 1 теоремы 2 орграф Г примитивный и exp Г < $(15, 27, 80) + 199. Определим $(15,27,80). Вычисляем: d = (15,27) = 3, z = 3 ■ 31 = 93, тогда |

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