Аттракторы динамических систем, ассоциированных с циклами | ПДМ. 2011. № 2(12).

Аттракторы динамических систем, ассоциированных с циклами

Доказывается критерий принадлежности состояний аттракторам и описывается формирование аттракторов динамических систем, ассоциированных с циклами, состояниями которых являются двоичные векторы заданной размерности, а эволюционная функция преобразует вектор с помощью одновременного выполнения следующих действий: начальный 0 и последняя 1 заменяются на 1 и 0 соответственно, каждая диграмма 10 - на 01.

Attractors of dynamical systems associated with cycles.pdf ВведениеВ задачах, связанных с отказоустойчивостью компьютерных сетей, заметное ме-сто занимают графовые модели, в которых отказы процессоров интерпретируютсякак удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг.Здесь можно выделить следующую конструкцию, получившую самостоятельное зна-чение в теории графов - бесконтурный граф с заданной структурой источников и сто-ков [1]. В модели [1] в качестве механизма восстановления работоспособности сетипредлагается так называемая SER-динамика бесконтурных графов. Это позволяет ис-пользовать при изучении модельных графов идеи и методы теории конечных динами-ческих систем и, в частности, динамических систем двоичных векторов (см., напри-мер, [2, 3]), когда имеется естественная двоичная кодировка графов рассматриваемогокласса.Под конечной динамической системой понимается пара (S, 8), где S - конеч-ное непустое множество, элементы которого называются состояниями системы,8 : S ^ S - отображение множества состояний в себя, называемое эволюционной функ-цией системы.Каждой конечной динамической системе сопоставляется карта - ориентирован-ный граф с множеством вершин S и дугами, проведенными из каждой вершины s Е Sв вершину 8(s). Этот граф является функциональным, т. е. из каждой вершины выхо-дит точно одна дуга. Компоненты связности графа, задающего динамическую систему,называются её бассейнами.Каждый бассейн представляет собой контур с входящими в него деревьями. Кон-туры называются предельными циклами или аттракторами.Основными проблемами теории конечных динамических систем являются задачиотыскания эволюционных параметров состояний системы без проведения динамики,таких, как индекс (расстояние до аттрактора того бассейна, которому принадлежитсостояние), период (длина соответствующего аттрактора), ветвление (количество непо-средственных предшественников) [4] и другие. Программа [5] позволяет исследоватьнекоторые из эволюционных параметров определенных систем. Одной из нерешенныхв общем случае задач является вопрос о том, принадлежит ли данное состояние ат-трактору, что обозначено, например, в [1, 3].В данной работе представлены критерий принадлежности состояний аттракторами описание формирования аттракторов динамических систем двоичных векторов, по-рожденных такими графами, как циклы.1. Описание динамической системыПусть имеется n-звенный цикл c. Выберем в нём какую-либо вершину в качественачальной и обозначим её со, тогда цикл можно записать как с = c0ci..cn-icn, гдеcn = c0. Придадим каждому ребру цикла произвольную ориентацию. Дуги, имеющиенаправление по часовой стрелке, пометим символом 1, а дуги с противоположной ори-ентацией - символом 0.Таким образом, каждой ориентации цикла сопоставляется n-мерный двоичный век-тор. С другой стороны, каждый такой вектор однозначно определяет некоторую ори-ентацию цикла, так что между множеством Cn, n > 2, всевозможных ориентацийn-звенного цикла и множеством Bn всех двоичных векторов размерности n устанав-ливается взаимно однозначное соответствие.Динамическая система (Cn, в) вводится следующим образом: если дан некоторыйграф c из Cn, то его динамическим образом e(c) является граф, получаемый из cодновременным превращением всех стоков в источники (SER-динамика бесконтурныхграфов [1]).Исходная динамическая система (Cn, в) оказывается изоморфной динамической си-стеме (Bn, в), которая вводится следующим образом: пусть состоянием динамическойсистемы (Bn, в) в данный момент времени является вектор v Е Bn, тогда в следую-щий момент времени она окажется в состоянии e(v), описываемом правилами: 1) еслипервой компонентой в v является 0 и последней компонентой является 1, то первойкомпонентой в e(v) будет 1, а последней компонентой - 0; 2) если в составе v имеют-ся диграммы вида 10, то в e(v) каждая из них заменяется на 01; 3) других отличиймежду v и e(v) нет. Вышеперечисленные правила применяются одновременно. Будемполагать по определению, что контуры представляют собой аттракторы единичнойразмерности. На рис. 1 показана карта динамической системы (B6, в).Рис. 1. Карта динамической системы (B6, в)2. Аттракторы динамической системы (Bn, 0)Через pc(v) обозначим циклическую плотность вектора v, т. е. количество парсовпадающих соседних компонент в нем с учётом циклического сдвига. Например,pc(111111) = 6, pc(101010) =0, pc(111011) = 4, pc(0(111011)) = pc(110111) = 4. Очевидно,что для состояния v системы (Bn, 0) верно 0 ^ pc(v) ^ n. Циклический блок - этомаксимальное по включению множество подряд стоящих нулей (0-блок) или единиц(1-блок) в количестве ^ 2 с учетом циклического сдвига. При работе с динамическойсистемой, ассоциированной с циклом, будем под понятием блок подразумевать понятиециклический блок. Длина блока - число нулей (единиц) в блоке, уменьшенное на 1.Обозначим через p0, p1 суммы длин с учетом циклического сдвига рассматриваемых0-блоков и 1-блоков соответственно.Теорема 1 (критерий принадлежности состояния аттрактору). Вектор динами-ческой системы ( B 0 ) тогда и только тогда принадлежит аттрактору, когда у негоp0 = 0 или p1 = 0 . При этом периоды равны делителям числа n, и если p0 = 0, тоаттрактор представляет собой цикл, в котором следующее состояние получается изпредыдущего циклическом сдвигом влево на одну компоненту, а при p1 = 0 - вправо.Доказательство. Рассмотрим состояния системы (Bn,0) в зависимости от на-личия и количества 0- и 1-блоков.I. Вектор не содержит ни 0-, ни 1-блоков, т. е. p0 = p1 = 0. Это состояние вида п п п (01)2, которое при динамике переходит в состояние (10)2, или вида (10)2, которое ппри динамике переходит в состояние (01)2, где n - четное (при нечетном n состояниесодержит хотя бы один блок, образуемый первой и последней компонентами). Такимобразом, эти состояния образуют аттрактор длины 2.II. Вектор содержит блоки, и все они состоят из 1. Рассмотрим эволюцию такихсостояний в зависимости от количества 1-блоков.1) Вектор имеет единственный 1-блок. Не теряя общности, рассмотрим эволюциютакого состояния при расположении 1-блока в начале вектора. В табл. 1 приведена егосхематичная эволюция.Таким образом, эти состояния образуют аттрактор длины n, причём в нем каждоеследующее состояние получается из предыдущего циклическим сдвигом влево на однукомпоненту. Можно заметить, что длина 1-блока на каждом очередном шаге остаётсяпрежней.2) Вектор имеет несколько блоков, и все они состоят из 1. Из рассмотрения п. II(1)можно заключить, что каждый 1-блок на очередном шаге смещается влево на однукомпоненту c учётом циклического сдвига. Таким образом, такие состояния образу-ют аттракторы, причём в каждом аттракторе следующее состояние получается изпредыдущего циклическим сдвигом влево на одну компоненту, и их периоды равныделителям числа n, отличным от 1 и 2.III. Вектор содержит блоки, и все они состоят из 0. Рассмотрим эволюцию такихсостояний в зависимости от количества 0-блоков.1) Вектор имеет единственный 0-блок. Не теряя общности, рассмотрим эволюциютакого состояния при расположении 0-блока в начале вектора. В табл. 2 приведена егосхематичная эволюция.Таким образом, эти состояния образуют аттрактор длины n, причём в нем каж-дое следующее состояние получается из предыдущего циклическим сдвигом вправона одну компоненту. Можно заметить, что длина 0-блока на каждом шаге остаётсяпрежней.Т а б л и ц а 1 Таблица 2Эволюция вектора, содержащего Эволюция вектора, содержащегоединственный 1-блок единственный 0-блок№ шага Состояние0 1h01... 0101 1h - 1010... 1012 1h-20101... 011h - 2 110... 10101h-2h - 1 101... 010101h-1h 010... 10101hh + 1 101...0101h0h + 2 010... 101h01n - 1 01h01... 01n 1h010... 10№ шага Состояние0 0h101... 01011 10h10...10102 010h1... 0101n - h 1010... 1010hn - h + 1 0101... 010101h-1n - h + 2 0010...101010h-2n - 1 0h-11010... 1010n 0h101... 01012) Вектор имеет несколько блоков, и все они состоят из 0. Из рассмотрения п. III(1)можно заключить, что каждый 0-блок на очередном шаге смещается вправо на однукомпоненту c учётом циклического сдвига. Таким образом, эти состояния образуют ат-тракторы, причём в каждом аттракторе следующее состояние получается из предыду-щего циклическим сдвигом вправо, и их периоды равны делителям числа n, отличнымот 1 и 2.IV. Вектор состоит из 0-блоков (1-блоков), после которых идут 1-блоки (0-блоки).Так как блоки в состоянии рассматриваются с учётом циклического сдвига, то не имеетзначения, идут ли сначала 0-блоки или 1-блоки. Не теряя общности, будем считать,что сначала идут 0-блоки, потом 1-блоки.1. Рассмотрим эволюцию данных состояний, включающих в себя по одному 0-блокуи 1-блоку, в зависимости от их значений p0 и p^.Исходя из рассуждений предыдущих пунктов, можно заключить, что в данном слу-чае на каждом шаге эволюции одновременно 0-блок начнет движение вправо, 1-блок -влево с учётом циклического сдвига, пока не окажутся стоящими рядом. Рассмотримэволюцию с этого шага в зависимости от сумм длин 0- и 1-блоков.а) С о с т о я н и я , д л я к о т о р ы х p0 < p^.В табл. 3 приведена схематичная эволюция таких состояний.Т а б л и ц а 3Эволюция вектора, содержащегоединственные 0-блок и 1-блок, с p0 < pj№ шага Состояние0 01...01010h01hl 0101...011 10. .. 101010h0-11hl-101010.. 102 01.. .0101010ho-21hi-2010101. .10ho - 2 01.. .010101001hl-ho+2010101. .10ho - 1 10.. 101010101hl-ho+10101010. ..01Таким образом, когда блоки оказываются стоящими рядом, то их длины начина-ют уменьшаться у каждого на единицу за счёт поглощения компонент друг друга,пока 0-блок полностью не поглотится. В результате остаётся 1-блок и чередующиеся0 и 1; дальнейшая эволюция такого состояния описана в п. II(1) и показано, что онопринадлежит аттрактору.б) С о с т о я н и я , д л я к о т о р ы х p° = p1.Покажем, что такая ситуация возможна только при четном n, независимо от коли-чества и размерности 0- и 1-блоков. Докажем это индукцией по p°.Базис индукции: p° = 1. Здесь длины 0- и 1-блоков равны 1 и в сумме дают чётноечисло; количество компонент между этими блоками с учетом циклического сдвигатакже чётно, так как это чередующиеся 0 и 1, а после 0-блока обязательно стоит 1 иперед 1-блоком стоит 0. В итоге получаем чётное количество компонент вектора.Шаг индукции. Предположим, что при любом p° ^ m Е N количество компонентвектора чётно, и покажем, что это условие выполняется при p° = m +1.Рассмотрим несколько ситуаций.1) Длины первого 0-блока и последнего 1-блока не равны 1. Тогда отсекаем у этихблоков по одному элементу, получаем случай pc° = m, для которого требуемое условиевыполняется, а отсекли мы две компоненты, т. е. в итоге получаем чётное число ивыполнение нужного условия.2) Длина первого 0-блока или длина последнего 1-блока равна 1. Например, длинапервого 0-блока равна 1. Тогда отсекаем у этих блоков по одной компоненте, получаемслучай p° = m, для которого требуемое условие выполняется. От 0-блока осталась однакомпонента, до следующего 0-блока идёт нечетное количество компонент, а отсекли мыдве компоненты, т. е. в итоге получаем чётное число и выполнение нужного условия.3) Длины первого 0-блока и последнего 1-блока равны 1. Тогда отсекаем у этихблоков по одному элементу, получаем случай pc° = m, для которого требуемое усло-вие выполняется. От 0-блока и 1-блока осталось по одной компоненте, до следующего0-блока идёт нечетное количество компонент, от предыдущего 1-блока идёт нечетноеколичество компонент, а отсекли мы две компоненты, т. е. в итоге получаем чётноечисло и выполнение нужного условия.Заключаем, что действительно ситуация pc° = pci возможна только для векторовчетной размерности.Из рассуждений п. IV(1,a) получаем, что блоки будут поглощать друг друга с каж-дым следующим шагом эволюции, пока от них не останется по одной компоненте,причём это уже будет вектор, полностью состоящий из чередующихся 0 и 1, а про егоэволюцию было сказано в п. I, и это состояние принадлежитаттрактору.в) С о с т о я н и я, д л я к о т о р ы х pc° > pci .Здесь ситуация аналогична п. IV(1,a), только в конце концов остаётся один 0-блоки чередующиеся 0 и 1, дальнейшая эволюция описана в п. III(1).2. Рассмотрим состояния, включающие в себя несколько 0-блоков, после которыхидут 1-блоки, также в зависимости от значений pc° и pci в векторе.а) С о с т о я н и я , д л я к о т о р ы х p° < p1.Из п. IV(1,a) получаем, что здесь на каждом шаге эволюции 0-блоки начинаютдвигаться вправо, а 1-блоки - влево за счёт поглощения компонент, стоящих междублоками, с учетом циклического сдвига; когда они оказываются стоящими рядом, тоблоки начинают уменьшаться на единицу каждый за счёт поглощения компонент другдруга, пока один из блоков полностью не поглотится, после чего опять продолжаютсясдвиги блоков навстречу друг другу, пока не поглотится самый последний 0-блок. Та-ким образом, в состоянии останутся только 1-блоки и чередующиеся 0 и 1, дальнейшаяэволюция описана в п. II, и это состояние принадлежит аттрактору.б) С о с т о я н и я, д л я к о т о р ы х pc° = pci .В п. I V ^ ^ было показано, что такая ситуация возможна только для четного n.Из рассуждений пп. IV(1,6) и IV(2,a) получаем, что при эволюции 0-блоки и 1-блокиначнут движение навстречу друг другу, пока не окажутся рядом, а затем начнут по-глощать друг друга с каждым следующим шагом эволюции, пока не поглотится одиниз блоков, после чего продолжится аналогичное движение, пока рядом не окажутсяпоследние оставшиеся 0-блок и 1-блок, которые начнут поглощать друг друга с каж-дым следующим шагом эволюции, пока от них не останутся по одной компоненте,причём это уже будет вектор, полностью состоящий из чередующихся 0 и 1, эволюциякоторого была описана в п. I, и он принадлежит аттрактору.в) С о с т о я н и я , д л я к о т о р ы х p° > p1.Здесь ситуация аналогична п. IV(2,a), только в состоянии в конце концов остаётсяодин 0-блок и чередующиеся 0 и 1, дальнейшая эволюция состояния описана в п. II, ионо принадлежит аттрактору.V. Вектор состоит из 0-блоков и 1-блоков в произвольном порядке.Из доказательств предыдущих пунктов можно заключить, что при эволюции та-кого состояния 0-блоки будут циклически сдвигаться вправо, при этом если они будутвстречаться с 1-блоками, то длина этого 0-блока будет уменьшаться с очередным ша-гом эволюции, т. е. если есть подряд стоящие 0-блоки, то они или все поглотятся, еслиследующие за ними подряд стоящие 1-блоки в сумме имеют равный или больший поря-док, или поглотят сами следующие за ними подряд стоящие 1-блоки и продолжат сдвигвправо, встречая очередные 1-блоки, если порядок 0-блоков будет больше порядка1-блоков. С точки рассмотрения 1-блоков ситуация получается аналогичная. В итогеполучим состояние, имеющее только 0-блоки, только 1-блоки или содержащее толькочередующиеся нули и единицы, чьи эволюции описаны в пп. I-III, где показано, чтоони и только они (с учетом дальнейшего доказательства) принадлежат аттракторам.Для полноты заметим, что контуры представляют собой аттракторы единичнойдлины; периоды равны делителям числа n. ЗаключениеДля динамических систем, ассоциированных с циклами, решена задача выясненияпринадлежности состояния аттрактору; приведено описание аттракторов этих систем.

