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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 17
ДИСКРЕТНАЯ ДИНАМИЧЕСКАЯ СИСТЕМА НА ДВОЙНОМ ЦИРКУЛЯНТЕ С РАЗНЫМИ ФУНКЦИЯМИ В ВЕРШИНАХ
А. М. Нажмиденова
Исследована структура функционального графа дискретной динамической системы, состоящей из двух циркулянтов Gn, k с различной ориентацией и мультипликативным отображением на одном циркулянте и аддитивным на другом. Описаны неподвижные точки, выведено рекуррентное соотношение для числа неподвижных точек и получена асмиптотика этого числа, а также описаны висячие вершины и их число для частного случая k = 2.
Ключевые слова: генная сеть, дискретная модель, регуляторный контур, циркулянт, функциональный граф, циклы, неподвижные точки, висячие вершины.
Работа посвящена анализу функционирования дискретной модели генной сети. Характерной особенностью организации генных сетей является способность к саморегулированию через регуляторные контуры с положительными и отрицательными обратными связями. Процесс перераспределения концентраций веществ в регуляторном контуре может быть описан дискретной моделью, а строение регуляторных контуров может быть сформулировано в терминах ориентированных графов. В данной работе моделью является граф-носитель, состоящий из двух циркулянтов Gn& gt-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. (1)
Для асимптотического поведения Sn справедливо
Sn — Ck Rn,
где Ck — константа, зависящая только от к, а 1 & lt- R & lt- 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 называется его расширение с минимальным количеством ребер.

ПоказатьСвернуть
Заполнить форму текущей работой