On attractors in finite dynamic systems of binary vectors associated with palms orientations.pdf Под конечной динамической системой понимается пара (S, 8), где S - конечное непустое множество, элементы которого называются состояниями системы, 8 : S ^ S - отображение множества состояний в себя, называемое эволюционной функцией системы. Каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведёнными из каждой вершины s £ S в вершину $(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры, в свою очередь, называются предельными циклами, или аттракторами. Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров без проведения динамики. К их числу относятся свойство принадлежности состояния аттрактору и описание аттракторов системы (их количество, вид и длина). Автором составлены программы для ЭВМ, позволяющие вычислять различные параметры динамических систем двоичных векторов, ассоциированных с некоторыми типами графов, в частности [1]. Дерево называется пальмой, если оно является объединением цепей, имеющих общую концевую вершину, причём все эти цепи, за исключением, быть может, одной, имеют длину 1. Пальма является частным случаем сверхстройного (звездообразного) дерева (дерево, в котором в точности одна вершина имеет степень больше 2). Пусть пальма p образована объединением цепей p0, p1, ..., pc, имеющих общую концевую вершину. Будем считать, что p0 имеет среди этих цепей максимальную длину s ^ 1. Назовём p0 стволом пальмы p, цепи p1, p2, ..., pc, имеющие длину 1, - её листьями, а их совокупность - кроной. Будем говорить, что p является пальмой типа (s,c). Пальма с точностью до изоморфизма определяется своим типом. При c = 1 пальма вырождается в цепь [2, 3], поэтому далее не будем рассматривать этот случай, считая c > 1. Пусть имеется пальма p типа (s,c), s + c = n. Зафиксируем расположение её цепей и перенумеруем рёбра пальмы p, начиная от корня (начальной вершины ствола), двигаясь к кроне (рёбра с номерами от 1 по s), а далее рёбра кроны слева направо (рёбра с номерами от s + 1 по s + c). Придадим каждому ребру пальмы произвольную ориентацию и сопоставим полученному ориентированному графу n-мерный двоичный вектор v(p), полагая его i-ю компоненту равной 1, если i-е ребро пальмы p ориентировано от корня, и 0 - в противном случае. Теперь можно последовательно выписать получившуюся последовательность из нулей и единиц: v = v1... vS.vS+1... vs+c, где Vj, 0 < i ^ s + c, принимает значение 0 или 1 в зависимости от ориентации i-го ребра пальмы. Таким образом, каждой ориентации пальмы сопоставляется n-мерный двоичный вектор, причём n = s + c. В свою очередь, каждый такой вектор v однозначно определяет некоторую ориентацию пальмы p(v) типа (s,c). Таким образом, между множеством Ps+c, s > 0, c > 1, всевозможных ориентированных пальм типа (s,c) указанного вида и множеством Bs+c, s > 0, c > 1, всех двоичных векторов размерности n = s + c устанавливается взаимно однозначное соответствие. В дальнейшем ориентации пальмы для простоты также будем называть пальмами. Опишем конечную динамическую систему ориентаций (s, c)-пальмы p на языке двоичных векторов. Пусть состоянием динамической системы в данный момент времени является вектор v = v1... vS.vS+1... vs+c £ Bs+c. Тогда в следующий момент времени она окажется в состоянии y(v) = v', полученном путём одновременного применения следующих правил: I) если v1 = 0, то v' = 1; II) если vj = 1 и vj+1 = 0 для некоторого 0 < i < s, то vj = 0 и vj+1 = 1; III) если vj = 1 для некоторого s < i ^ s + c, то vj = 0; IV) если vs = 1 и vj = 0 для всех s 0, с > 1, соответствуют эволюционным преобразованиям соотносимых им двоичных векторов в динамической системе (Bs+c,Y), s > 0, с > 1, и обратно, а именно v(y(p)) = y(v(p)) [5]. Таким образом, динамические системы (Bs+c, y) и (Ps+c, y), s > 0, с > 1, изоморфны. Теорема 1. Динамическая система (Bs+c,y), s > 0, с > 1, имеет единственный бассейн и аттрактор, представляющий собой двухэлементный контур, образуемый состояниями (01)(s-1)/201c и (10)(s-1)/210c при нечётном s и состояниями (01)s/20c и (10)s/21c при чётном s. Следствие 1. В динамической системе (Bs+c,Y), s > 0, с > 1, состояния (01)(s-1)/201c и (10)(s-1)/210c при нечётном s и состояния (01)s/20c и (10)s/21c при чётном s, и только они, принадлежат аттрактору.

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