On attractors of dynamical systems associated with cycles.pdf Под конечной динамической системой понимается пара (S, 8), где S - конеч-ное непустое множество, элементы которого называются состояниями системы,8 : S " S - отображение множества состояний в себя, называемое эволюционной функ-цией системы.Каждой конечной динамической системе сопоставляется карта - ориентирован-ный граф с множеством вершин S и дугами, проведенными из каждой вершины s Е Sв вершину 8(s). Этот граф является функциональным, т. е. из каждой вершины выхо-дит точно одна дуга. Компоненты связности графа, задающего динамическую систему,называются её бассейнами.Каждый бассейн представляет собой контур с входящими в него деревьями. Кон-туры называются предельными циклами или аттракторами.Основными проблемами теории конечных динамических систем являются зада-чи отыскания эволюционных параметров состояний системы без проведения динами-ки, таких, как индекс (расстояние до аттрактора того бассейна, которому принадле-жит состояние), период (длина соответствующего аттрактора), ветвление (количествонепосредственных предшественников) [1] и др. Программа [2] позволяет исследоватьнекоторые из эволюционных параметров определенных систем. Одной из нерешенныхв общем случае задач является вопрос о том, принадлежит ли данное состояние ат-трактору, что обозначено, например, в [3, 4].В данной работе представлены критерий принадлежности состояния аттракторами описание формирования аттракторов динамических систем двоичных векторов, по-рожденных такими графами, как циклы.Пусть имеется n-звенный цикл с. Выберем в нём какую-либо вершину в качественачальной и обозначим её со, тогда цикл можно записать как с = СоС1... cn-1cn, гдеcn = со. Придадим каждому ребру цикла произвольную ориентацию. Дуги, имеющиенаправление по часовой стрелке, пометим символом 1, а дуги с противоположной ори-ентацией - символом 0.Таким образом, каждой ориентации цикла сопоставляется n-мерный двоичный век-тор. С другой стороны, каждый такой вектор однозначно определяет некоторую ори-ентацию цикла, так что между множеством Cn, n > 2, всевозможных ориентацийn-звенного цикла и множеством Bn всех двоичных векторов размерности n устанав-ливаетсявзаимно однозначное соответствие.Динамическая система (Cn, 0) вводится следующим образом: если дан некоторыйграф с из Cn, то его динамическим образом 0(c) является граф, получаемый из содновременным превращением всех стоков в источники (SER-динамика бесконтурныхграфов [3]).Исходная динамическая система (Cn, 0) оказывается изоморфной динамической си-стеме (Bn, 0), которая вводится следующим образом: пусть состоянием динамическойсистемы (Bn, 0) в данный момент времени является вектор v Е Bn, тогда в следующиймомент времени она окажется в состоянии 0(v), описываемом следующими правилами:1) если первой компонентой в v является 0 и последней компонентой является 1, топервой компонентой в 0(v) будет 1, а последней компонентой - 0; 2) если в составе vимеются диграммы 10, то в 0(v) каждая из них заменяется на 01; 3) других отличиймежду v и 0(v) нет. Вышеперечисленные правила применяются одновременно. Будемполагать по определению, что контуры представляют собой аттракторы единичнойразмерности. На рис. 1 показана карта динамической системы (B6, 0).Рис. 1. Карта динамической системы (B6, 9)Через pc(v) обозначим циклическую плотность вектора v, т. е. количество парсовпадающих соседних компонент в нем с учётом циклического сдвига. Например,Pc(111111) = 6, pc(l01010) = 0, pc(111011) = 4, pc(0(111O11)) = pc(110111) = 4. Оче-видно, что для состояния v системы (Bn, 0) выполняется условие 0 ^ pc(v) ^ п.Циклический блок - это максимальное по включению множество подряд стоящих ну-лей (0-блок) или единиц (1-блок) в количестве ^ 2 с учетом циклического сдвига.При работе с динамической системой, ассоциированной с циклом, будем под понятиемблок подразумевать понятие циклический блок. Длина блока - число нулей (единиц)в блоке, уменьшенное на 1. Обозначим через p0, p^ суммы длин с учетом циклическогосдвига рассматриваемых 0-блоков и 1-блоков соответственно.Теорема 1 (критерий принадлежности состояния аттрактору). Вектор динами-ческой системы (Bn, 0) тогда и только тогда принадлежит аттрактору, когда у негоp0 = 0 или plc = 0 . При этом периоды равны делителям числа п, и если p0 = 0, тоаттрактор представляет собой цикл, в котором следующее состояние получается изпредыдущего циклическим сдвигом влево на одну компоненту, а при pc = 0 - вправо.Подробное изложение представленных результатов можно найти в [5].

Скачать электронную версию публикации