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

УДК 519.17

ДИСКРЕТНАЯ ДИНАМИЧЕСКАЯ СИСТЕМА НА ДВОЙНОМ ЦИРКУЛЯНТЕ С РАЗНЫМИ ФУНКЦИЯМИ В ВЕРШИНАХ

А. М. Нажмиденова

Исследована структура функционального графа дискретной динамической системы, состоящей из двух циркулянтов Gn,k с различной ориентацией и мультипликативным отображением на одном циркулянте и аддитивным на другом. Описаны неподвижные точки, выведено рекуррентное соотношение для числа неподвижных точек и получена асмиптотика этого числа, а также описаны висячие вершины и их число для частного случая k = 2.

Ключевые слова: генная сеть, дискретная модель, регуляторный контур, циркулянт, функциональный граф, циклы, неподвижные точки, висячие вершины.

Работа посвящена анализу функционирования дискретной модели генной сети. Характерной особенностью организации генных сетей является способность к саморегулированию через регуляторные контуры с положительными и отрицательными обратными связями. Процесс перераспределения концентраций веществ в регуляторном контуре может быть описан дискретной моделью, а строение регуляторных контуров может быть сформулировано в терминах ориентированных графов. В данной работе моделью является граф-носитель, состоящий из двух циркулянтов Gn>k [1-3] противоположной ориентации, соответствующие вершины которых попарно сопряжены. Вершины графа-носителя имеют веса x0,x1,... , xn—1, y0, y1,... , yn-i из конечного поля F2, где Xi соответствуют вершинам первого циркулянта, а yi — вершинам второго. Набор w = (xo,... ,xn-1 ,y0,... ,yn-1) E F2n назовем состоянием системы. В каждый момент времени состояние системы меняется и динамика его изменения определяется отображением

FuncMult,Add : F22n ^ Fia, где Mult — мультипликативное отображение, действующее на вершинах первого циркулянта, и Add — аддитивное на вершинах второго, принимающие значения из F2 в каждой вершине в зависимости от весов в тех к вершинах, дуги из которых входят в данную вершину.

Функциональным графом GMult,Add называется орграф, вершинами которого являются наборы из F22n, причём дуга из вершины w идёт в вершину V тогда и только тогда, когда FuncMuit,Add(w) = V.

Описаны неподвижные точки для произвольных n и к, а также выведено рекуррентное соотношение и асимптотика числа неподвижных точек.

Теорема 1. Число неподвижных точек Sn выражается рекуррентной формулой

Sn = Sn— 1 + Sn-k.

Для асимптотического поведения Sn справедливо

Sn - Ck Rn,

где Ck — константа, зависящая только от к, а 1 < R < 2 — наибольший по модулю корень характеристического уравнения

\к - \k—1 - 1 = 0

рекуррентного соотношения (1).

Для случая k = 2 доказана

Теорема 2. Число висячих вершин функционального графа равно 22n — 3n.

Получены необходимые и достаточные условия принадлежности набора циклу длины не более двух.

Теорема 3 (необходимое условие). В графе функционирования для цикла длины не более двух вида (а, в) ^ (y,$) ^ (а, в) выполнены условия y = в, $ = а, где а, в,1,$ — наборы длины n.

Теорема 4 (достаточное условие). Если в наборе X = (x0,... , xn-l,y0,... , yn-l) для всех i = 0,... ,n — І выполняются условия

1) если xi — 0, то y(i-1) mod n — y(i+l) mod n — 0;

2) если yi — 1, то x(i-1) mod n — x(i+l) mod n — 1,

и при этом Xj = yj для некоторого j, то X принадлежит циклу длины два.

ЛИТЕРАТУРА

1. Григоренко Е. Д., Евдокимов А. А., Лихошвай В. А., Лобарева И. А. Неподвижные точки и циклы автоматных отображений, моделирующих функционирование генных сетей // Вестник Томского государственного университета. Приложение. 2005. №14. С. 206-212.

2. Evdokimov A. A. and Kutumova E. O. The discrete model of the gene networks regulatory loops with the threshold functions // Proc. 7th Int. Conf. on bioinformatics of genom regulation and structure. Novosibirsk, June 20-27, 2010. P. 155.

3. Харари Ф. Теория графов М.: Наука, 2003.

УДК 519.1T

О Т-НЕПРИВОДИМЫХ РАСШИРЕНИЯХ СВЕРХСТРОЙНЫХ ДЕРЕВЬЕВ

Д. Ю. Осипов

Рассматривается один из способов построения оптимального расширения графа — Т-неприводимого расширения (ТНР). Приводится способ построения всех неизоморфных ТНР для подкласса сверхстройных деревьев — равнолучевых звезд.

Ключевые слова: граф, Т-неприводимое расширение, сверхстройные деревья, равнолучевые звезды.

Все понятия и определения взяты из работы [1].

Определение 1. Расширением n-вершинного графа G называется граф H с (n + І) вершинами, такой, что граф G вкладывается в каждый максимальный подграф графа H.

Простейшим примером расширения графа является его тривиальное расширение — соединение с одноэлементным графом (т. е. к графу G добавляется новая вершина, которая соединяется ребром с каждой вершиной графа G).

Возникает вопрос о получении такого расширения графа G, которое не содержит «лишних» ребер. Один из способов — конструкция минимального расширения графа [2], другой — его Т-неприводимого расширения [3].

Определение 2. Минимальным расширением графа G называется его расширение с минимальным количеством ребер.