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

Матрицу М порядка п > 1 над {0, 1} называют примитивной, если М > 0 при некотором t е N, а наименьшее у е N, при котором М' 0 называется экспонентом или показателем примитивности матрицы А, обозначается ехрМ. Неотрицательную матрицу М назовем субпримитивной, если.

M^x* 1 > 0 при некотором t е N, где М¹^ — М + М² + … + М'. Субэкспонентом матрицы М, обозначается sbxpM, называют наименьшее о е N, при котором Ml '-^с1 > 0. Отсюда sbxpM < ехрМ. Если матрица М не примитивна (не субпримитивна), то expМ = °° (sbxpM = оо). Если матрица М примитивная, то и любая ее степень примитивная.

Моноид образует решетку в смысле частичного порядка: если А = (ау), В = (bjj), то А < В а_ц < b_tJ для любых допустимых пар (i, j). Положим А < В, если А< В и Аф В.

Утверждение 11.1. Пусть А, А В, В' е ^у?_п и А < В, А' < В', тогда.

• а) А + А' < В + В, АА' < ВВ А¹ < В¹ при любом t е N;
• б) множество примитивных (субпримитивных) матриц образует в верхнюю полурешетку, ехрЛ есть антимонотонная функция, определенная на данной полурешетке.

А Отношение А< В равносильно тому, что В = А + С, где С е Ч^/". Отсюда и из правил умножения и сложения матриц получаем утверждение. ?

Далее Г — сильно связный и-вершинный орграф с матрицей смежности вершин М. Орграф Г примитивный матрица М примитивная, ехрМ = ехрГ. В соответствии с теоремой 3.2 граф Г примитивный, если при некотором t е N для любых i, j е N_n в Г имеется путь длины t из i в j, наименьшее такое t равно ехрГ. Субпримитивность матрицы М (графа Г) тождественна сильной связности графа Г, sbxpM = сПашГ.

Обозначим: g (a_b …, a_k) — число Фробениуса для аргументов а_х,…, а_к е е N, где НОД{а₁,…, а_к} = 1, т. е. g (a_x,…, a_k) — наибольшее натуральное число, не входящее в аддитивную полугруппу (а_ь …, а_к), порожденную числами …, a_k, g(й|,…, ад) — g (a|,…, а^) — а_х — … — а_к, k > 1.

Теорема 11.3 (критерий примитивности и универсальная оценка экспонента орграфа).

Сильно связный орграф Г примитивный о Г содержит систему т простых контуров длины /j,…, /," соответственно, где т > 1 и IЮД{/|,…, /,"} = 1. Если Г примитивный, то.

А Для контура С орграфа Г, проходящего через вершину а, обозначим kC{a) контур в Г, соответствующий^{-кратному} проходу контура С из вершины а, где k е N₀, kC (a) — пустой путь при к = 0.

Для любой вершины b обозначим s (b, а_г) — кратчайший путь из b до ближайшей вершины а_г простого контура С,., г = 1, …, т, s (b, j) — кратчайший путь из b до j. Тогда lens (/>, а,) < п — len. v (/;,/) < п — 1. Для любых вершин i, j построим путь z (i, j) из i в j с помощью конкатенации: z (z, j) = = s (i, «,) •^, С₁(й₁) • 5(й» й₂) • k₂C₂(a₂) • s (flj, й₂) • … • k_mC_m(a_m) • s (a,",;'). Отсюда lenz (z, y) = ^ + Х₂, где А, = lens (/, а_х) + lens (fl₍, й₂) +… + lens (a_m_j, а_т) + + len. v (a_m, y), Х₂ = k_xl_x +… + k_ml_m. Следовательно, _х < п (т + 1) — 1_Х -… — l_m — 1, величина Х₂ в зависимости от набора коэффициентов k_x,…, k_m принимает любое значение, превышающее число Фробениуса g (l_x, …, /,"). Значит, для любых i, j и любого t > п{т + 1) + g (l_x, …, /,") в Г есть путь длины ?, т. е. оценка экспонента верна.

Обратно, пусть Г примитивный и НОД^, l_m) = d. Тогда орграф Г является d-дольным по теореме 3.5, обозначим К₀, …, V_(J__X доли, на которые разбивается множество вершин. Для любых вершин i, j положим, нс теряя общности, что i е V₀, j е V_r 0 < г < d. В соответствии с определением fi-дольного графа len z (i, j) = r (modd) для любого пути z (t, j) из i в j, что при d > 1 противоречит примитивности орграфа Г. ?

Следствие. При п > 1 неориентированный граф Г примитивный содержит простой контур нечетной длины.

Ч Следует из теоремы 11.3, так как ребро в Г есть контур длины 2. ?

А В графе систему простых контуров С = {С_ь …, С_т} с длинами 1_и …, 1_т соответственно назовем примитивной, если НОД^, …, l_m) = 1. Далее счи;

А таем 1_Х < … < 1_т. Систему С назовем минимальной примитивной, если любая ее собственная подсистема не является примитивной. Система С минимальная примитивная /_у 6 (1р …, lj_y) при j = 2,…, т [14].