Ключевые слова

evolutional function, dynamical system, attractor, эволюционная функция, динамическая система, аттрактор

Авторы

ФИООрганизацияДополнительноE-mail
Власова Анастасия ВладимировнаСаратовский государственный университет им. Н. Г. ЧернышевскогоаспиранткаVAnastasiyaV@gmail.com
Всего: 1

Ссылки

Власова А. В. Исследование эволюционных параметров в динамических системах двоичных векторов // Свидетельство РОСПАТЕНТа №2009614409, зарегистрировано 20 августа 2009.
Власова А. В. Ветвления в конечной динамической системе (Bn, в) // Научные исследования студентов Саратовского государственного университета: материалы итог. студ. науч. конф. Саратов: Изд-во Сарат. ун-та, 2008. С. 57-58.
Colon-Reyes O., Laubenbacher R., and Pareigis B. Boolean monomial dynamical systems // Ann. Combinat. 2004. V. 8. P. 425-439.
Салий В. Н. Об одном классе конечных динамических систем // Вестник Томского госуниверситета. Приложение. 2005. №14. С. 23-26.
Barbosa V. C. An atlas of edge-reversal dynamics. London: Chapman&Hall/CRC, 2001. 372 p.
 Аттракторы динамических систем, ассоциированных с циклами | ПДМ. 2011. № 2(12).

Аттракторы динамических систем, ассоциированных с циклами | ПДМ. 2011. № 2(12).

Полнотекстовая версия