Примитивность систем матриц и систем графов

А Рассмотрим систему 0, 1-матриц М = {М_х,…, М_р} и мультипликативную полугруппу (М), состоящую из всех слов в алфавите М. Пусть w = w_x… w_t е N_p*. Каждому слову (M_W{, …, M_w) е (М) однозначно соответствует произведение матриц M (w) = Слово (М_и^, …, М_а>) называется.

положительным (примитивным), если матрица M (w) положительная (примитивная^. Подмножество всех положительных (примитивных) слов полугруппы (М) обозначим М₊ (М_Р). По определению М₊ с М _Р.

Система М называется множественно примитивной, если при некотором I е N положительны все слова длины / в алфавите М, а наименьшее такое / называется множественным экспонентом системы М. Множественный экспонент любой множественно примитивной системы не превышает 2″ - 2 |8|. Имеются оценки множественного экспонента для некоторых частных классов систем^[1].

Лк А Система М называется примитивной, если М₊ Ф 0, а наименьшая длина положительного слова называется экспонентом системы М (обозначается ехрМ).

Для слова w = w_x…w_t через w{т) обозначим подслово w_x…w_x, т = 1, …, t.

Систему М назовем субпримитивной, если А/И > 0 для некоторого слова.

w е N_p*, где ЛЯ® 1 = ^ M (?f;(T)). Субэкспонентом системы М (обозначается, А ^Т=1

sbxpAf) называется наименьшая длина t слова w, для которого М№ 1 > 0. Если М примитивная, то она и субпримитивная, и sbxpM < ехрМ.

На множестве систем 0, 1-матриц порядка п задан квазипорядок: М >

> М' для указанных систем М, М' для любой матрицы М' е М' имеется матрица Me М, где М>М'. В частности, М > М если М з М'. Если М > М',

А, А А, А то в соответствии с утверждением 11.1 ехрМ < ехрМ' и sbxpM < sbxpM'. Теорема 11.8:

• а) система М примитивная М_РФ 0; если t_w — длина примитивного слова w е М _Р, то ехрМ < t_wexpw;
• б) если система М примитивная, то матрица М = М_{ + … + М_р также примитивная, и ехрМ > ехрМ.

М а) заметим, что М₊Ф0М_РФ0, поскольку если w е М _р и ехрш = г, то r-кратная конкатенация слова w принадлежит М₊. Тогда ехрМ < t_wr, б) при любом t е N матрица М^[1] есть сумма матриц, соответствующих всем словам длины t в алфавите М. Если хотя бы одному слову длины t соответствует положительная матрица, то M^f > 0. Следовательно, ехрМ >

> ехрМ. ?

Пусть M_r — матрица смежности вершин орграфа Г,., тогда системе М соответствует система орграфов Г = {Г_х>…, Г^} или мультиграф ТО*) = и… и и Г., в котором дуга графа Г., помечена символом г, г = 1, г?. Система.

? А, А А Л графов Г примитивная система матриц М примитивная, ехрГ = ехрА/.

а В соответствии с теоремой 3.4 система Г примитивная, если найдется слово w = w_x…w_t такое, что для любых i, j е N_n в Г имеется путь длины t из i в j с меткой w, наименьшая длина t такого слова равна ехрГ.

А Теорема 11.9. Система матриц М субпримитивная мультиграф Г0>) сильно связный. Если система М субпримитивная, то diam№) < sbxpM.

Л Пусть система матриц М не субпримитивная, тогда для некоторых i_yje {1, …, п) при любом слове w = w_x…w_t е N_p* равен 0 элемент матрицы M^w 1 с координатами i, j_f и, следовательно, равен 0 элемент матрицы M (w) с координатами z, j. Отсюда по теореме 3.4 в Пр) вершина j не достижима из i за любое число шагов, т. е. мультиграф IW не сильно связный.

Л, А Пусть sbxpM = t_y тогда М№ 1 > 0 для некоторого слова w длины t. Значит, для любых iyj е {1,…, п) при некотором т е {1,…, t} элемент матрицы M (w (т)) с координатами i, j равен 1. Следовательно, по теореме 3.4 вершины i, j в Пр) взаимно достижимы не более чем за т шагов, где т < t. Тогда мультиграф №> сильно связный и diam№)< t. ?

Теорема 11.10 (универсальная оценка субэкспонента системы графов [12]). Если система Мсубпримитивная, п > 4, то sbxpM < (гг² — 2)(п — 1) / 2.

М Обозначим Х (п) = (гг² — гг) / 2. Опишем гг шагов построения слова w = w_x…w_t е N_p*y где t<(n² — 2)(п — 1) / 2, при котором М1®1 > 0. На i-м шаге построим начальный отрезок слова w, при котором положительны все А.

элементы первых i строк матрицы M^w i = 1,…, гг.

1-й таг. В сильно связном мультиграфе Г (р) имеется полный контур С_х длины /(1), где /(1) < Х (п) [56|. Пусть 1 — начальная вершина контура С_х и w (l ( 1)) — метка контура С_х (слово длины /(1) в алфавите N_p*). Тогда при j = 1, п в Г (р) имеется путь из 1 sj длины т (/), где 1 < т(j) < 1(1). Отсюда по теореме 3.4 положительны все элементы первой строки матрицы M (w (x (j))) > 0, и, следовательно, все элементы первой строки матрицы, а а /(1) П

так как MW⁷*¹«! = % M (w (i)) > S M (w (x (j))).

i-1 M

П}^сть выполнены i-1 шагов построения, т. е. построено слово w (l (i — 1)) такое, что положительны все элементы первых i — 1 строк матрицы ММ*(^,_1))1, 1 < i < п.

i-й шаг. Обозначим через С__х путь длины 1(г — 1) с меткой w (l (i — 1)), начинающийся в г. Пусть конечная вершина п}^ти С'__х есть р е {1, …, гг}. Продолжим слово w (l (i — 1)) до слова w (l (i)). В ГО*) имеется полный путь Cj длины lj с началом в р, где /, < Х (п) — 1 [13, теорема 3]; метку пути С, обозначим W;. Построим начинающийся в i путь С' длины /(г) с помощью последовательного соединения путей С__х и С,-, где /(г) = /(/ - 1) + 1_Г и метка w (l (i)) пути С получена соединением меток путей С'__х и С: w (l (i)) = = w (l (i — 1 ))го_{. Тогда по построению в ТО*) имеется путь из i в j длины 0(/), где /(/ - 1) < 0(/) < /(/), отсюда по теореме 3.4 Tnjj (w (Q (j))) > 0 при j = 1,…, гг.

Отсюда положительны все элементы i-й строки матрицы ^ M (zv (Q (j)))

;=1.

— а КО

и, следовательно, матрицы М№(КО)]_у так как М№(КО)] = ?М (ге>(5)) >

5=1.

>?мокеО))).

>1.

В силу предположения индукции также положительны все элементы первых i — 1 строк матрицы Ml^w(KO) так как Ml^w(KO) > 1))]. Значит, положительны первые г строк матрицы М^^(/(/))1, т. е. искомое слово w есть w (l (n)). Поскольку /(/) = l (i — 1) + /, где по теореме 3 1581 /(1) < (п) и /, < < Х (п)~ 1, г > 1, то/(гг) = /(1) + /₂ + … +/_и < тгЛ (гг) -/г + 1 = (п²-2)(п- 1)/2. ?

• [1] Князев А. В. О диаметрах дихотомических графов // Математические заметки. 1991.Т. 50. № 1.
• [2] Князев А. В. О диаметрах дихотомических графов // Математические заметки. 1991.Т. 50. № 1.