On number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations.pdf Под конечной динамической системой понимается пара (S,8), где S - конечное непустое множество, элементы которого называются состояниями системы; 8 : S ^ S - отображение множества состояний в себя, называемое эволюционной функцией системы. Каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведёнными из каждой вершины s G S в вершину 8(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры называются предельными циклами, или аттракторами. Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров без проведения динамики. К их числу относятся ветвление (количество непосредственных предшественников данного состояния) и, в частности, свойство недостижимости состояния (то есть когда состояние имеет нулевое ветвление). Автором составлены программы для ЭВМ, позволяющие вычислять различные параметры динамических систем двоичных векторов, ассоциированных с некоторыми типами графов [1], описаны недостижимые состояния конечных динамических систем двоичных векторов, ассоциированных с графами [2], подсчитаны количества недостижимых состояний в системах, связанных с ориентациями цепей и циклов [3]. Дерево называется пальмой, если оно является объединением цепей, имеющих общую концевую вершину, причём все эти цепи, за исключением, быть может, одной, имеют длину 1. Пальма является частным случаем сверхстройного (звездообразного) дерева (дерево, в котором в точности одна вершина имеет степень больше 2). Пусть пальма p образована объединением цепей po,p1,... ,pc, имеющих общую концевую вершину. Будем считать, что po имеет среди этих цепей максимальную длину s ^ 1. Назовёмpo стволом пальмы p, цепиp1,p2,... ,pc, имеющие длину 1, - её листьями, а их совокупность - кроной. Будем говорить, что p является пальмой типа (s,c). Пальма с точностью до изоморфизма определяется своим типом. При c =1 пальма вырождается в цепь (см., например, [3, 4]), поэтому далее полагаем c> 1. Пусть имеется пальма p типа (s, c), s + c = n. Зафиксируем расположение её цепей и перенумеруем рёбра пальмы p, начиная от корня (начальной вершины ствола), двигаясь к кроне (рёбра с номерами от 1 по s), а далее рёбра кроны слева направо (рёбра с номерами от s + 1 до s + c). Придадим каждому ребру пальмы произвольную ориентацию и сопоставим полученному ориентированному графу p n-мерный двоичный вектор v(p), полагая его i-ю компоненту равной 1, если i-е ребро пальмы p ориентировано от корня, и 0 - в противном случае. Теперь можно последовательно выписать получившуюся последовательность из нулей и единиц: v = vi... v8.v8+i... v8+c, где vi, 0 < i ^ s + c, принимает значение 0 или 1 в зависимости от ориентации i-го ребра пальмы. Таким образом, каждой ориентации пальмы сопоставляется n-мерный двоичный вектор, причём n = s + c. В свою очередь, каждый такой вектор v = vi ... v8.v8+i... v8+c однозначно определяет некоторую ориентацию пальмыp(v) типа (s, c). Таким образом, между множеством P8+c, s > 0, c > 1, всех возможных ориентированных пальм типа (s,c) указанного вида и множеством B8+c, s > 0, c > 1, всех двоичных векторов размерности n = s + c устанавливается взаимно однозначное соответствие. В дальнейшем ориентации пальмы для простоты также будем называть пальмами. Опишем конечную динамическую систему ориентаций (s, c)-пальмы p на языке двоичных векторов. Пусть состоянием динамической системы в данный момент времени является вектор v = vi... v8.v8+i... v8+c E B8+c. Тогда в следующий момент времени она окажется в состоянии 7(v) = v', полученном путём одновременного применения следующих правил: 1) если vi = 0, то v' = 1; 2) 3) 4) 0 и v' 1; i+i 0 и vi' = 1 для всех i, если vi = 1 и vi+i = 0 для некоторого i, 0 < i < s, то vi' если vi = 1 для некоторого i, s < i ^ s + c, то v' = 0; если v8 = 1 и vi = 0 для всех i, s < i ^ s + c, то v8 = s < i ^ s + c; 5) других отличий между v и 7(v) нет. Пусть теперь имеется n-рёберная (s, c)-пальма. На языке ориентаций пальм эволюция динамической системы вводится следующим образом: если дана некоторая ориентированная пальма p E P8+c, то её динамическим образом 7(p) является пальма, получаемая из p одновременным превращением всех стоков в источники. Это частный случай динамики бесконтурных связных графов, введённой в [5]. Преобразования ориентаций пальм в динамической системе (P8+c,Y), s > 0, c > 1, соответствуют эволюционным преобразованиям соотносимых им двоичных векторов в динамической системе (B8+c,7), s > 0, c > 1, и обратно, а именно v(y(p)) = 7(v(p)) [6]. Таким образом, динамические системы (B8+c,7) и (P8+c,7), s > 0, c > 1, изоморфны. Теорема 1. Количество недостижимых состояний в динамической системе (B8+c,7), s > 0, c > 1, равно КНС(8+с,7) = 28+c - 28 - 28-3 + П(-1) - 2П(1) + ОД, где [(8-x)/4] Е (-1) i=i i+i . 28-x-4i _ Ci 2 C8-x-3^ причём если коэффициенты или степени принимают отрицательные значения, то соответствующие выражения принимают значение 0. С помощью программы для ЭВМ получены данные о количестве недостижимых состояний в динамической системе (B 8+c,7), представленные для s = 8 и 1

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