Оценки экспонентов примитивных графов | ПДМ. 2011. № 2(12).

Оценки экспонентов примитивных графов

Уточнены оценки экспонентов для n-вершинных примитивных орграфов (неотрицательных матриц порядка n), содержащих два простых контура, длины которых взаимно просты. Получены достижимые оценки порядка O(max{lA,/(l,X,n)}), где l и А - взаимно простые длины простых контуров в орграфе и /(l,A, n) - линейный полином. Описан полностью класс примитивных орграфов, на которых достигается абсолютная оценка экспонента n2 - 2n + 2 (H. Wielandt, 1950).Для экспонентов неориентированных n-вершинных примитивных графов доказаны уточняющие оценки. В частности, если l - длина длиннейшего простого цикла нечетной длины в графе Г, то экспонент графа Г не превышает 2n - l - 1. Описан полностью класс примитивных неориентированных графов, на которых достигается абсолютная оценка экспонента 2n - 2.

The Estimates of Exponents for Primitive Graphs.pdf ВведениеРассмотрим неотрицательную (положительную) матрицу A = (ai;j) порядка n > 1над полем действительных чисел, т. е. ai;j ^ 0 (ai;j > 0) для всех i, j е { 1 , . . . , n}, свой-ство неотрицательности (положительности) матрицы A обозначим так: A ^ 0 (A > 0).Неотрицательную матрицу A называют примитивной, если A* > 0 при некоторомнатуральном t, а наименьшее натуральное Y, при котором AY > 0, называется экспо-нентом, или показателем примитивности матрицы A, и обозначается exp A. Еслитакого t не существует, то exp A = то.Важной задачей, в частности для криптографических приложений, является опре-деление экспонентов матриц из различных классов. При исследовании экспонентовматриц часто используется эпиморфизм ^ мультипликативного моноида неотрица-тельных матриц порядка n на моноид n-вершинных орграфов, где умножение оргра-фов1 определено как умножение бинарных отношений [1, с. 212]. При эпиморфизме ^матрице A соответствует орграф Г с множеством вершин {1,... , n} и с множествомдуг U, где (i, j) е U ^ ai;j > 0, при этом матрица M смежности вершин графа Г назы-вается носителем матрицы A. Очевидно, 0 ^ орграф Г = 3, и оценкиэкспонентов графов, n > 2. Описаны все n-вершинные орграфы и графы, на которыхдостигаются абсолютные оценки exp Г.1. Свойства экспонентов графовДалее через C обозначим контур в орграфе и через C* - мультимножество вершинконтура C, в случае простого контура - множество вершин.Множество W(Г) всех путей орграфа Г образует частичный моноид относительнооперации конкатенации (обозначим ее ), операция определена на паре путей (u,v),если и только если конечная вершина пути u совпадает с начальной вершиной пути v.Результат конкатенации пути u с начальной вершиной i и конечной вершиной a ипути v с начальной вершиной a и конечной вершиной j есть путь w = u v с начальнойвершиной i и конечной вершиной j. При этом len(w) = len(u) + len(v), где len(w) -длина пути w е W(Г), измеряемая числом дуг (или ребер), составляющих путь w.Единицей частичного моноида W(Г) является пустой путь w0, где len(w0) = 0.При обходе контура C выделим его вершину a как начальную, контур C в этомслучае обозначим C(a). Для целого неотрицательного q через q-C(a) обозначим контур,составленный из q-кратнопройденного контура C(a), где 0 C(a) = w0.Обозначим при i = j, где i, j е { 1 , . . . , n}, через w(i, j) путь из i в j; [i, j] -крат-чайший путь из i в j; [i,i] -кратчайший контур, проходящий через вершину i. ДляH, P С { 1 , . . . , n} обозначим через dist(H, P) расстояние в графе Г между множества-ми H и P:( min len[i, j], H П P = 0,dist(H, P) = J (м)еяхрI 0, H П P = 0.Множество W путей из i в j (при i = j - контуров), где i , j е { 1 , . . . , n } , назо-вем (t,/)-множеством путей, t,/ - натуральные, если в W имеется / путей (контуров),длины которых равны t, t + 1 , . . . , t + l - 1 .Для получения оценки экспонентов примитивных графов отметим ряд свойств. Изкритерия примитивности орграфа следует достаточное условие.Утверждение 1. Сильносвязный орграф примитивен, если содержит два про-стых контура, длины которых взаимно просты.Пусть M - матрица смежности вершин графа Г и M1 = ( m f j ) , / ^ 1.Утверждение 2 [4, следствие 1 теоремы 2, с. 114]. Число путей длины / из i в jв n-вершинном графе Г равно элементу mfj матрицы M г д е / ^ 1.Утверждение 3.а) Если M1 > 0 при натуральном /, то M4 > 0 при любом t > /.б) Если в n-вершинном сильносвязном орграфе Г (связном графе Г'), где n > 1,имеются пути из i в j длины / > 0 для любых i, j е { 1 , . . . , n}, то орграф Г (граф Г')примитивен и exp Г ^ /.в) Если для некоторых i, j е { 1 , . . . , n} и для натурального т в примитивном ор-графе Г (в графе Г') не имеется путей из i в j длины т, то exp Г > т.Доказательство.а) Если M1 > 0, то mfj > 0 для всех i, j е {1,... , n}. Вместе с тем в матрице Mкаждая строка и каждый столбец ненулевые, иначе M1 > 0 не выполнено, отсюдаmS(j) j > 0 при любом j = 1,..., n и некотором s(j) е { 1 , . . . , n}. Тогда из равенстваM1+1 = M1M следует, что m( = ^ m( ^mSj ^ m( ^(^mSj) j > 0 для всех i , j еs=1е { 1 , . . . , n}. Значит, M1+1 > 0.б) и в) следуют из утверждений 2 и 3,а. Утверждение 4. Пусть в n-вершинном орграфе Г при n > 1 имеется контур Cдлины / и (t, /)-множество путей из i в j, каждый из которых проходит через некоторуювершину контура C, тогда в Г имеются пути из i в j длины т при любом т ^ t, где i , j е { 1 , . . . , n } .Доказательство. Пусть путь w(s) из (t, /)-множества путей графа Г есть путьиз i в j длины t + s, проходящий через вершину a контура C, s = 0,1,..., / - 1.Тогда при a е {i, j} путь w(s) может быть представлен конкатенацией двух путей:w(s) = w(i,a) w(a,j), где len(w(i,a)) + len(w(a,j)) = len(w(s)) = t + s. Построимпути uq из i в j длины t + s + q/, где q = 0,1,...:ugs) = (q C(a)) w(s), если i = a;uqs) = w(s) (q C(a)), если j = a, i = j;uqs) = w(i, a) (q C(a)) w(a, j) в остальных случаях.По построению len(uqs)) = q/ + t + s, где q = 0,1,..., s = 0,1,... , / - 1. Значит,в семействе путей {uqs ) } имеется путь из i в j длины т при любом т ^ t. 2. Оценки экспонентов орграфовПусть в орграфе Г имеются простые контуры C и C' длины соответственно / и Л,где, не теряя общности, положим 1 < Л < / ^ n. Обозначим 9 = (/ - 1)(Л - 1).Для вершин i и j контура (цикла) C обозначим через p(i, j) длину кратчайшегопути от i до j, составленного только из дуг контура (ребер цикла) C, и положимp(i,i) = 0. При i = j имеем p(i,j) ^ l - 1 для орграфа и p(i,j) ^ \}/2\ для графа.Для вершины i и подмножества H вершин контура (цикла) C обозначим через p(i, H)длину кратчайшего пути от i до ближайшей вершины множества H, составленноготолько из дуг контура (ребер цикла) C. Если |H| = h, то p(i, H) ^ l - h для контура Cорграфа. Аналогичные расстояния на контуре C обозначим р'.Теорема 1. Пусть (l, Л) = 1, n > 2, тогда:а) если C* П C'* = 0, то exp Г ^ 1Л - 21 - 3Л + 3n;б) если C* П C'* = H, где |H| = h > 0, то exp Г ^ 1Л - l - 3Л + h + 2n.Доказательство. В условиях теоремы граф Г примитивен. Для полученияоценки exp Г построим (t, Л)-множество путей из i в j для любых i , j Е { 1 , . . . , n },каждый из которых проходит через некоторую вершину контура C'.Множество чисел {ql mod Л : q = 0 , 1 , . . . , Л - 1} в силу взаимной простоты чисел lи Л образует полную систему неотрицательных вычетов по модулю Л, при этом числа qlне превосходят (Л- 1)l. Значит, для любого q = 0,1,... , Л - 1 найдется неотрицательноецелое число z(q), такое, что в ^ ql + z ( q ^ ^ (Л - 1)l, при этом{ql + z ( q^ : q = 0, 1,. . . , Л - 1} = N (в, Л), (2)где N (в, Л) = {в, в + 1,..., в + Л - 1}; равенство (2) известно как лемма Шора.а) Пусть C* П C'* = 0, a,b Е C*, a', b' Е C'*, где len[a,a'j = dist[C*,C'*],len[b',b] = dist[C'*,C*] (рис. 1). Определим пути uq(i, j) и vq(i, j) из i в j, проходящиечерез вершины контура C', q = 0,1,... , Л - 1:uq(i, j) = q C(a) [a, a'] z(q) C'(a'), если i = a, j = a';uq(i, j) = q C(a) [a, a'] z(q) C'(a') [a', j], если i = a, j = a';uq(i,j) = [i,a] q C(a) [a, a'] z(q) C'(a'), если i = a , j = a';uq(i, j) = [i, a] q C(a) [a, a'] z(q) C'(a') [a', j], если i = a, j = a';vq(i, j) = z(q) C'(b') [b',b] q C(b), если i = b', j = b;vq(i, j) = z(q) C'(b') [b', b] q C(b) [b, j], если i = b', j = b;vq(i, j) = [i, b'] z(q) C'(b') [b', b] q C(b), если i = b', j = b;vq(i, j) = [i, b'] z(q) C'(b') [b', b] q C(b) [b, j], если i = b', j = b.Рис. 1. Непересекающиеся контуры C и C в орграфеДлины путей uq(i, j) и vq(i, j) соответственно равны:len(uq(i, j ) ) = q/ + z ( q ^ + len[a,a'], если i = a, j = a'; (3)len(uq(i,j)) = q/ + z ( q ^ + len[a,a'] + len[a',j], если i = a , j = a'; (4)len(uq(i,j)) = q/ + z ( q ^ + len[i,a]+ len[a, a'], если i = a , j = a'; (5)len(uq(i, j ) ) = q/ + z^)Л + len[i, a] + len[a, a'] + len[a', j], если i = a, j = a'; (6)len(vq(i, j ) ) = q/ + z ( q ^ + len[b',b], если i = b', j = b; (7)len(vq(i,j)) = q/ + z ( q ^ + len[b',b]+ len[b,j], если i = b',j = b; (8)len(vq(i,j)) = q/ + z(q)Л + len[i,b']+ len[b',b], если i = b',j = b; (9)len(vq(i, j ) ) = q/ + z ( q ^ + len[i,b'] + len[b',b] + len[b, j], если i = b', j = b. (10)Из формул (3)-(6) следует, что в соответствии с леммой Шора для любых i, j ее { 1 , . . . , n} множество путей {uq(i, j) : q = 0 , 1 , . . . , Л-1} есть (9+10(i, j ) , Л)-множествопутей из i в j , гдеt0(i, j) = len[a,a'], если i = a, j = a'; (11)t0(i, j) = len[a,a'] + len[a', j], если i = a, j = a'; (12)t0(i,j) = len[i,a] + len[a,a'], если i = a , j = a'; (13)t0(i, j) = len[i,a] + len[a,a'] + len[a', j], если i = a, j = a'. (14)Аналогично из формул (7)-(10) следует, что в соответствии с леммой Шора длялюбых i, j е { 1 , . . . , n} множество {vq(i, j) : q = 0 , 1 , . . . , Л - 1} есть (9 + t1(i, j ) , Л)-множество путей из i в j, гдеt1(i,j) = len[b',b], если i = b', j = b; (15)t1(i, j) = len[b',b] + len[b, j], если i = b', j = b; (16)t1 (i, j) = len[i, b'] + len[b',b], если i = b',j = b; (17)t1(i, j) = len[i, b'] + len[b',b] + len[b, j], если i = b', j = b. (18)Следовательно, в соответствии с утверждениями 3,б и 4exp Г ^ 9 + max{min{t0(i, j ) , t 1 ( i , j ) } } . (19)(i>j)Оценим величины t0(i, j) и t1 (i, j). Пусть w, - кратчайший путь от i до ближайшейвершины контура C (z - конечная вершина) при i е C*, не проходящий через верши-ны контура C'; u, - кратчайший путь от i до ближайшей вершины контура C' (z' -конечная вершина) при i е C'*, не проходящий через вершины контура C. В W(Г) со-держится хотя бы один из путей w, и u, при любом i е C* U C'*. Тогда верны следующиеоценки:len[i, a] ^ len(w,) + p(z,a), если w, е W(Г) и i е C*; (20)len[i,a] ^ p(i,a), если i е C*; (21)len[i, b'] ^ len(u,) + p'(z', b'), если u, е W(Г) и i е C'*; (22)len[i,b'] ^ p'(i,b'), если i е C'*; (23)len[a'j, ] ^ n - 1, если j / C'*; (24)len[a', j] ^ p'(a', j ) , если j Е C'*; (25)len[b, j] ^ n - 1, если j Е C*; (26)len[b, j] ^ p(b, j ) , если j Е C*. (27)В соответствии с (20) и (21) наибольшее значение оценка len[i,a] принимает приi Е C*, и в соответствии с (22) и (23) наибольшее значение оценка len[i,b'] принима-ет при i Е C'*. Значит, при i Е C* U C'* независимо от того, какой из путей Wj, uсодержится в W(Г),min{len[i, a], len[i,b']} ^ max{len(w»), len(u»)} + max{p(z, a), p'(z', b')};при i Е C* U C'* оценка min{len[i, a], len[i,b']} ниже этой. При любом i Е C* U C'*в соответствии с определением путей Wj, щ верна оценкаmax{len(wj), len(u»)} ^ n - l - Л,отсюда, учитывая, что p(z,a) ^ l - 1 и p'(z',b') ^ Л - 1, получаем для любого i ЕЕ { 1 , . . . , n}min{len[i, a], len[i, b']} ^ n - Л - 1. (28)Кратчайший путь из a в a' (из b' в b) по определению не содержит вершин конту-ров C и C', исключая начальную и конечную вершины, поэтомуmax{len[a, a'], len[b,b']} ^ n - l - Л + 1. (29)Для len[a', j] и len[b, j] в соответствии с (24)-(27) при любом j Е { 1 , . . . , n} вернаоценкаmax{len[a',j], len[b,j]} ^ n - 1. (30)Из формул (11)-(14) и (15)-(18) следует, что для любых i, j Е { 1 , . . . n}to(i,j) ^ len[i,a] + len[a,a'] + len[a',j],ti(i, j) ^ len[i,ba'] + len[b',b] + len[b, j],где первая оценка достигается при i = a, j = a', а вторая - при i = b', j = b (см. рис. 1).В остальных случаях оценка t0(i, j) ниже этой. Следовательно,т Ы ш т ^ о ^ Д ^ j ) } } ^^ min{len[i, a], len[i,b']} + max{len[a, a'], len[b',b]} + max{len[a', j], len[b, j ] } ,отсюда в соответствии с (28)-(30) получаемmax{min{t0(i, j),t1 (i, j ) } } ^ 3n - l - 2Л - 1.Из этой оценки и из (19) получаем оценку теоремы 1,а.б) Пусть H = C* П C'* и a Е H (рис. 2). Определим пути wq (i, j) из i в j, проходящиечерез вершину a контура C', где q = 0 , 1 , . . . , Л - 1:wq(i, j) = q C(a) z(q) C'(a), если i = j = a;wq(i, j) = q C(a) z(q) C'(a) [a, j], если i = a, j = a;wq(i, j) = [i, a] q C(a) z(q) C'(a), если i = a, j = a;wq(i, j) = [i, a] q C(a) z(q) C'(a) [a, j], если i = a, j = a.Длины путей wq(i, j) соответственно равныlen(wq(i, j ) ) = ql + z(q)Л, если i = j = a;len(wq(i, j ) ) = ql + z^)Л + len[a, j], если i = a, j = a;len(wq(i, j ) ) = ql + z ( q ^ + len[i, a], если i = a, j = a;len(wq(i, j ) ) = ql + z(q) Л + len[i,a] + len[a, j], если i = a, j = a.(31)(32)(33)(34)Рис. 2. Пересекающиеся контуры C и C' в орграфеИз формул (31)-(34) следует, что в соответствии с (2) для любых i, j Е { 1 , . . . ,n}множество путей {wq(i, j) : q = 0,1,... , Л - 1} есть (0 + t2(i, j ) , Л)-множество путей из iв j , гдеt2(i, j) = 0, если i = j = a;t2(i, j) = len[a, j], если i = a, j = a;t2(i, j) = len[i,a], если i = a , j = a;t2(i, j) = len[i,a] + len[a, j], если i = a, j = a.Следовательно, в соответствии с утверждениями 3,б и 4exp Г ^ 0 + max t2(i, j).( j>j )(35)(36)(37)(38)(39)В случае б путь wj при i Е C* и путь щ при i Е C'* определим так же, какв случае а, за исключением того, что конечные вершины путей могут, в частности,принадлежать H. В W(Г) для i Е C* U C'* содержится хотя бы один из путей wj и щ^.В соответствии с (20)-(23) при i Е C* U C'*dist(i,H) ^ min{len(wi), len(u^)} + max{p(z, H),p'(z',H)},при i Е C* U C'* оценка dist (i, H) ниже этой. При любом i Е C* U C'* по определениюпутей wj и Ujmin{len(w^), len(ui)} ^ n - l - Л + h,p(z, H) ^ l - h, p'(z',b') ^ Л - h. Тогда независимо от того, какие из путей wj, Ujсодержатся в W(Г), для любого i Е { 1 , . . . , n} верна оценкаdist (i, H) ^ n - Л. (40)Пусть w* - кратчайший путь от контура C до j (y - начальная вершина) приj Е C* U C'*, не проходящий через вершины из C'*, за исключением, быть может,начальной вершины, и u* -кратчайший путь от контура C' до j (y' - начальная вер-шина), не проходящий через вершины контура C, за исключением, быть может, на-чальной вершины. В W(Г) содержится хотя бы один из путей w* и u*. Значит, дляj / C* U C' * и для любого a H выполненоlen[a,j] ^ max{p(a,y) + len(w*),p'(a,y') + len(u*)}(при j Е C* U C'* и любом a Е H оценка len[a, j] ниже этой), где по определению путейw* и u*len(w*) ^ n - l - Л + h, len(u*) ^ n - l - Л + h,и p(a,y) ^ l - 1, p'(a,y') ^ Л - 1. Отсюда, независимо от того, какие из путей w*, u*содержатся в W(Г), получаем для любого j Е {1,... , n} и любого a Е Hlen[a,j] ^ n - Л + h - 1. (41)Из формул (35)-(38) следует, что для любых i, j {1, . . . , n}t2(i,j) ^ dist(i,H) +max{len[a,j]}, aEHгде наибольшее значение оценки достигается при i , j Е H (см. рис.2). В осталь-ных случаях оценка t2(i, j) ниже этой. Следовательно, используя оценки (40) и (41),получаемmaxt2(i, j) ^ 2n - 2Л + h - 1.Из этой оценки и из (39) получаем оценку теоремы 1,б. Следствие 1. Для любого примитивного n-вершинного орграфа Г при n > 2верно:а) если циклы C и C' не имеют общих вершин, тоexp Г ^ n + 12n + 12 ^ n2/4 + n/2 + 1/4;б) если циклы C и C' имеют h общих вершин, где 1 ^ h ^ Л, тоexp Г ^ n + h + 2. 2 .n + h + 2-2 - 2h - n ^ n2 - 2n + 2.Доказательство.а) По теореме 1,a exp Г ^ ^(n, l, Л), где ^(n, l, Л) = 1Л - 2l - 3Л + 3n. Заметим, что-0(n, l, Л) - -0(n, l, Л - 1) > 0 при любых допустимых n, l. Так как Л ^ n - l, тоexp Г ^ ^(n, l, n - l) = (n + 1 - l)l,г где произведение (n - l + 1)l принимает наибольшее значение при l = -n 2+-1б) По теореме 2,б exp Г ^ 2 в графе Г' (рис. 3);a и b - конечные вершины кратчайших путей от цикла C соответственно до i и до j,где i, j Е C*, a, b Е C*. Определим пути u(i, j) и v(i, j) из i в j:u ( ^ j ) = z ( ^ j j ) = У(^ j ) , е с л и i , j Е C*;u ( i , j ) = [ i , a ] z ( a , j ) , v ( i , j ) = [ i , a ] y ( a , j ) е с л и i Е C * , j Е C*;u ( i , j ) = z ( i , b ) [ Ъ , j ] , v ( i , j ) = y ( i , b ) [ Ъ , j ] , е с л и i Е C*, j Е C*; u ( i , j ) = [ i , a ] z ( a , b ) [ b , j ] , v ( i , j ) = [ i , a ] y ( a , b ) [ b , j ] , е с л и i , j Е C*.Тогда пара путей (u(i, j),v(i, j ) ) в соответствии с утверждением 5 образует (t(i, j), 2)-множество путей из i в j при любых i, j Е { 1 , . . . , n}, гдеt (^ j ) = l' - P( i , j ) - 1 е с л и i, j Е C*;t(i, j) = len[i,a] + l' - p(a, j) - 1, если i Е C*, j Е C*;t(i, j) = l' - p(i, b) - 1 + len[b, j], если i Е C*, j Е C*;t(i, j) = len[i, a] + l' - p(a, b) - 1 + len[b, j], если i, j Е C*.В соответствии с определением max{len[i,a],len[b, j]} ^ e(C) ^ n - l' при всех i, j Е C*и p(a, b) ^ 0 при всех a, b Е C*. Значит, t(i, j) ^ 2e(C) + l' - 1 ^ 2n - l' - 1 прилюбых i, j Е { 1 , . . . , n}, т. е. exp Г' ^ 2e(C) + l' - 1 ^ 2n - l' - 1. Так как рассмотренпроизвольный простой цикл нечетной длины l' > 2, то получаем оценку теоремы 3,а.Рис. 3. Цикл C в неориентированном графеЕсли n > 1 и l = 1, т. е. в Г' имеется петля в вершине a и не имеется цикловнечетной длины l' > 2, то пути u(i, j) и v(i, j) из i в j определим так:u(a, a) = 2 (a, a), v(i, j ) = (a, a);u(i, a) = [i, a] (a, a), v(i, a) = [i, a], если i = a;u ( a j ) = ( a , a ) К j L ^ ^ j ) = [a, j ] , е с л и j = a;j ) = [ i , a ] ( a , a ) [a j j ) = [ i , a ] [a, j ] , е с л и i = a , j = a.Пара путей (u(i, j), v(i, j ) ) в соответствии с утверждением 5 образует (t(i, j), 2)-множество путей из i в j при любых i , j Е { 1 , . . . , n } , где t(a,a) = 1, max{t(i,a),t(a, j ) } ^ n - 1 при i = a, j = a и t(i, j) ^ 2n - 2 при i = a, j = a. Следовательно,t(i, j) ^ 2n - 2 при любых i, j Е { 1 , . . . , n}, т. е. exp Г' ^ 2n - 2 при n > 1. Эта оценкасовпадает с оценкой 2n - l - 1 теоремы 3,а при l = 1.б) При условиях теоремы 3, б i Е C*, где Cj - простой цикл нечетной длины lj иC* -блок покрытия множества вершин, i Е { 1 , . . . , n } . Пусть b - концевая вершинакратчайшего пути от цикла Cj до j, где b Е C*. Тогда (t(i, j), 2)-множество путей из iв j при любых i, j Е { 1 , . . . , n} образовано путями u(i, j) и v(i, j) из i в j, где при n > 2u ( i , j ) = z ( i , j ) , v ( i , j ) = y ( i , j ) , е с л и j Е C*; u ( i , j ) = z ( i , b ) [ b , j ] , v ( i , j ) = y ( i , b ) [ b , j ] , е с л и j Е C*Отсюда, обозначая через pj расстояния на цикле Cj, i Е { 1 , . . . , n}, получаемt (^ j ) = к - pj( i , j ) - 1, е с л и j Е C*;t(i, j) = lj - pj(i, b) - 1 + len[b, j], если j Е C*.В соответствии с определением len[b, j] ^ n - U при всех j Е C* и pj(i,b) ^ 0 при всехb Е C*. Отсюда t(i, j) ^ n - 1 при любых i, j Е { 1 , . . . , n}, т. е. exp Г' ^ n - 1 при n > 2.Теорема доказана. Если n = 2, то при условиях теоремы 3,б граф Г' полный, следовательно, exp Г' = 1.При l = 1 из теоремы 3,а получаем известную оценку для связных графов с петлей.Следствие 2. Для любого примитивного n-вершинного графа Г' имеет местоexp Г' ^ 2n - 2.Обозначим через Гр(n) множество примитивных n-вершинных графов, состоящихиз гамильтонова пути w и петли, инцидентной одной из концевых вершин.Теорема 4. При любом n > 1 множество ГР (n) состоит из n! изоморфных гра-фов; абсолютная оценка 2n - 2 достигается на графах из Гр (n), и только на них.Доказательство. Из определения множества Гр (n) следует, что оно инвари-антно относительно любой перенумерации вершин, следовательно, Гр(n) состоит изn! изоморфных графов. По следствию теоремы 3 exp Г' ^ 2n - 2 для любого графаГ' Е Гр (n).Пусть граф Г' состоит из гамильтонова пути P = (1, 2,... , n) и петли (n, n). Тогдапути из 1 в 1 нечетной длины 2n - 3 не существует. Значит, в соответствии с утвер-ждением 3,в exp Г' = 2n - 2.Покажем, что на связном графе Г, не принадлежащем Гр(n), оценка 2n - 2 не до-стигается. В силу теоремы 3,а абсолютная оценка 2n - 2 достижима только на связномграфе Г с петлей, не имеющем циклов нечетной длины l > 1.Пусть Г - гамильтонов цикл (1, 2,... , n) с петлей в вершине i, где i Е { 1 , . . . , n},или гамильтонов путь с петлей в вершине i, где 1 < i < n, тогда e(i) ^ n - 2.Пусть Г не есть гамильтонов путь или цикл, т. е. содержит, кроме петли в вершине i,где i Е { 1 , . . . ,n}, вершину r степени выше 2. Кратчайший путь [i, j] при i = j либопроходит, либо не проходит через вершину r. Тогда в первом случае len[i, j] ^ len[i, r] ++len[r, j] ^ n - 2, так как кратчайшие пути [i,r] и [r,j] не содержат общих вершин,кроме r (иначе кратчайший путь [i, j] не проходит через r), и содержат не более двухвершин, смежных с r. Во втором случае len[i, j] ^ n - 2, так как путь [i, j] не содержитвершину r. Следовательно, e(i) ^ n - 2, если Г Е Гр(n), и по теореме 3,а exp Г ^ 2n - 4.Теорема доказана.

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

примитивные графы, экспонент графа, graph exponent, primitive graphs

Авторы

ФИООрганизацияДополнительноE-mail
Фомичев Владимир МихайловичИнститут проблем информатики РАН, г. Москвастарший научный сотрудник, доцент, доктор физико-математических наук, ведущий научный сотрудникfomichev@nm.ru
Всего: 1

Ссылки

Берж К. Теория графов и её применение. М.: ИЛ, 1962.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. P. 642-648.
Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000.
Биркгоф Г. Теория решёток. М.: Наука, 1984.
 Оценки экспонентов примитивных графов | ПДМ. 2011. № 2(12).

Оценки экспонентов примитивных графов | ПДМ. 2011. № 2(12).

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