Периоды p-графов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/5

Периоды p-графов

Связный граф с n ^ 3 вершинами, полученный из контура Cn путём переориентации некоторых его дуг, называется многоугольным графом. Рассмотрим некоторую биекцию р между множеством стоков и множеством источников многоугольного графа G. Присоединим к G все дуги вида vр(v), где v - сток. Полученный сильносвязный граф будем называть р-графом. Рассматривая последовательность различных матриц A, A2, A3,... (степеней булевой матрицы A), заметим, что эта последовательность конечна. Если Am - её последний элемент, то Am+1 = A1 для некоторого l ^ m. Число ind(A) = l - 1 называется индексом матрицы A, а число p(A) = ((m + 1) - l) - её периодом. Для графа G с матрицей смежности A положим ind(G) = ind(A) и p(G) = p(A) (индекс и период графа). Вычислены значения периодов всех неизоморфных р-графов с числом вершин до 9. Рассчитаны максимальные периоды р-графов с числом вершин до 17. Доказана теорема, позволяющая вычислить период любого р-графа. Найдено значение максимального периода n-вершинных р-графов при чётном n и дана оценка максимального периода при нечётном n.

Periods of p-raphs.pdf Введение Ориентированный граф (далее граф) - это пара G = (V, а), где V - конечное непустое множество, а а С V2 - бинарное отношение на множестве V. Отношение а называют отношением смежности, а соответствующую ему двоичную булеву матрицу - матрицей смежности графа G. Элементы множества V называются вершинами графа, а пары, входящие в отношение смежности а, - его дугами. Если (u,v) G а, то говорят, что вершина u является началом дуги (u, v), а вершина v - её концом. При u = v получается петля (u,u). Считаем, что каждая вершина графа инцидентна некоторой дуге, т. е. является началом или концом некоторой дуги. Говорят, что вершина v достижима из вершины u за k ^ 1 шагов, если существует последовательность примыкающих дуг (маршрут) (w0, wl), (wl, w2),... , (wk-l, ), где w0 = u и = v. Если A - матрица смежности орграфа G, то последнее определение означает, что на пересечении строки, соответствующей элементу u, и столбца, соответствующего элементу v, в матрице-степени Ak стоит 1. Маршрут с неповторяющимися вершинами Cn = vlv2 ... vnvl, в котором начало и конец совпадают, называется n-элементным контуром. Граф G = (V, а) по определению является функциональным, если его отношение смежности функционально (т.е. из каждой вершины исходит точно одна дуга). Функциональный граф называется связным, если он содержит точно один контур. Под высотой вершины в функциональном графе понимается расстояние от неё до контура, т. е. минимальная из длин цепей с началом в данной вершине и концом в вершине, принадлежащей контуру. Под конечной динамической системой понимается пара (S, 8), где S - конечное непустое множество состояний системы, 8 : S ^ S - отображение множества состояний в себя, называемое эволюционной функцией системы. Таким образом, каждой конечной динамической системе сопоставляется карта, представляющая собой граф с множеством вершин S и дугами, проведёнными из каждой вершины s G S в вершину 8(s). Этот граф является функциональным. Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Получается, что каждый бассейн представляет собой контур с входящими в него деревьями. Контуры, в свою очередь, называются предельными циклами, или аттракторами. Индексом состояния называют его расстояние до аттрактора, а периодом - длину принимающего аттрактора. Связный граф с n ^ 3 вершинами, полученный из контура Cn путем переориентации некоторых его дуг, называется многоугольным графом. Граф называется примитивным, если существует целое число r ^ 1, такое, что каждая вершина графа достижима из любой вершины за r шагов (иначе говоря, если в матрице Ar все элементы равны 1). Таким образом, каждый примитивный граф является сильносвязным (любые две вершины взаимно достижимы), но обратное не верно. 1. Об индексах и периодах Пусть A - булева матрица. Рассматривая последовательность различных матриц A, A2, A3,... , заметим, что эта последовательность конечна и что, если Am - её последний элемент, то Am+1 = A1 для некоторого l ^ m. Число ind(A) = l - 1 называется индексом матрицы A, а число p(A) = ((m +1) - l) -её периодом. Так определённые индекс и период матрицы A - это её индекс и период в динамической системе булевых матриц соответствующей размерности с эволюционной функцией $(Afc) = Afc+1. Для графа G с матрицей смежности A положим ind(G) = ind(A) и p(G) = p(A) (индекс и период графа). Пару t(G) = (ind(G), p(G)) назовём типом графа G. Об индексах и периодах графов см. [1]. Ряд работ посвящён двоичным булевым матрицам с минимально возможным типом (0, 1) (идемпотентные матрицы) [2]. Индексы и периоды относятся к числу важнейших параметров, связываемых с графами. Решению проблем, связанных с этими параметрами, посвящены работы [1-6]. Об индексах состояний в динамических системах, связанных с графами, см. [7-11]. Не для всех графов индексы и периоды аналитически вычислены. Известны, например, следующие результаты. Теорема 1 [3]. Индекс функционального графа равен уменьшенной на единицу максимальной из высот его элементов, а период - наименьшему общему кратному длин его контуров. Теорема 2 [3]. Бесконтурный граф имеет индекс, равный максимальной из длин его цепей, и период, равный 1. Каковы максимальные значения индекса и периода для n-вершинного графа? Для периода точная формула неизвестна, асимптотической оценкой является (n ln n)1/2 [6]. Что касается индекса, то имеются компьютерные вычисления [4], которые показывают, что для графа с n вершинами справедливо неравенство ind ^ (n - 1)2. 2. О периодах р-графов Вершина графа называется источником, если в неё не входит ни одна дуга, и стоком, если из неё не исходит ни одна дуга. Количество источников в многоугольном графе равно количеству стоков. Пусть р - некоторая биекция между множеством стоков и множеством источников данного многоугольного графа G. Если к G присоединить все дуги вида vp(v), где v - сток, получится сильносвязный граф, назовём его р-графом. Конструкция р-графа предложена в [12] в связи с проблемой описания минимальных примитивных расширений для многоугольных графов. В частности, доказано, что любой р-граф, полученный из данного многоугольного графа, является его минимальным сильносвязным расширением. В каждом многоугольном графе есть по крайней мере один источник. Такая вершина имеет степень исхода 2. Эту степень она сохранит и в любом р-графе, связанном с исходным многоугольным графом. Следовательно, р-графы не являются функциональными графами и к ним неприменима теорема 1. Будучи сильносвязными, р-графы не удовлетворяют и условию теоремы 2, так что вопрос об индексах р-графов требует отдельного рассмотрения. Был проведен вычислительный эксперимент, в ходе которого были найдены все неизоморфные р-графы размерности от 3 до 9 вершин и вычислены их периоды. Получены следующие результаты: - n = 3. Существует один р-граф с 3 вершинами. Он имеет период 1. - n = 4. Есть всего три неизоморфных р-графа с 4 вершинами. Два графа имеют период 2 и один - период 3. - n = 5. Есть всего четыре неизоморфных р-графа с 5 вершинами. Данные графы имеют период 1. - n = 6. Есть всего одиннадцать неизоморфных р-графов с 6 вершинами. Три графа имеют период 1, семь графов имеют период 2 и один граф - период 4. - n = 7. Есть всего девятнадцать неизоморфных р-графов с 7 вершинами. Восемнадцать графов имеют период 1 и один граф - период 3. - n = 8. Есть всего сорок семь неизоморфных р-графов с 8 вершинами. Двадцать два графа имеют период 1, двадцать один граф - период 2, два графа - период 3 и по одному графу имеют периоды 4 и 5. - n = 9. Есть всего сто четырнадцать неизоморфных р-графов с 9 вершинами. Сто тринадцать графов имеют период 1 и один граф имеет период 3. Вычислены максимальные периоды графов каждой размерности до 17 вершин (таблица). Максимальные периоды р-графов Размерность Максимальный период 3 1 4 3 5 1 6 4 7 3 8 5 9 3 10 6 11 5 12 7 13 5 14 8 15 7 16 9 17 7 На основе полученных данных сформулировано следующее утверждение. Теорема 3. Период р-графа равен наибольшему общему делителю длин его контуров. Доказательство. Пусть дан р-граф G с матрицей смежности A; C1, C2,..., Ct - множество всех контуров графа G; lx,l2,... - соответствующие длины контуров. 1) Если граф G примитивен, то по определению существует целое число r ^ 1, такое, что в матрице Ar все элементы равны 1, т. е. Ar = Ar+1. По определению период графа G равен (r + 1) - r, т.е. p(G) = 1. По критерию примитивности наибольший общий делитель длин всех контуров примитивного графа равен 1. Таким образом, p(G) = 1, (/1, /2,..., /t) = 1. Следовательно, p(G) = (/1, /2,..., /t). 2) Пусть граф G непримитивен, p(G) = 1 и (7i, /2,..., /t) = 1. Будем обозначать через aij элемент матрицы смежности A, находящийся на пересечении строки i и столбца j. Элемент akj - аналогичный элемент в матрице-степени Ak. Если элемент aj = 1, то это означает, что в исходной матрице A вершина j достижима из вершины i за k шагов (существует путь длины k из вершины i в вершину j). Если в матрице Akl элемент a^j1 равен 1 и в матрице Ak2 элемент akj- равен 1 (k1 < k2), то в матрице A существуют пути длины k1 и k2, соединяющие вершины i и j. Так как в ^-графе любые две вершины взаимно достижимы, то длину простого пути из вершины i в вершину j обозначим k = min{ks : a-1 = 1, s = 1, 2,... }. Рассмотрим некоторый путь длины ks из вершины i в вершину j, где s = 1, 2,... Исходя из структуры ^-графа (в любом ^-графе каждая дуга принадлежит некоторому контуру), имеем, что длина пути из вершины i в вершину j может быть увеличена только за счёт прохождения по некоторому контуру. Таким образом, ks = = k + (x111 + x2/2 + ... + xSk), где x!, x2,..., xst - целые неотрицательные числа. Так как граф G непримитивен, Am+1 = A1 для некоторого / < m. Для любых вершин i и j графа G, таких, что a- = am+1 = 1, имеем / = k + (хг1/1 + x'2/2 + ... + xt/t), (m + 1) = k + (хГ+1/1 + + .. • + xmi+1/t). Период p(A) равен (m +1) - /, следовательно, m + 1 = p(A) + /. Таким образом, P(a)+/ = k+(xm+1/1+xm+1 /2 +...+xm+1/t), / = k+(x1/1+x2/2 +...+xt/t) = k+(xm+1/1+xm+1/2 +...+xm+1/t) - P(a), p(a) = k+(xm+1/1+xm+1/2 +...+xm+1/t) - (k+(xi/i+x2/2 +...+xt/t)), p(A)=(xm+1 /1+xm+1/2 +...+xm+1/t) - (x1/1+x2/2 +...+АМ^/!+zp/2 +...+A) где zf = (x™+1 - xi); xi - целые неотрицательные числа; Zi - целые числа, i = 1, 2,..., t. Так как A1 = Am+!, A1 = Ap(A)+1 = A2p(A)+1 = A3p(A)+1 = ..., то A1 = Aap(A)+1, a = 1, 2,... Следовательно, ap(A) = (z1/1 + z2/2 + ... + zt/t), a = 1, 2,... При z1 = 1, z2 = z3 = ... = zt = 0 имеем a1p(A) = /1. Аналогично asp(A) = /s, s = 1, 2,... ,t, т.е. длина любого контура графа G представима в виде aip, где p = p(A). Следовательно, период графа G является общим делителем длин его контуров. Очевидно, что p ^ min{/i : i = 1, 2,... , t}. Докажем, что p - наибольший делитель. При p = min{/i : i = 1, 2,... , t} это очевидно. Рассмотрим случай, когда p < min{/i : i = 1, 2,... , t}, и докажем, что p - наибольший делитель длин контуров графа G. От противного. Пусть p - общий делитель длин контуров, но не наибольший. Тогда граф G состоит из контуров вида /i = aip, где ai = aci, a, ci - целые числа, i = 1, 2,..., t (т. е. наибольший общий делитель равен ap). Имеем p = (zi/i + z2/2 + ... + ztk) = (ziapci + z2apc2 + ... + ztapct), p = ap(zici + z2C2 + ... + ztCt), 1/a = zici + z2C2 + ... + ztCt, где p, a, ci, zi - целые числа. Последнее уравнение имеет решение в целых числах только при a =1. Следовательно, p - наибольший общий делитель длин контуров графа G. ■ Теорема 4. Максимальный период ^-графа с числом вершин n не превышает |_n/2j + 1, причём эта оценка достигается при чётном n. Доказательство. n-Вершинный ^-граф состоит из n + k дуг (k - количество стоков/источников в исходном многоугольном графе), а сумма длин его контуров равна n + 2k. По теореме 3 p = p(G) = (11, /2,... , /t), p ^ шт{^}, где ^ - длины контуров графа. Очевидно, что максимальный период p = min{/i} имеют графы, у которых контур минимальной длины максимален. При чётном n длина минимального контура будет максимальной при k = 1, t = 2, /1 = /2 = (n + 2k)/2 = n/2 + k = n/2 + 1, т. е. граф имеет два контура длины n/2 + 1. Следовательно, p = n/2 + 1. При нечётном n гипотетически максимальная длина минимального контура достигается при k = 1, t = 2, /1 = [n/2j +1, /2 = [n/2j +2 и равна /1. Так как (l_n/2j + 1, Ln/2j + 2) = 1, перебрав все возможные длины контуров при k = 1, 2,... , получаем, что p(G) < |_n/2j + 1. ■ ^-Графы, полученные из многоугольных графов с одним источником и стоком, будем называть ^-графами. Такой граф имеет два контура. Из теоремы 4 получаем три следствия. Следствие 1. Максимальный период среди всех n-вершинных ^-графов при чётном n имеют ^1-графы. Следствие 2. Максимальный период n-вершинных ^-графов при чётном n равен n/2 + 1. Следствие 3. Максимальный период n-вершинных ^-графов при нечётном n имеет оценку p(G) < |_n/2j +1. 3. Пояснения Коэффициенты zi = xj - Xj -целые числа. Эти коэффициенты могут принимать отрицательные значения (при xj > xj). Как показано в доказательстве теоремы 3, p ^ min{/j : i = 1, 2,... , t}. Случаи p = min{/j : i = 1, 2,..., t} и p =1 не нуждаются в пояснениях. Рассмотрим случай p < min{/j : i = 1, 2,...,t} на примере конкретного ^-гра-фа G (рис. 1) с матрицей смежности A, которая имеет следующий вид: A 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 -(V^--(§> (g^--(V^- Рис. 1. ^-Граф G с матрицей смежности A Для данного графа l = 19, ind(G) = 18, p(G) = 3, Zl = 6, l2 = 9. Рассмотрим пути из вершины vl в вершину v3. Элемент а^ матриц равен 1 при к = 7,13,16,19, 22,... Положим к = 7, kl = 13, к2 = 16, к3 = 19, к4 = 22, ... Запишем, согласно формулам из теоремы 3, ^ = к + xlll + ж^. Подставим известные значения к, к^ ll, l2 и вычислим значения коэффициентов xl, ж1,. Получим xl = 1, x2 = 0. Аналогичные действия выполним и для к2, к3, к4: к2 = к + x2l l + x2l2, x2 = 0 к3 = к + x3l l + x3l2, x3 = 2 к4 = к + x4l l + x4l2, x4 = 1 Так как l = к3 = к + xl l l + x3l2 и к4 = к + x4l l + x4l2 = l + p = к3 + p = к + x l l l + x3l2 + p, то p = к + x4l l + x^l2 - (к + x3l l + x2l2) = (xl - xl)l l + (x2 - x3)l2, где x4 = 1, x4 = 1, x l = 2, x2 = 0. Получаем p = (1 - 2)l l + (1 - 0)l2 = -l l +12 = -6 + 9 = 3. В обозначениях доказательства теоремы 3 имеем z = (x4 - x3) = -1 -отрицательный коэффициент. Заключение Доказана теорема, позволяющая вычислить период любого ^-графа. Дана оценка максимального периода n-вершинных ^-графов и показана её корректность.

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

многоугольный граф, примитивность, р-граф, индекс графа, период графа, polygonal graph, primitivity, p-graph, index and period of graph

Авторы

ФИООрганизацияДополнительноE-mail
Артемова Наталья АлександровнаСаратовский национальный исследовательский государственный университет имени Н. Г. ЧернышевскогоассистентNatalyaKorArt@ya.ru
Всего: 1

Ссылки

Салий В. Н. Отказоустойчивость и оптимизация дискретных систем с заданными индексом и периодом // Вестник Томского государственного университета. Приложение. 2006. №17. С. 222-225.
Chaudhuri R. and Mukherdjea A. Idempotent Boolean matrices // Semigroup Forum. 1980. V. 21. P. 273-282.
Максимов А. А., Салий В. Н. Индексы и периоды нечетких матриц и графов // Теоретические проблемы информатики и её приложения. Саратов: Изд-во Сарат. ун-та, 2006. Вып. 7. С. 87-95.
Максимов А. А. Об индексе и периоде нечеткой матрицы. Саратов, 2005. Деп. в ВИНИТИ 20.01.05. № 78-В2005. 11с.
Бар-Гнар Р. И., Фомичев В. М. О минимальных примитивных матрицах // Прикладная дискретная математика. Приложение. 2014. №7. С. 7-9.
Miller W. The maximum order of an element of a finite symmetric group // Amer. Math. Monthly. 1987. No. 94. P. 497-506.
Barbosa V. C. An Atlas of Edge-Reversal Dynamics. London: Chapman&Hall/CRC, 2001. 385 p.
Салий В. Н. Об одном классе конечных динамических систем // Вестник Томского государственного университета. Приложение. 2005. № 14. С. 23-26.
Власова А. В. Индексы в динамической системе двоичных векторов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2011. Т. 11. Вып.3. С. 116-122.
Жаркова А. В. Индексы в динамической системе двоичных векторов, ассоциированных с ориентациями циклов // Прикладная дискретная математика. 2012. №2. С. 79-85.
Жаркова А. В. Индексы состояний в динамической системе двоичных векторов, ассоциированных с ориентациями пальм // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2016. Т. 16. Вып. 4. С. 475-484.
Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1. С. 116-119.
 Периоды p-графов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/5

Периоды p-графов | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/5