Новая универсальная оценка экспонентов графов | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/6

Новая универсальная оценка экспонентов графов

Получена новая универсальная оценка экспонентов n-вершинных примитивных орграфов через характеристики содержащихся в орграфе контуров Ci,...,Ck длины l1,..., lk соответственно, где (l1,..., lk) = 1. Показано, что exp Г ^ n(r+1) + + g(l1,...,lk) + L, где r - число компонент связности орграфа C1 u ... u Ck; g(l1,...,lk) -число Фробениуса; L - линейная комбинация длин определённых контуров орграфа Г. Дано уточнение оценки для некоторых частных случаев. Приведены примеры оценок экспонентов орграфов. Полученная универсальная оценка для многих n-вершинных примитивных орграфов улучшает известные оценки. Порядок её величины варьируется от O(n) до O(n). Оценка принимает наибольшие значения порядка O(n), только если кратчайший контур примитивной системы имеет длину порядка O(n). На графах Виландта полученная оценка совпадает с оценкой Виландта.

The new universal estimation for exponents of graphs.pdf Введение Введём основные обозначения: - N - множество натуральных чисел, N0 = N U {0}; - (/, Л) -наибольший общий делитель натуральных чисел /, Л; - (Z!,..., Ik) - аддитивная полугруппа, порождённая множеством натуральных чисел ... , /fc; - g(/i,... , /k) -число Фробениуса для натуральных аргументов /1,... , /k; - V(С) - множество вершин системы контуров (7 в графе; - w(a, b) -путь из вершины a в вершину b в графе; - w • w' - конкатенация путей w и w', где совпадают последняя вершина пути w и первая вершина пути w'; - len w - длина пути w в графе. В соответствии с известным критерием сильносвязный граф является примитивным тогда и только тогда, когда содержит систему контуров, имеющих взаимно простые длины. Абсолютная оценка экспонента [1] примитивного n-вершинного орграфа Г использует только число вершин: exp Г ^ n10 - 2n + 2. (1) Так как в примитивном графе имеются контуры, универсальной можно считать также следующую оценку [2, с. 227]: если в Г имеется контур длины /, то exp Г ^ n + /(n - 2). (2) Последующие результаты уточняли универсальные оценки экспонента с учётом длин имеющихся в орграфе контуров. Если, в частности, в орграфе Г имеется d петель [2, с. 408], то exp Г ^ 2n - d - 1. Если в орграфе Г известны длины / и Л двух простых контуров C и Z [3, с. 408], где (/, Л) = 1, 1 2 и h - число общих вершин контуров C и Z, то exp Г ^ /Л-2/ - 3A+3n при h = 0 и exp Г ^ /Л - / - 3A+h+2n при h > 0. Список уточнений имеет продолжение [4]. Данная работа посвящена получению новой универсальной оценки экспонентов n-вершинных примитивных орграфов. Оценка использует длины ряда контуров, содержащихся в примитивном орграфе. Полученная универсальная оценка по сравнению с оценками (1) и (2) использует больше информации о графе и, как правило, улучшает их. 1. Универсальная оценка экспонента с использованием длин контуров графа Обозначим: (7 = {С1,... , Ck} - система контуров в орграфе Г длин /1,... , /k соответственно, k Е N; Г((7) = С1 U ... U Ck - часть орграфа Г. Систему (7 назовём примитивной, если (/1,... , /k) = 1. Систему контуров (7 назовём связной, если граф Г((7) связный. В орграфе Г контуры ( и С назовём смежными (записываем ( ~ С), если они имеют общую вершину. Лемма 1. Если ( - связная система контуров орграфа Г, то в орграфе Г((7) имеется контур, обходящий однократно каждый контур системы (7. Доказательство2. Индукция по числу контуров связной системы. При k = 1 утверждение тривиально. Если при k = 2 контуры ( и (2 длин /1 и /2 смежные и i - их общая вершина, то искомый контур ( есть (1(i) • (2(i). Пусть k ^ 2 и лемма выполнена для любой связной системы менее k контуров. По условию контур Ci смежный с другим контуром системы (пусть C\ ~ C2). Тогда либо C1, либо C2 является смежным с некоторым из остальных контуров системы (пусть это C3). Следовательно, система контуров |C1,C2,C3} является связной. Рассуждая аналогично, построим связную систему контуров {C1,... , Ck-1}. По предположению индукции в Г(С) существует контур C', однократно обходящий каждый из контуров C1,... , Ck-1. По условию контур Ck смежный с некоторым из контуров C1,... , Ck-1, значит, Ck ~ C и по предположению индукции в Г(С) существует контур C, обходящий однократно контуры C и Ck. ■ Контур Z, обходящий однократно каждый контур связной системы C, назовём квазиэйлеровым C-контуром, при этом len Z = /1 + ... + Ik в силу леммы 1. Следствие 1. В орграфе Г((7) множеству {C1,... , Cr} компонент связности соответствует множество {Z1,...,Zr} (в общем случае не единственное) независимых контуров, 1 ^ r ^ k, где Zj - квазиэйлеров Cj-контур, j = 1,... ,r. Доказательство. Следует из леммы 1 и свойств разбиений множеств. ■ Пусть далее /1 ^ ... ^ lk, А1 ^ ... ^ Ar, где A j = len Zj, j = 1,...,r. При (/1,..., lk) = 1 обозначим g(l1,..., lk) число Фробениуса (наибольшее число, не принадлежащее полугруппе (l1,... , lk) при k > 1; g(1) = -1). Теорема 1. Пусть n-вершинный орграф Г содержит примитивную систему контуров C = {C1,... , Ck} длин l1,... , lk соответственно и компонента связности Cj орграфа Г(С) содержит квазиэйлеров Cj-контур Zj длины Aj, j = 1,..., r. Тогда exp Г ^ n(r + 1)+ g(l1,..., lk) - E (lj + (j - 1)Aj). J=1 Доказательство. Для вершин a, b орграфа Г обозначим: w(a, aj) - кратчайший путь из a до ближайшей вершины aj контура Zj ; w(aj, b) - кратчайший путь из aj до b, j = 1,..., r; mC(i) - контур, полученный при m-кратном проходе контура C из вершины i, где m ^ 0; 0C(i) -пустой контур. Без ограничения общности положим, что контур Zj содержит вершины контуров Ctj_1+1,... , Ctj, и только этих контуров, где 0 = t0 < ... < tr = k и len Zj = Aj = = ltj-1+1 + ... + ltj в силу леммы 1, j = 1,... , r. Перенумеруем все вершины контура Zj числами от 1 до Aj , где нумерация начинается с вершины aj, и обозначим: 1) путь w(t, 0) = (т, т + 1,... , 0) при т ^ 0, путь w(t, 0) пустой при т = 0; 2) - наименьший номер вершины, принадлежащей контуру Ci, i = tj-1 + 1,... , tj; 3) vj = max{^tj_i+1,...,Ctj}. Так как ltj-1+1 ^ ... ^ ltj, то vj ^ Aj - ltj-1+1 + 1. Положив для определённости Ctj-1+1 ^ ... ^ Ctj (в общем случае не исключено любое упорядочение этих номеров), определим путь w(Zj) при неотрицательных целых числах mtj,... ,mtj-1+1: w(ZJ) = w(1,ftj) ■ mj cj (Ctj ) ■ ... ■ w(CtJ-1+2,CtJ-1+1) ■ mtJ-1+1CtJ-1+1(CtJ-1 + 1). Отсюда при любом порядке указанных номеров для длины пути w(Zj) выполнено len w(Zj) = len w(1,Ctj ) + ... + len w(Ctj-1+2 ,Ctj-1+1)+ (3) + mtj ltj + ... + mtj_1+1ltj_1+1 = vj - 1 + Sj, где vj - 1 ^ Aj - ltj_1+1; Sj = mtj ltj + ... + mtj_1+1ltj_1+1. Построим путь w(a, b) в Г для любых вершин a, b: w(a, b) = w(a0, a1) ■ w(Z1) ■ w(a1, a2) ■ w(Z2) ■ ... ■ w(ar-1, ar) ■ w(Zr) ■ w(ar, b). Здесь a0 = a; w(aj,aj+1) -кратчайший путь из вершины aj до ближайшей вершины aj+1 графа Ctj+1 U ... U Ck, j = 0,... ,r - 1; w(ar,b) - кратчайший путь из ar до вершины b. Заметим, что lenw(ar,b) ^ n - 1, и с учётом разбиения графа Г(С) на компоненты связности len w(aj ,aj+1) ^ n - (Л3+1 + ... + Лг ), j = 0,... ,r - 1. Тогда при Л1 ^ ... ^ Лг получаем rr lenw(a,b) ^ n(r + 1) - Е jЛj - 1 + Е lenw(Zj). j=1 j=1 Из равенств (3) для j = 1,... ,r следует, что при l1 ^ ... ^ lk Е len w(Zj ) = Е (Лз - lj) + Е Sj, j=1 j=1 j=1 rk где Y] Sj = E mili с учётом разбиения графа Г(С) на компоненты связности. В си-j=1 i=1 k лу примитивности системы контуров C сумма £ mi li в зависимости от набора неотi=1 рицательных целых коэффициентов m1 ,...,mk принимает любое значение, большее r g(l1,..., lk). Следовательно, len w(a, b) ^ n(r + 1) + g(l1,... ,lk) - E (lj + (j - 1)Л3-). ■ j=1 Следствие 2. Если примитивная система контуров C является связной, то exp Г ^ 2n - l1 + g(l1,... ,lk). Доказательство. В оценке теоремы 1 следует положить r = 1. ■ Следствие 3. Если в условиях теоремы 1 |V((7)| = n, то exp Г ^ nr + g(h,... ,lk) - Е (3 + (j - 2)Л3). j=1 Доказательство. Если IV(C) = n, то n = Л1 +... + Лг и вершина a принадлежит компоненте связности орграфа Г(£7). Значит, lenw(a,a1) = n - (Л1 + ... + Лг) = 0. Следовательно, оценку len w(a,b), приведённую в доказательстве теоремы 1, а также оценку экспонента орграфа Г в условиях следствия 3 можно уменьшить на величину n - (Л1 + ... + Лг). ■ Примитивную систему контуров C назовём минимальной, если любая её собственная подсистема не примитивная. Система C минимальная примитивная, если и только если lj ф (l1,..., lj-1) при j = 2,... ,k [5, с. 21]. Пример 1. Оценка экспонента перемешивающего орграфа регистра с одной обратной связью. Рассмотрим перемешивающий орграф Г преобразования автономного двоичного регистра левого сдвига длины 8 с функцией обратной связи f (x1,..., x8) = x1 ф ж3ж4жб. Зададим орграф Г списком дуг Er = {(i,i - 1) : i = 2,..., 8}U{(1, 8), (3, 8), (4, 8), (6,8)}. Следовательно, список всех простых контуров есть {( = (8, 7, 6, 5, 4, 3, 2,1), ( = = (8, 7, 6,5, 4, 3), ( = (8, 7, 6, 5, 4), ( = (8, 7, 6)}, длины контуров равны соответственно 8, 6, 5 и 3. В орграфе Г имеются примитивные системы контуров {(1, (2, (3, (4}, {(1, (2, (3}, {(1 ,(2,(4}, {(1,(3,(4}, {(1,(3}, {(1,(4}, {(2,(3} и {(3,(4}, все они являются связными. Минимальными являются системы контуров {(1,(3}, {( ,(4}, {(2,(3} и {(, (4}. Используя формулу числа Фробениуса для двух аргументов g(/1, /2) = /1/2 - /1 - /2, (4) получаем в соответствии со следствием 2, что оценка равна: 38 для системы {(1, (3}, 26 для системы {(1, (4}, 30 для системы {(2, (} и 20 для системы {(3, (4}. Наименьшая оценка экспонента достигается для системы контуров {(3, (4}: exp Г ^ 20. Заметим, что абсолютная оценка Виландта (1) принимает значение 50, оценка (2) принимает значение 26 при / = 3. Пример 2. Оценка экспонента перемешивающего орграфа регистра с двумя обратными связями. Рассмотрим перемешивающий орграф Г преобразования автономного двоичного регистра левого сдвига длины 8 с функциями обратной связи f8(x1,... , x8) = x1 ф и f3(x1,... , x8) = x1x4, которые определяют значения соответственно 8-й и 3-й координатных функций преобразования. Зададим орграф Г списком дуг Er = {(i, i - 1) : i = 2,... , 8} U {(1, 8), (5, 8), (1, 3)}. Тогда список всех простых контуров есть {( = (8, 7, 6, 5, 4, 3, 2,1), ( = (8, 7, 6, 5), (3 = (3, 2, 1)}, длины контуров равны соответственно 8, 4 и 3. В орграфе Г имеются примитивные системы контуров {(1,(2,(3}, {( ,(3} и {(, (3}. Системы {(1, (2, (3} и {(1, (3} являются связными, система {(2, (3} несвязная. Минимальными являются системы контуров {(1,(3} и {(2,(3}. Используя формулу (4), получаем в соответствии со следствием 2, что оценка равна 26 для связной системы {(1,(3} и 19 для несвязной системы {(2, (3}, во втором случае в оценке теоремы 1 следует положить r = 2, /1 = Л2 = 3, /2 = 4. Наименьшая оценка экспонента достигается для системы контуров {(2,(3}: exp Г ^ 19. Оценки (1) и (2) принимают те же значения, что и в примере 1. Пример 3. Сравнение полученной оценки с оценкой Виландта в случае n-вер-шинного графа Виландта. В n-вершинном графе Виландта имеется связная система двух контуров длины n - 1 и n. Тогда в соответствии со следствием 2 exp Г ^ 2n - (n - 1) + g(n, n - 1) = n2 - 2n + 2, что совпадает с абсолютной оценкой Виландта. Оценим возможные значения величины k для минимальной примитивной системы. Обозначим простое число с номером i (числа берутся в порядке возрастания), i = 1, 2,..., то есть p1 = 2, p2 = 3 и т. д. Теорема 2. В n-вершинном орграфе Г при n > 2 минимальная примитивная система имеет не более k простых контуров, где k - наибольший номер, при котором Р2 ... Pk ^ n. Доказательство. Наибольшее значение k достигается при наименьших взаимно простых длинах контуров li,... ,lk, где lk ^ n. Наименьшие числа, составляющие множество k взаимно простых чисел, имеют следующий вид [6, с. 9-10]: li = pi.. .pk/pi, i = 1,... ,k. Тогда lk = p2 .. .pk ^ n. ■ Следствие 4. В условиях теоремы 1 5т, [in n_|n, Доказательство. В таблице для некоторых интервалов значений n приведены оценки k и r, полученные с помощью теоремы 2. 3 < n < 14 15 < n < 104 105 < n < 1154 1155 < n < 15014 15015 < n < 255254 255255 < n < 4849844 1 < r < k = 2 1 < r < k < 3 1 < r < k < 4 1 < r < k < 5 1 < r < k < 6 1 < r < k < 7 Оценки следствия 4 вытекают из теоремы 1 и из таблицы, так как k ^ [in nj - 1 при n ^ 1155. ■ Следствие 5. При n - то выполнена асимптотическая оценка k = o(ln n). Доказательство. Воспользуемся известной оценкой [7] pk > k in k. Тогда из теоремы 2 следует k n > Пj in j. j=2 Отсюда k! < n при k > 3. Используя формулу Стирлинга и логарифмируя неравенство (k/e)k < n, получаем, что k(ln k - 1) < in n при k - то. Следовательно, k = o(ln n) при n -У то. ■ Замечание 1. Оценки и алгоритмы вычисления чисел Фробениуса для любого числа аргументов, требуемые при оценивании экспонентов орграфов, можно найти в ряде публикаций [8,9]. Выводы 1) Для получения оценки экспонента графа в соответствии с теоремой 1 и её следствиями можно использовать любую примитивную систему контуров. Наименьшие значения оценок достигаются при одной из минимальных примитивных систем. 2) Порядок величины полученной универсальной оценки экспонента n-вершинного примитивного орграфа варьируется от O(n) до O(n2) при n - то. Оценки теоремы 1 и её следствий принимают значения порядка O(n2), только если кратчайший контур примитивной системы имеет длину порядка O(n). 3) На множестве графов Виландта полученная оценка совпадает с абсолютной оценкой Виландта. ЛИТЕРАТУРА

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

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

Авторы

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

Ссылки

Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. N.52. S. 642-648.
Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. 448 с.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Когос К. Г., Фомичев В. М. Положительные свойства неотрицательных матриц // Прикладная дискретная математика. 2012. №4(18). С. 116-121.
Фомичев В. М. Эквивалентные по Фробениусу примитивные множества чисел // Прикладная дискретная математика. 2014. №1(23). С. 20-26.
Кяжин С. Н., Фомичев В. М. О примитивных наборах натуральных чисел // Прикладная дискретная математика. 2012. №2(16). С. 5-14.
Rosser B. The n-th prime is greater than n log n // Proc. London Math. Soc. 1939. V. 45. P.21-44.
Alfonsin J. R. The Diophantine Frobenius Problem. Oxford University Press, 2005.
Фомичев В. М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов // Прикладная дискретная математика. 2014. №2(24). С. 88-96.
 Новая универсальная оценка экспонентов графов | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/6

Новая универсальная оценка экспонентов графов | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/6