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

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

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

On number of inaccessible states in finite dynamic systems of complete graphs orientations.pdf Графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг, занимают важное место в задачах, связанных с отказоустойчивостью компьютерных сетей. При изучении модельных графов можно применять идеи и методы теории конечных динамических систем [1-3]. В модели [1] в качестве механизма восстановления работоспособности сети предлагается так называемая SER-динамика бесконтурных связных ориентированных графов. В настоящей работе полные графы изучаются с точки зрения динамического подхода к отказоустойчивости графовых систем. Под ориентированным графом (орграфом) понимается пара "G = (V, в), где V - конечное непустое множество вершин; в С V х V - отношение смежности на множестве V (пара (u,v) е в называется дугой орграфа). Неориентированным графом (или, для краткости, графом) называется пара G = (V, в), где в - симметричное и антирефлексивное отношение на множестве вершин V. Дуги неориентированного графа называют рёбрами. Орграф "G = (V, в) называется направленным графом (или диграфом ), если отношение в антисимметрично. Граф G = (V, в) называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначим Kn. Турниром называется полный направленный граф. Говорят, что вершина v достижима из вершины u, если в орграфе существует путь из u в v. Вершина орграфа, не достижимая из других его вершин, называется источником, а вершина, из которой не достижима никакая другая вершина, - стоком [4]. Под конечной динамической системой понимается пара (S, 5), где S - конечное непустое множество состояний системы, 5 : S " S - отображение множества состояний в себя, называемое эволюционной функцией системы. Каждой конечной динамической системе сопоставляется карта, представляющая собой орграф с множеством вершин S и дугами, проведёнными из каждой вершины s е S в вершину 5(s). Компоненты связности графа, задающего динамическую систему, называются её бассейнами. Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров системы без проведения динамики. К их числу относятся ветвление (количество непосредственных предшественников данного состояния) и, в частности, свойство недостижимости состояния (то есть когда состояние имеет нулевое ветвление). Автором описаны недостижимые состояния конечных динамических систем всех возможных ориентаций графов [5], подсчитаны количества недостижимых состояний в системах, связанных с ориентациями цепей, циклов, пальм [6]. В данной работе предлагаются формулы для подсчёта количества недостижимых и количества достижимых состояний в конечных динамических системах ориентаций полных графов. Пусть дан полный граф Kn, n > 1, m = n(n - 1)/2 - число рёбер. Придадим его рёбрам произвольную ориентацию, тем самым получив направленный граф (турнир) G. Применим к полученному орграфу эволюционную функцию а, которая у данного орграфа одновременно переориентирует все дуги, входящие в стоки, а остальные дуги оставляет без изменения, в результате чего получим орграф а( G), других отличий между "G и a(G) нет. Если проделать указанные действия со всеми возможными ориентациями данного графа, то получим карту конечной динамической системы (Гкп, а), n > 1, где через Гкп обозначим множество всех возможных ориентаций данного полного графа Kn, |Гкп | = 2m, состоящую из одного или нескольких бассейнов. На рис. 1 изображена карта конечной динамической системы (Гк3, а). А А- Рис. 1. Карта конечной динамической системы (Гк3, а) Теорема 1. Состояние Е Гкп конечной динамической системы (Гкп, a), n > 1, недостижимо тогда и только тогда, когда в орграфе (G нет источника и есть сток. Теорема 2. Количество недостижимых состояний в конечной динамической системе (ГКп, a), n > 1, равно КНС(Г*„ ,a) = n(2(n-1)(n-2)/2 - (n - 1)2(n-2)(n-3)/2). Следствие 1. Количество достижимых состояний в конечной динамической системе (ГКп, a), n > 1, равно КДС(Гкп >a) = 2n(n-1)/2 - n(2(n-1)(n-2)/2 - (n - 1)2(n-2)(n-3)/2). В таблице приведены данные по количеству недостижимых и достижимых состояний в конечных динамических системах (Гкп, a) для 2 ^ n ^ 10, полученные с помощью вычислительных экспериментов. n КНС(Гк„ ,a) КДС(ГКп ,a) 2 0 2 3 0 8 4 8 56 5 160 864 6 4224 28544 7 186368 1910784 8 14942208 253493248 9 2264924160 66454552576 10 663035576320 34521336512512 Можно заметить, что в конечных динамических системах (Гкп, a) большинство состояний являются достижимыми.

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

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

Авторы

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

Ссылки

Barbosa V. C. An atlas of edge-reversal dynamics. London: Chapman&Hall/CRC, 2001.
Khrennikov A. and Nilsson M. On the number of cycles of p-adic dynamical systems //J. Number Theory. 2001. V. 90. P. 255-264.
Салий В. Н. Об одном классе конечных динамических систем // Вестник Томского госуниверситета. Приложение. 2005. №14. С. 23-26.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
Жаркова А. В. О ветвлении и непосредственных предшественниках состояний в конечной динамической системе всех возможных ориентаций графа // Прикладная дискретная математика. Приложение. 2013. №6. С. 76-78.
Жаркова А. В. Недостижимые состояния в динамических системах, ассоциированных с цепями и циклами // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2011. Т. 11. Вып. 4. С. 116-123.
 О количестве недостижимых состояний в конечных динамических системах ориентаций полных графов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/29

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