Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах | ПДМ. 2014. № 4(26).

Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах

Рассматриваются дискретные динамические системы, заданные на графе-циркулянте, функционирование которых определяется пороговыми функциями. Получены общие свойства графа функционирования системы. В случае значности системы p = 2 проведена классификация всех состояний системы в зависимости от длин серий нулей и единиц. Как результат, получены некоторые свойства циклов функционирования и нижняя оценка количества компонент связности. Для произвольного значения p сформулирован критерий существования неподвижных точек, определены их вид и количество.

Functioning of discrete dynamic circulant-type system with threshold functions.pdf Введение Динамические системы в целом и дискретные динамические системы в частности моделируют различные явления и объекты. С помощью теории динамических систем можно охарактеризовать процесс, который описывает система, тем самым спрогнозировать поведение объекта (явления) в будущем. Например, можно определить, к каким последствиям приведёт какой-либо процесс: к негативным или же, напротив, к позитивным. Одним из объектов, которые моделируют дискретные динамические системы, являются генные сети. 1. Постановка задачи 1.1. Граф функционирования Дискретной динамической системой называется пара (H,A), где П - множество состояний системы, а A - отображение, действующее на множестве состояний: A : П ^ П. Функционированием дискретной динамической системы с начальным состоянием w е П назовём бесконечную последовательность w, A^w), A2(w), A3(w), ..., где AV) = A(w); Ai+1(w) = A(A*(w)) для i е Z+. Графом функционирования (или графом состояний) дискретной динамической системы называют ориентированный граф H = G( V, D) с петлями, где V = П; D = {(ш1,ш2) : ш1,ш2 е П, A(w1) = ш2}. Согласно [1], каждая компонента связности графа функционирования представляет собой единственный контур (возможно, петлю), к которому присоединены деревья, ориентированные к корню. Любой контур этого графа будем называть циклом фунционирования. Для любого состояния ш из цикла функционирования длины r верно Ar (ш) = ш. Любую вершину с петлёй будем называть неподвижной точкой. Другими словами, если ш - неподвижная точка, то А(ш) = ш. Висячую вершину графа функционирования будем называть истоком, т. е. если ш - исток, то для любого ш' G П имеем А(ш') = ш. Задача анализа функционирования дискретных динамических систем состоит в определении качественных характеристик графа функционирования по заданным множеству всех состояний П и отображению перехода A. К качественным характеристикам графа состояния относятся, например, следующие: 1) характеристики компонент связности (циклов функционирования); 2) характеристики неподвижных точек; 3) максимальная длина цикла графа функционирования; 4) максимальная длина цепи в графе функционирования; 5) характеристики истоков. 1.2. Динамическая система циркулянтного типа Рассматриваются динамические системы, заданные на графе-циркулянте [2, 3]. Граф-циркулянт - ориентированный граф Gn,k (1 ^ k ^ n) с множеством вершин V = {0,1,..., n - 1} и множеством рёбер D = {(i, j) : i, j G V, (i - j) mod n ^ k}. Определим множество всех состояний П и отображение перехода A. Каждой вершине i графа-циркулянта сопоставим значение xi из множества Zp = = {0,1,... ,p - 1}. Состоянием назовем кортеж, составленный из значений всех вершин графа-циркулянта: (x0,xi, ...,xn-i), т.е. |П| = pn. Если состояние имеет вид (^с, ^с,..., xx), то будем обозначать его (X). Определим отображение A, действующее на П следующим образом: A((xo,Xi,... ,Xn-i)) = (yo,yi,... , Уп-l), где yi вычисляется по правилу k xi + 1, если YI xi+j 0, среди 1, 2,... , к найдётся хотя бы одно j, такое, j=i что xi+j = 1. Выберем наименьшее такое j и обозначим его j'. Снова, в силу того, k что X - неподвижная точка, верно Е x(i+j')+j < T. Заметим, что в силу выбора j' j=i k выполняется У] xi+j ^ T - 1; с другой стороны, имеем j=j'+i k k j'+k k j'+k T > E x(i+j')+j = E xi+j + E xi+j ^ E xi+j = T - 1; E xi+j = 0. j=i j=j'+i j=k+i j=j'+i j=k+i Так как к + 1 С j' + к, верно xi+k+i = 0 = xi. Аналогично, если xi = 1. ■ Следствие 6. Если состояние X = (x0,xi,... ,xn-i) является неподвижной точкой системы с параметрами n, к, T, то xi = xi+r(k+i) для любого r из Z+. Лемма 8. Если состояние X = (x0, xi,... , xn-i) является неподвижной точкой системы с параметрами n, к, T, то xi = xi+(n,k+i). Доказательство. Пусть к + 1 = r(n, к + 1) и n = q(n, к + 1). Заметим, что r и q - взаимно простые числа. Докажем, что существует такое j ^ 0, что к + 1 делит ((n, к + 1) + jn) нацело. Запишем (n, к + 1) + jn 1 + jq к + 1 r где w Е R+. По свойству взаимно простых чисел существуют а, b Е Z, такие, что ar + bq = 1. Тогда a'r + b'q =1 для а' = a + qt, b' = b - rt при любом t Е Z. В силу того, что r ^ 1 и q ^ 1, можно выбрать t так, чтобы выполнялись условия а' > 0, b' < 0. Возьмём w = а' и j = -b' (при таком t); получим, что к + 1 делит ((n, к + 1) + jn) нацело. Обозначим j' = ((n, к + 1) + jn)/^ + 1). Тогда xi+j'(k+i) = 0 по следствию из леммы 7; (i + (n, к + 1) + jn) = i + (n, к + 1) (mod n). ■ Следствие 7. Если состояние X = (x0,xi,... ,xn-i) является неподвижной точкой системы с параметрами n, к, T, то xi = xi+r(n,k+i) для любого r Е Z+. 4.1. Критерий существования неподвижных точек Теорема 5. Пусть система задана параметрами n, к, T. Тогда неподвижные точки в системе существуют в том и только в том случае, когда выполняется каждое из следующих трёх условий: 1) (n, к + 1) > 1; 2) к + 1 - (к + 1)/(^к + 1) ^ T; 3) (к + 1)/(n, к + 1) нацело делит T. Доказательство. Необходимость. Пусть X - неподвижная точка. 1) Если (n, к + 1) = 1, то по лемме 8 X = (0) или X = (1). Противоречие, так как (0) и (1) не являются неподвижными точками. 2) Пусть k + 1 - (k + 1)/(n, k + 1) < T и существует хотя бы одно такое i, что (n,k+1) (n,k+1) (n,k+1) О, 0. Тогда по лемме 8 X имеет вид (..., 0, ..., 0, ..., 0, ). Xi k+1 Отсюда следует, что xi+j ^ k + 1 - (k + 1)/(n, k + 1) < T, а это означает, j=1 что xi = 1. Противоречие. 3) Пусть k' = (k + 1)/(n, k + 1) не делит нацело T и существует хотя бы одно i, для которого xi = 0. Тогда существуют такие t,q из {0,1,... , k'}, что i+(t+1)(n,k+1) i+(q+1)(n,k+1) xi+j = Xi+j. j=i+t(n,k+1) + 1 j=i+q(n,k+1)+1 Отсюда следует, что существует такое r (1 ^ r < (n,k + 1)), что xiq = xit, где iq = i + q(n, k + 1) + r; it = i + t(n, k + 1) + r. Очевидно, что |it - iq| кратно (n,k + 1), тогда по лемме 8 имеем xiq = xit. Противоречие. Достаточность. Пусть выполнены все три условия. Построим неподвижную точку. Обозначим Tk = T(n, k + 1)/(k + 1). Рассмотрим состояние (n,k+l)-0fc Tk (n,k+l)-Tk Tfc X = ( 0,...,0 ,1,...,1, 0,...,0 ,...,1,...,1). Легко убедиться, что X - неподвижная точка. ■ 4.2. Количество неподвижных точек Теорема 6. Пусть система задана параметрами n, k, T, которые удовлетворяют условию существования неподвижных точек. Тогда количество неподвижных точек равно T + , где Tk = T(n, k + 1)/(k + 1). Доказательство. Как следует из леммы 8 и теоремы 5, неподвижная точка задаётся первыми (n, k + 1) компонентами, сумма которых должна быть равна Tk. Обратно: пусть сумма первых (n, k + 1) компонент состояния X = (xo, x1,... , xn-1) равна Tk, а все остальные компоненты получены повторением первых (n, k + 1) компонент необходимое число раз. Покажем, что X - неподвижная точка системы. В силу свойств состояния X можно провести следующие преобразования: k xi+j j=1 k + 1 (n,k+1) ^ k + 1 (n,k+1) (n,k + 1) jt1 xi+j - xi+k+1 = (n,k + 1) j=1 xi+j - xi k + 1 (n,k+1)-1 ^ = = xj - xi = T = xi. (n, k + 1) j=o Отсюда T 1 , если xi = 1 , k xi+j j=1 T иначе. Это означает, что X - неподвижная точка. Следовательно, неподвижная точка однозначно задаётся расстановкой Tk единиц на первых (n, k +1) позициях и других неподвижных точек, кроме состояний такого т ((n,k + 1)N вида, не существует. То есть число неподвижных точек равно Tk 4.3. Обобщение на случай произвольного p Результаты о неподвижных точках в случае p = 2 можно обобщить на случай произвольного p. Из определения (1) следует, что если состояние X в системе c параметрами p, n, к, T является неподвижной точкой, то либо xi = 0, либо xi = p - 1 для любого i (в противном случае значение xi изменится). Теперь понятно, что так как значения всех компонент в неподвижной точке делятся на p - 1, то рассмотрение неподвижных точек при произвольном значении p эквивалентно случаю двоичной системы с параметрами n, к, [T/(p - 1)]. Теоремы о неподвижных точках можно обобщить следующим образом. Теорема 7. Пусть система задана параметрами p, n, к, T. Тогда неподвижные точки в системе существуют в том и только в том случае, когда выполняется каждое из следующих трёх условий: 1) (n, к + 1) > 1; 2) к + 1 - (к + 1)/(n, к + 1) ^ [T/(p - 1)]; 3) (к + 1)/(n, к + 1) нацело делит [T/(p - 1)]. Теорема 8. Пусть система задана параметрами p, n, к, T, которые удовлетворяют условию существования неподвижных точек. Тогда количество неподвижных точек Доказательства теорем 7 и 8 аналогичны доказательствам теорем для p = 2. Заключение В ходе работы основным предметом изучения были циклы графа функционирования дискретных динамических систем заданного вида. Отдельно, как частный случай циклов функционирования, рассмотрены неподвижные точки (циклы длины 1). Для них получено полное их описание при произвольном значении p: необходимое и достаточное условие их существования, их количество и вид. Циклы функционирования в общем случае рассматривались для систем с параметром p = 2. Установлено, что любой цикл функционирования либо полностью состоит из состояний с длинными сериями, либо полностью - из состояний с короткими. Для состояний с длинными сериями доказано, что любое из них лежит в цикле графа функционирования. Построены две конструкции для получения состояний с короткими сериями, лежащих в циклах, из состояний систем с меньшими значениями параметров. В дальнейшем планируется получить полное описание всех циклов из состояний с короткими сериями и с помощью этого улучшить оценку количества компонент связности графа функционирования.

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

дискретные динамические системы, граф функционирования, граф-циркулянт, пороговые функции, циклы графа функционирования, неподвижные точки, discrete dynamic systems, functional graph, circulant graph, threshold functions, cycles of functional graph, stable states

Авторы

ФИООрганизацияДополнительноE-mail
Быков Игорь СергеевичНовосибирский государственный университетмагистрант механико-математического факультетаpatrick.no10@gmail.com
Всего: 1

Ссылки

Harary F. The number of functional digraphs // Math. Ann. 1959. V. 139. P. 203-210.
Евдокимов А. А., Лиховидова Е. О. Дискретная модель генной сети с пороговыми функциями // Вестник ТГУ. Приложение. 2008. №2. С. 18-21.
Кутумова Е. О. Циклы функционирования дискретной модели регуляторного контура генной сети с пороговыми функциями // Дискретный анализ и исследование операций. 2011. Т. 38. №3. С. 65-75.
Григоренко Е. Д., Евдокимов А. А., Лихошвай В. А., Лобарева И. А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестник Томского государственного университета. Приложение. 2005. №14. С. 206-212.
 Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах | ПДМ. 2014. № 4(26).

Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах | ПДМ. 2014. № 4(26).