Улучшенная формула универсальной оценки экспонента орграфа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/5

Улучшенная формула универсальной оценки экспонента орграфа

Улучшена формула универсальной оценки экспонента n-вершинного примитивного орграфа, данная А. Далмэджем и Н. Мендельсоном (1964) с использованием множества контуров, длины которых взаимно простые. Предложенная формула использует в орграфе множество контуров С с множеством длин L(C) = = {I1,... ,lm}, где d = (I1,... ,lm) ^ 1, и множество длин кратчайших путей : s = 0,..., d-1} из вершины i в вершину j, проходящих через множество контуров С и образующих полную систему вычетов по модулю d. Показано, что exp Г < 1 + F (L(C)) + R(C), где F(L) = d · F (h/d,..., lm/d); F (a1,...,am) -число Фробениуса; R(C) = max max{rsjd(C)}. Указан класс орграфов с множеством (i,j) s вершин {0,..., 2k - 1}, k > 2, для которых предложенные оценки экспонентов лучше известных на величину k - 2.

An improved formula for the universal estimation of digraph exponents.pdf Введение Обозначим: Zn = {0, ...,n - 1} - кольцо вычетов по модулю n, n £ N; M01 - множество 0,1-матриц порядка n; exp Г - экспонент орграфа Г. Рассмотрим неотрицательную матрицу M (все её элементы суть неотрицательные действительные числа), свойство неотрицательности записывают так: M ^ 0. Матрицу M, все элементы которой положительные, называют положительной (M > 0). Для квадратной неотрицательной матрицы M в [1] был поставлен вопрос: имеются ли положительные матрицы в ряду {Mi : i = 1, 2,...}? То есть содержит ли циклическая полугруппа (M) положительные матрицы? Если содержит, то матрицу M называют примитивной, в противном случае - непримитивной. Наименьшее натуральное y, при котором M7 > 0, называется экспонентом матрицы M, обозначается exp M. Если матрица M непримитивная, то положим exp M = то. В случае примитивной матрицы M1+i > 0 при любом i £ N. Мультипликативная полугруппа всех неотрицательных матриц гомоморфно отображается на полугруппу всех 0,1-матриц (все элементы суть целые числа 0 или 1) с помощью замены каждого положительного элемента единицей. Этот эпиморфизм согласован со свойством примитивности: прообразом любой примитивной (непримитивной) 0,1-матрицы является класс, состоящий только из примитивных (непримитивных) матриц. Данное свойство позволяет ограничиться исследованием мультипликативных моноидов Mn'1, n £ N, где умножение выполняется как обычное умножение целочисленных матриц с последующей заменой положительных элементов единицами. Множество матриц смежности вершин n-вершинных ориентированных графов с петлями совпадает с Mn'1, и на орграфы распространены понятия примитивности и экспонента, где умножение орграфов определено как умножение бинарных отношений. Заметим, что примитивный граф является сильносвязным. Далее обозначаем через M матрицу смежности вершин орграфа Г с множеством вершин Zn. Связь между графами и неотрицательными матрицами устанавливает общеизвестная теорема теории графов (назовём её основной теоремой): число путей длины t из i в j в графе Г равно mfj, i, j £ {1,..., n}, где M* = (mj. Таким образом, примитивность орграфа и величина экспонента определяется свойствами путей в графе, в частности M > 0, если и только если орграф Г полный. Утверждения о примитивности и об экспонентах равносильно формулируются и на матричном, и на графовом языке. Известные оценки экспонентов матриц и орграфов можно разделить на универсальные и специальные (для частных классов). Работа посвящена улучшению универсальной оценки экспонента примитивного орграфа. 1. Известные универсальные оценки экспонентов Основополагающие результаты получены в середине XX в. авторами [2-4], предложившими термин «экспонент». Обозначим: C = {C1,... , Cm} -множество контуров длин /1,... , lm соответственно, L(C) = {l1,... , lm}. Индексом множества контуров C (обозначается ind C) назовём число d = НОД( L((7)). Критерий примитивности орграфа Г [3] определяется множеством его контуров: сильносвязный орграф Г примитивный, если и только если содержит множество контуров индекса 1 . Универсальная оценка экспонента примитивного орграфа дана Виландтом [2] в 1950 г.: exp Г ^ n2 - 2n + 2. (1) Доказательство оценки (1) представлено в [3, 5]. При n > 1 описаны n-вершинные орграфы [4, 6] (названные в [6] в честь Виландта), на которых достигается оценка (1). Эти орграфы изоморфны, имеют n +1 дугу и содержат ровно два простых контура длин n и n - 1. В [4] уточнена оценка (1) при известной длине l контура в орграфе: ехрГ ^ n + l(n - 2). Для более точных оценок введём определения. Говорят, что «путь проходит через контур», если у пути и контура есть общая вершина. Путь проходит через множество контуров, если он проходит через каждый контур множества. В орграфе Г обозначим: C - множество всех простых контуров; Cd - класс всех множеств простых контуров индекса d; r^j (С) -длина кратчайшего пути из i в j, проходящего через множество контуров C; r(C) = max ri,j ((C). Оценочная формула Далмэджа и Мендельсона [4] определяется неравенством exp Г ^ 1 + F(L(C0) + r(C'), (2) где C - любое множество контуров индекса 1; F - число Фробениуса. Уточним (2): ехр Г ^ 1 + min{ F (£((?)) + r(C0) . (3) ceci L J Для получения из (2) числовых оценок экспонента достаточно определить число Фробениуса F(L((7)) [7, 8] и величину r((7). С помощью оценки величины r((7) [9, ч. 1, с. 185] получено ехрГ ^ n(m + 1) + F(£((?)) - li - ... - lm. (4) Учёт структуры множества C улучшает оценку (4) [10, с. 80]. Обозначим Г(С) = = Ci U... U Cm - часть орграфа Г, где li ^ ... ^ lm. Если орграф Г((7) сильносвязный, то он содержит контур K, проходящий через множество контуров C и проходящий через каждую дугу столько раз, сколько контуров множества (7 содержат эту дугу. Контур K в общем случае определён неоднозначно и называется квазиэйлеровым С-контуром, его длина len K = li + ... + lm. Если Г(С) имеет компоненты связности Ci,... , Cr , 1 ^ r ^ m, содержащие независимые квазиэйлеровы контуры Ki,... , Kr длин ... соответственно, то, полагая без ущерба для общности ^ ... ^ , получаем оценку ехр Г ^ n(r + 1) + F (L((7)) - £ (lj + (j - 1)^-). (5) v / j=i В частности, если орграф Г((7) связный, то ехр Г ^ 2n - li + F . Оценка (5) следует из (2) и из оценки величины r(C) для примитивных орграфов. 2. Улучшение универсальной оценки экспонента орграфа Для усиления формулы (3) используем понятие локального экспонента орграфа [11]. Орграф Г называют (i,j)-примитивным, i,j Е Zn, если при некотором Y Е N для любого t ^ y в орграфе Г имеется путь длины t из вершины i в вершину j. Наименьшее такое y называется (i, j)-экспонентом орграфа Г и обозначается (i, j)-exp Г. Примитивный орграф Г является (i, j)-примитивным для любых i, j G Zn и exp Г= max (i,j)-exp Г. O^i , j^n-1 Обозначим: F(L) = d • F(h/d,... , /m/d), где L = {/1,... , /m}, d = НОД(Ь) (F(L) = = F(L) при d = 1); rs/jd(((7) - длина кратчайшего пути w из i в j, проходящего через множество контуров C, сравнимая с s mod d, s = 0,... , d - 1 (такие пути в Г есть); R j (CO = max i jCT),... , rj 1/d((7H; R((7) = max R j ((7). Заметим, что ri j ((7) = = min jr°jd((7),... , rdj 1/d((7)|, если (C - множество контуров индекса 1. Теорема 1. Для любого непустого множества контуров (7 индекса более 1 (i, j)-exp Г ^ 1 + F (l(C0) + Rij((7), exp Г ^ 1 + F (l((7)) + R((7). (6) Следствие 1. Для любого примитивного орграфа Г exp Г ^ 1+ min {F (l((7)) + . (7) ccc , (5=0 IV/ J Замечание 1. Уточнение (по сравнению с (3)) оценки экспонента с помощью формулы (7) возможно только при оценке (6) для множества (7 индекса больше 1. Найден класс орграфов, для которого формула (6) дает оценки существенно лучше, чем (3). Теорема 2. Пусть множество вершин орграфа Г есть Z2k, k > 1, множество дуг содержит дуги контуров C0 = (k - 1, 2k - 1), C1 = (0,..., k - 2, 2k - 1), C2 = (k - 1, ... , 2k - 2), и ещё дуги (k - 2, k - 1) и (2k - 2, 2k - 1) (рис. 1). Тогда для орграфа Г: - оценка (3) принимает значение 3k - 2 при чётных k и 3k - 3 при нечётных k; - оценка (6) принимает значение 2k при чётных k и 2k - 1 при нечётных k. Множество простых контуров орграфа Г есть C = {C0, C1, C2, C3, C4, C5}, где C3 = = (0,... , k - 1, 2k - 1), C4 = (k - 1,..., 2k - 2, 2k - 1) и C5 есть гамильтонов контур (0,1,... , 2k - 1). Множество длин всех простых контуров есть L(C) = {2, k, k + 1, 2k}, ind C = 1. Пусть (7 С C. При нечётном k ind (7 = 1, если и только если 2, k G L((7) или k, k + 1 G L(C). Класс C1 состоит из 42 множеств (при чётном k также). В данном орграфе величина F(L((7)) + r((7) принимает наименьшее значение при (7 = C. Обозначим через p(i, j) длину кратчайшего пути из i в j, тогда max p(i, j) = O^i , j^2k-1 = p(0, 2k - 2) = p(k, k - 2) = 2k - 2. Кратчайшие пути w = (0,..., 2k - 2) и W = = (k, . . . , k - 2) суть части гамильтонова контура и проходят через вершины k - 1 и 2k - 1 соответственно. Значит, через любое множество контуров индекса 1 проходит либо w, либо w'. Отсюда r((7) = 2k - 2 для любого (7 G Ci. Заметим: F(L) ^ F(L') при НОД(Ь') = НОД(Ь) = 1, если L' С L. Отсюда F(L((7)) ^ F(L(C)) = F(2 , k, k + 1, 2k) для любого множества (7 индекса 1. Отсюда получаем нужные значения оценки (3), так как F(L(C)) = F(2, k) = k - 2 при нечётных k и F(L(C)) = F(2, k + 1) = k - 1 при чётных k. Получим оценку (6) для контура C0 длины 2. При нечётных k: R(C0) = = R2fc-i,2fc-2(Co) = 2k. При чётных k: R(Co) = R2fc-i,2fc-2(Co) = max{len w, len w'} = = 2k + 1. В обоих случаях имеем нужные значения оценки (6), так как -F(Co) = -F(2) = = -2. В таблице приведены экспоненты орграфов (теорема 2) и их оценки (3), (6) при k = 2,..., 7. Число вершин орграфа 2k Оценка (3) exp Г Оценка (6) exp Г для контура C0 exp Г 4 4 4 4 6 6 5 5 8 10 8 8 10 12 9 9 12 16 12 11 14 18 13 13

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

exponent of graph, primitive graph, Frobenius number, экспонент орграфа, примитивный орграф, число Фробениуса

Авторы

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

Ссылки

Фомичев В. М. Новая универсальная оценка экспонентов графов // Прикладная дискретная математика. 2016. №3(33). С. 78-84.
Фомичев В. М., Кяжин С. Н. Локальная примитивность матриц и графов // Дискретный анализ и исследование операций. 2017. Т. 24. №1. С. 97-119.
Alfonsin J. R. The Diophantine Frobenius Problem. Oxford University Press, 2005.
Фомичев В. М., Мельников Д. А. Криптографические методы защиты информации. В 2 ч. Ч. 1. Математические аспекты. М.: Юрайт, 2016. 209c.
Фомичев В. М. О вычислительной сложности оригинальной и расширенной диофантовой проблемы Фробениуса // Дискретный анализ и исследование операций. 2017. T.24. №3. С. 104-124.
Holladay J. C. and Varga R. S. On powers of non-negative matrices // Proc. Amer. Math. Soc. 1958. V.IX. P. 631.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Perkins P. A theorem on regular graphs // Pacific J. Math. 1961. V. II. P. 1529-1533.
Dulmage A. L. and Mendelsohn N. S. Gaps in the exponent set of primitive matrices // Illinoise J. Math. 1958. No. 86. P. 642-656.
Frobenius G. Uber Matrizen aus nicht negativen Elementen // K. Preuss. Akad. Wiss. Berlin. 1912. S.456-477.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. N.52. S. 642-648.
 Улучшенная формула универсальной оценки экспонента орграфа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/5

Улучшенная формула универсальной оценки экспонента орграфа | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/5