Любая примитивная система контуров может быть использована для получения оценки экспонента графа в соответствии с теоремой 11.3. Наименьшее значение оценки достигается при одной из минимальных примитивных систем.

Обозначим pi простое число с номером i (числа берутся в порядке возрастания), i = 1, 2,…, т. е. р_х = 2, р₂ = 3 и т. д.

Теорема 11.4. В /7-вершиниом орграфе Г при п> 2 любая минимальная примитивная система имеет не более т простых контуров, где in — наибольший номер, при котором р₂-Р_т ^ я;

Л Наибольшее значение т достигается при наименьших взаимно простых длинах контуров /_t,…, 1_т, где 1_т < п. В соответствии с [ 71 наименьшие взаимно простые числа суть /, = Р.~Р_т / p_v i = 1, ш. Тогда 1_т = р₂.-Р_т ^ < п. ?

В табл. 11.1 приведены значения т для некоторых интервалов значений п.

Таблица 11.1

Число простых контуров в минимальной примитивной системе и-вершинного орграфа.

Поскольку т < llnwl — 1 при п > 1115, то из табл. 11.1 и теоремы 11.3 следуют оценки.

Следствие. Если Г примитивный, то.

В соответствии с теоремой 11.3 сильно связный граф Г с петлей является примитивным. Оценим его экспонент. Обозначим: А (Г) — множество вершин орграфа Г с петлями; d_t ,• — длина кратчайшего пути из i в ] (ИатГ = тах{г/,_;, ij = 1,п} — диаметр графа Г; е (г) = таx{d, j_yj = 1,п) — эксцентриситет вершины г; p (j) = таx{d_itp i = 1, п) — периферийность вершины j; d_{f г}? — длина кратчайшего пути в Г из i в j_y проходящего через вершину г, diam’T = таx{d_{i r}j_y i_yj = 1, п) — г-диаметр графа Г. Заметим, что (ПатГ < diam’T при любом г е А (Г); для неориентированного графа e (i)=p (i), i = 1,п.

Теорема 11.5 113]. Для примитивного орграфа Г с петлями верны оценки:

• а) diam’T <р (г) + е (г) <2п — 2 при любом ге А (Г);
• б) ехрГ < min dianVT <2п-2.

геЛ (Г).

А а) по определению diam’T < max{^ _r + d_{r j}, i, j = 1, /?}, где d_{t r} < p{r) <

< n — 1, d_rj < e (f) < n — 1. Значит, diam’T < p® + e® <2n-2 при любом г e e А (Г) и n > 2;

6) если орграф Г имеет петлю в вершине г, то с учетом возможности кратного прохождения данной петли, для любых i, j е {1,п) имеется путь из i в j длины t при любом t > diam’T. Следовательно, ехрГ < min diam’T ?

/еА (Г) Теорема 11.6. Если примитивный граф Г имеет контур длины /, то ехрГ<�п + 1{п — 2).

М Граф Р примитивный и имеет не менее / петель. В Р имеется путь длины /?-1 из любой вершины гс петлей в любую вершину j. Тогда в Г имеется путь длины 1(п — 1) из любой вершины г контура длины / в любую вершину j. Кроме того, в Г имеется путь длины п — I из любой вершины i в некоторую вершину контура длины /. Значит, для любых i, j в Г имеется путь из z в j длины t = п — I + 1(п — 1), т. е. оценка экспонента верна. ?

Следствие (универсальная оценка Виландта^[1]). ехрГ < п^[2] -2/7 + 2.

Ч В условиях теоремы 11.3 длина кратчайшего контура I <�п — 1, тогда оценка следует из теоремы 11.6. ?

Оценка теоремы 11.6 может быть понижена, если в Г известны длины двух контуров.

Теорема 11.7 [12]. Пусть п > 2, С и С' суть простые контуры в Г длины / и X соответственно, h — число общих вершин контуров, где (/, X) = 1, / > X. Тогда ехрГ < IX — 21-ЗХ + 3/7 при h = 0 и ехрГ < IX -1-ЗХ + h + 2п при h > 0. D>

Для различных частных классов орграфов получены условия примитивности и уточнение известных оценок экспонентов [5, 8, 11].

Матрица называется минимальной примитивной_у если она не примитивная при замене любой единицы нулем. Минимальные примитивные 0, 1-матрицы суть минимальные элементы верхней нолурешетки примитивных матриц. Такие матрицы важны с точки зрения экономной реализации. При п > 4 все примитивные орграфы с числом дуг /7+1 являются минимальными^[2], имеются минимальные примитивные орграфы с числом дуг от /7 + 2 до 2/7 — 3. Описаны минимальные примитивные орграфы с числом дуг п + 1 и п + 2.

• [1] Wielandt Н. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642— 648.
• [2] Фомичёв В. M. Свойства минимальных примитивных орграфов. Томский гос. ун-т.Прикладная дискретная математика. 2015. № 2 (28). С. 86—96.
• [3] Фомичёв В. M. Свойства минимальных примитивных орграфов. Томский гос. ун-т.Прикладная дискретная математика. 2015. № 2 (28). С. 86—96.