О количестве аттракторов в конечных динамических системах ориентаций полных графов | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/33

О количестве аттракторов в конечных динамических системах ориентаций полных графов

Рассматриваются конечные динамические системы ориентаций полных графов. Состояниями системы являются все возможные ориентации полного графа, а эволюционная функция задаётся так: динамическим образом орграфа является орграф, полученный из исходного путём переориентации всех дуг, входящих в стоки, других отличий между исходным орграфом и его образом нет. Подсчитывается количество аттракторов в системе, приводятся соответствующие таблицы для конечных динамических систем ориентаций полных графов с количеством вершин от двух до десяти включительно.

On the number of attractors in finite dynamic systems of complete graphs orientations.pdf Графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг, занимают важное место в задачах, связанных с отказоустойчивостью компьютерных сетей. При изучении модельных графов можно применять идеи и методы теории конечных динамических систем, в частности динамических систем двоичных векторов [1, 2],- когда имеется естественная двоичная кодировка графов рассматриваемого класса. В модели [3] в качестве механизма восстановления работоспособности сети предлагается так называемая SER-динамика бесконтурных связных ориентированных графов. В настоящей работе полные графы изучаются с точки зрения динамического подхода к отказоустойчивости графовых систем. Под ориентированным графом (орграфом) понимается пара G = (У,в), где V - конечное непустое множество (вершины орграфа); в С V х V - отношение на множестве V (пара (u,v) Е в называется дугой орграфа с началом u и концом v). Отношение в называют отношением смежности. Отсутствие петель (дуг с совпадающими началом и концом) в орграфе ~G = (V, в) означает антирефлексивность его отношения смежности в. Неориентированным графом (графом) называется пара G = (V,в), где в - симметричное и антирефлексивное отношение на множестве вершин V. Дуги неориентированного графа называют рёбрами. Орграф ~G = (V, в) называется направленным графом (диграфом), если отношение в антисимметрично. Пусть ~G = (V, в) -некоторый орграф, v Е V - одна из его вершин. Степенью исхода вершины v Е V называется число d+(v) дуг орграфа ~G, имеющих своим началом v; степень захода вершины v - это количество d-(v) дуг, имеющих v своим концом. Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается Kn. Маршрут, в котором никакая дуга не встречается более одного раза, называется путём. Путь, каждая вершина которого принадлежит не более чем двум его дугам, по определению является простым. Простой циклический путь в орграфе называется контуром. Турниром называется полный направленный граф [4]. Под конечной динамической системой понимается пара (S,8), где S - конечное непустое множество, элементы которого называются состояниями системы; 8: S^S - отображение множества состояний в себя, называемое эволюционной функцией системы. Таким образом, каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведёнными из каждой вершины s Е S в вершину 8(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Каждый бассейн представляет собой контур с входящими в него деревьями. Контуры, в свою очередь, называются предельными циклами, или аттракторами. Под длиной аттрактора понимается количество образующих его (принадлежащих ему) состояний. Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров системы без проведения динамики. К их числу относится описание аттракторов системы, определение их количества. Автором написаны программы для ЭВМ, позволяющие вычислять различные параметры конечных динамических систем, ассоциированных с некоторыми типами графов [5]. Описаны аттракторы конечных динамических систем ориентаций некоторых типов графов [6, 7]). В данной работе подсчитывается количество аттракторов в конечных динамических системах ориентаций полных графов. Пусть дан полный граф G = (V,в), V = (vi,v2,... ,vn}, n > 1, m = n(n - 1)/2 - число рёбер. Придадим рёбрам произвольную ориентацию, тем самым получив направленный граф (турнир) G = (V, в), где отношение смежности в антирефлексивно и антисимметрично. Применим к полученному орграфу эволюционную функцию а, которая у данного орграфа одновременно переориентирует все дуги, входящие в стоки (вершины с нулевой степенью исхода), а остальные дуги оставляет без изменения, в результате получим орграф a("G^). Если проделать указанные действия со всеми возможными ориентациями данного графа, то получим карту данной динамической системы, состоящую из одного или нескольких бассейнов. Таким образом, будем рассматривать конечную динамическую систему (Гкп, а), n > 1, где Гкп - множество всех возможных ориентаций полного графа Kn, |Гкп | = 2m. На рис. 1 изображена карта конечной динамической системы (Гк3, а). А А- Рис. 1. Карта конечной динамической системы (Гк3, а) В [3] рассматривается конечная динамическая система (Q,a), где П - множество всех бесконтурных ориентаций данного графа, и замечается, что для полного графа существует n! бесконтурных ориентаций, где n! - количество перестановок его вершин, при этом система имеет (n - 1)! бассейнов, каждый из которых состоит исключительно из аттрактора длины n. Теорема 1. В конечной динамической системе (Гкп, a), n > 1, количество аттракторов длины 1 равно 2(n-1)(n-2)/2(2n-1 - n). Теорема 2. В конечной динамической системе (Гкп, a), n > 1, количество аттракторов длины n равно (n - 1)! . Теорема 3. В конечной динамической системе (Гкп,a), n > 1, количество аттракторов (бассейнов) равно 2(n-1)(n-2)/2(2n-1 - n) + (n - 1)!. Например, в конечной динамической системе (Гк3, a) (рис.1) 4 аттрактора (бассейна): два аттрактора длины 1 и два аттрактора длины 3. В таблице приведены данные по количеству аттракторов в конечных динамических системах (Гкп, a) для 1 < n < 11, полученные с помощью вычислительных экспериментов. n Количество аттракторов (бассейнов) Длины 1 Длины n 2 1 0 1 3 4 2 2 4 38 32 6 5 728 704 24 6 26744 26624 120 7 1868496 1867776 720 8 251663280 251658240 5040 9 66303597952 66303557632 40320 10 34497177684352 34497177321472 362880 Можно заметить, что при увеличении n количество аттракторов длины 1 в конечных динамических системах (Гкп, a) начинает составлять абсолютное большинство по сравнению с аттракторами длины n.

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

tournament, graph orientation, graph, finite dynamic system, evolutionary function, attractor, complete graph, эволюционная функция, турнир, полный граф, ориентация графа, конечная динамическая система, аттрактор, граф

Авторы

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

Ссылки

Жаркова А. В. Об аттракторах в конечных динамических системах ориентаций полных графов // Прикладная дискретная математика. Приложение. 2016. №9. С. 112-114.
Жаркова А. В. Аттракторы в конечных динамических системах двоичных векторов, ассоциированных с ориентациями пальм // Прикладная дискретная математика. 2014. №3(25). С. 58-67.
Власова А. В. Исследование эволюционных параметров в динамических системах двоичных векторов // Свидетельство о государственной регистрации программы для ЭВМ №2009614409, выданное Роспатентом. Заявка №2009613140. Дата поступления 22 июня 2009 г. Зарегистрировано в Реестре программ для ЭВМ 20 августа 2009 г.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997.
Barbosa V. C. An Atlas of Edge-Reversal Dynamics. London: Chapman&Hall/CRC, 2001.
Салий В. Н. Об одном классе конечных динамических систем // Вестник Томского госу-дарствеthereнного университета. Приложение. 2005. №14. С. 23-26.
Colon-Reyes O., Laubenbacher R., and Pareigis B. Boolean monomial dynamical systems // Ann. Combinatorics. 2004. V. 8. P. 425-439.
 О количестве аттракторов в конечных динамических системах ориентаций полных графов | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/33

О количестве аттракторов в конечных динамических системах ориентаций полных графов | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/33