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) большинство состояний являются достижимыми.

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