On branching and immediate predecessors of the states in finite dynamic system of all possible orientations of a graph.pdf Под конечной динамической системой понимается пара (S, #), где S — конечное непустое множество, элементы которого называются состояниями системы; S ^ S — отображение множества состояний в себя, называемое эволюционной функцией системы. Таким образом, каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведенными из каждой вершины s Е S в вершину $(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Получается, что каждый бассейн представляет собой контур с входящими в него деревьями. Контуры, в свою очередь, называются предельными циклами, или аттракторами. К числу основных характеристик состояний динамических систем можно отнести ветвление (количество непосредственных предшественников данного состояния), а также свойство недостижимости состояния (то есть когда состояние имеет нулевое ветвление; состояния, обладающие данным свойством, называются также начальными состояниями системы). Автором написаны программы для ЭВМ, позволяющие вычислять различные параметры динамических систем, ассоциированных с некоторыми типами графов [1]. Пусть дан некоторый граф G. Придадим его рёбрам произвольную ориентацию, тем самым получив ориентированный граф "G. Применим к полученному орграфу эволюционную функцию а, которая у данного орграфа одновременно переориентирует все дуги, входящие в стоки (вершины с нулевой степенью исхода), а остальные дуги оставляет без изменения, в результате чего получаем орграф а( G). Если проделать данные действия со всеми возможными ориентациями данного графа, то получим карту динамической системы заданной размерности (что определяется количеством рёбер в графе), состоящую из одного или нескольких бассейнов. Данная динамика для бесконтурных связных орграфов введена в [2]. Итак, будем рассматривать динамическую систему (Гс, а), где через Гс обозначим множество всех возможных ориентаций данного графа G, а эволюционная функция а задаётся следующим образом: если дан некоторый орграф "(G Е Гс, то его динамическим образом a((f) является орграф, полученный из G одновременной переориентацией всех дуг, входящих в стоки, других отличий между G и a(G) нет. Определим ветвление состояний, а также их непосредственных предшественников в полученной системе. Автором, в частности, рассматривались ветвления и непосредственные предшественники состояний в конечных динамических системах, ассоциированных с некоторыми типами графов, например цепями [3]. В [2] состояниями системы являются бесконтурные связные орграфы и замечается, что для любого достижимого состояния s рассматриваемой системы и состояния s' = a(s) каждый сток в s' имеет по крайней мере одну смежную вершину, которая также является стоком и в s. Ставится вопрос об определении всех возможных непосредственных предшественников состояния s' данной динамической системы. Из определённого свойства автор книги замечает, что каждый сток в s' имеет по крайней мере одну смежную вершину, являющуюся источником (вершиной с нулевой степенью захода), и тогда ответ на вопрос может быть получен путём построения всех таких непустых подмножеств множества источников в орграфе, представляющем состояние s', которые смежны со всеми стоками. Тогда количество непосредственных предшественников данного состояния s' равно количеству таких подмножеств; если же для данной ориентации графа таких подмножеств не существует, то такое состояние является начальным. Определение 1. Множество источников ориентированного графа назовем допустимым, если из него в каждый сток этого графа есть дуга. Теорема 1. Ветвление данного состояния s динамической системы (Гс, а) равно: 1) количеству допустимых множеств источников в орграфе ~(G, представляющем состояние s, если в есть стоки; 2) количеству различных подмножеств множества источников, включая пустое, в орграфе , представляющем состояние s, если в нет стоков. Следствие 1. Состояние s динамической системы (Гс, а) недостижимо тогда и только тогда, когда в орграфе , представляющем состояние s, есть по крайней мере один сток и при этом нет ни одного допустимого множества источников, или, другими словами, когда существует хотя бы один сток в (G, не смежный с источниками. Следствие 2. Для неначального состояния s динамической системы (Гс, а) все его непосредственные предшественники определяются: 1) всеми различными допустимыми множествами источников в орграфе G, представляющем состояние s, если в G есть стоки; 2) всеми подмножествами множества источников, включая пустое, в орграфе , представляющем состояние s, если в нет стоков. Это определение происходит следующим образом: все дуги, исходящие из всех источников соответствующего множества, переориентируются, а все остальные дуги остаются без изменения.

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