Sufficient conditions for local primitiveness of nonprimitive digraphs.pdf Введение Для объектов некоторых коммуникационных систем, моделируемых неотрицательными матрицами (орграфами), некоторые важные свойства достигаются, если положительны их подматрицы (подграфы являются полными). В связи с этим в [1] известные понятия примитивности и экспонента матрицы (орграфа) обобщены до понятий локальной примитивности и локальных экспонентов матрицы (орграфа). Обозначим = {1,... , n}, где n - натуральное число; I = {i*,... , ik}, J = {j*, ... , jr}, 0 = I С Nn, 0 = J С Nn. Пусть Г есть n-вершинный орграф, A - матрица смежности вершин графа Г, A(I х J) -её подматрица размера k х r, 0 < k,r ^ n, полученная из A вычёркиванием строк с номерами i Е I и столбцов с номерами j Е J. Матрица A называется I х J-примитивной (i х j-примитивной при I = {i}, J = = {j}), если существует натуральное число y, такое, что матрица A*(I х J) положительна при любом t ^ y. Наименьшее такое число 7 называется I х J-экспонентом (i х j-экспонентом при I = {i}, J = {j}) матрицы A, обозначается I х J-exp A (i х j- exp A). Орграф Г называется I х J-примитивным, если и только если матрица A является I х J-примитивной, при этом соответствующие I х J-экспоненты матрицы A и графа Г равны. Некоторые условия I х J-примитивности матриц (орграфов) получены в [1]. В работе развиваются и обобщаются результаты работы [1]. Приведены условия I х J-примитивности матрицы (орграфа), не обязательно являющейся примитивной. 1. Достаточные условия I х J-примитивности орграфов Используем определения и обозначения работы [1]. Путь в Г из i в j, проходящий через некоторые вершины множества Y, назовем Y-путём из i в j. Сильносвязный подграф U (множество его вершин обозначается U) орграфа Г назовём i, j-связывающим, если в Г существует U-путь из i в j .В частности, сильносвязный орграф есть i, j-связывающий орграф при любых i, j. Связный циклический орграф Г является I х J-примитивным, если и только если он i х j-примитивный для любой пары вершин (i, j) G I х J, при этом I х J- exp Г = = max i х j - exp Г [1], то есть достаточно получить условия i х j-примитивности для (i,j)e/xJ связного циклического орграфа Г. При натуральном d множество натуральных чисел называется d-полным, если оно содержит полную систему вычетов по модулю d. Для d-полного множества M обозначим через q(M) такое наименьшее натуральное число, что для любого a G {q(M), q(M) + 1,..., q(M) + d - 1} в M имеется число b, не превышающее а и b = а (mod d). В силу d-полноты множества M число q(M) существует и не превышает max M. Обозначим L(i, j) множество длин всех простых путей из i в j. Сумму R + R' множеств натуральных чисел R = {r1,r2,... } и R' = {r', r2,... } определим как {ri + rj : i, j = 1, 2,...}. Теорема 1. Пусть в связном орграфе Г имеется i, j-связывающий цикл C длины l и множество Mi,j = (J {L(i,^) + v) + L(v, j)} является l-полным. Тогда граф Г ее является i х j-примитивным и i х j - exp Г ^ q(Mi,j). Пример 1. В 5-вершинном орграфе Г1 (рис.1) имеется 1,5-связывающий цикл C = (2, 3, 4) длины l = 3. Покажем 1 х 5-примитивность орграфа Г1. Рис. 1. Граф Г1 Пусть ^ = v = 3, тогда L(1, 3) = {1, 2} = L(3, 5), v) = {0}, следовательно, L(1, 3) + L(3, 3) + L(3, 5) = {2, 3, 4} С M15. Тогда M15 есть 3-полное множество, где q(M1,5) = 2. Условия теоремы 1 выполнены, следовательно, граф Г1 является 1 х 5-примитив-ным и 1 х 5- exp Г ^ 2. Заметим, что 1 х 5- exp Г = 2, так как длина кратчайшего пути из 1 в 5 равна 2. Теорема 2. Пусть в связном орграфе Г имеются i, j-связывающие циклы C1, _ k ... ,Ck длины l, где k ^ 1, и множество Mi,j = (J (J {L(i,^r) + , vr) + L(vr, j)} r=1 ^r,vr ecr является l-полным. Тогда граф Г является i х j-примитивным и i х j - exp Г ^ q(Mi,j). Пример 2. В 8-вершинном орграфе Г2 (рис.2) имеются два 1,8-связывающих цикла длины l = 3: C1 = (2, 3, 4), C2 = (5, 6, 7). Покажем 1 х 8-примитивность орграфа Г2. Рис. 2. Граф Г2 Пусть = 2, V1 = 3, ^2 = V2 = 6, тогда L(1, 2) = {1}, L(3,8) = {1, 2}, L(2, 3) = {1}, L(1,6) = {1}, L(6, 8) = {1}, L(6, 6) = {0}. Отсюда {L(1, 2) + L(2, 3) + L(3, 8)} U {L(1, 6) + L(6, 6) + L(6, 8)} = {3, 4} U {2} = {2, 3,4}, следовательно, M1,g есть 3-полное множество, где q(M1,g) = 2. Условия теоремы 2 выполнены, следовательно, орграф Г2 является 1 х 8-прими-тивным и 1 х 8- ехрГ ^ 2. Заметим, что 1 х 8- ехрГ = 2, так как длина кратчайшего пути из 1 в 8 равна 2.

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