The finite dynamic system of all possible orientations of a given graph with all accessible states and with inaccesible .pdf Графовые модели, в которых отказы процессоров интерпретируются как удаление соответствующих вершин, а отказы сетевых каналов - как удаление дуг, занимают важное место в задачах, связанных с отказоустойчивостью компьютерных сетей. При изучении модельных графов можно применять идеи и методы теории конечных динамических систем [1-3]. В модели [1] в качестве механизма восстановления работоспособности сети предлагается так называемая SER-динамика бесконтурных связных ориентированных графов. В настоящей работе графы изучаются с точки зрения динамического подхода к отказоустойчивости графовых систем. Под ориентированным графом (орграфом) понимается пара "G = (V, в), где V - конечное непустое множество вершин; в V X V - отношение смежности на множестве V (пара (u, v) G в называется дугой орграфа). Неориентированным графом (или, для краткости, графом) называется пара G = (V, в), где в - симметричное и анти-рефлексивное отношение на множестве вершин V. Дуги неориентированного графа называют рёбрами. Граф G = (V, в) называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается Kn. Вершины u и v графа G называются связанными, если в G существует проходящий через них путь. Отношение связанности является эквивалентностью на множестве вершин графа. Классы этого отношения называются компонентами связности (или просто компонентами) графа. Говорят, что вершина v достижима из вершины u, если в орграфе существует путь из u в v. Вершина орграфа, недостижимая из других его вершин, называется источником, а вершина, из которой недостижима никакая другая вершина, - стоком [4]. Под конечной Динамической системой понимается пара (S, 5), где S - конечное непустое множество состояний системы; 5 : S G S - отображение множества состояний в себя, называемое эволюционной функцией системы. Конечной динамической системе сопоставляется карта, представляющая собой ориентированный граф с множеством вершин S и дугами, проведёнными из каждой вершины s G S в вершину 5(s). Основными проблемами теории конечных динамических систем являются задачи отыскания эволюционных параметров системы без проведения динамики. K числу основных характеристик состояний динамических систем относятся свойства достижимости и недостижимости: состояние, не имеющее непосредственных предшественников, называется неДостижимым или начальным состоянием системы, иначе состояние называется Достижимым. В [5] описаны недостижимые состояния конечных динамических систем всех возможных ориентаций графов. В данной работе характеризуются конечные динамические системы всех возможных ориентаций графов, все состояния которых являются достижимыми и в которых есть недостижимые состояния. Пусть дан некоторый граф G. Пометим его вершины и придадим его рёбрам произвольную ориентацию, тем самым получив ориентированный граф gG. Применим к полученному орграфу эволюционную функцию а, которая у данного орграфа одновременно переориентирует все дуги, входящие в стоки, а остальные дуги оставляет без изменения, в результате чего получаем орграф a(G). Если проделать эти действия со всеми возможными ориентациями данного графа, то получим карту динамической системы. Такая динамика для бесконтурных связных орграфов введена в [1]. Итак, будем рассматривать конечную динамическую систему (Го, а), где через rG обозначим множество всех возможных ориентаций графа G , а эволюционная функция а задаётся следующим образом: если дан некоторый орграф G G Го, то его динамическим образом a(-G) является орграф, полученный из G одновременной переориентацией всех дуг, входящих в стоки, других отличий между GG и а (GG ) нет. На рис. 1 изображён граф G и карта конечной динамической системы (Го, а). Теорема 1. В конечной динамической системе (Го, а) все состояния являются достижимыми тогда и только тогда, когда в графе G компонентами связности являются полные графы с п вершинами при 1 п 3, и только они. На рис. 1 граф G имеет следующие три компоненты связности: один граф K1, один граф K2 и один граф K3; все состояния конечной динамической системы (Го, а) являются достижимыми. Теорема 2. В конечной динамической системе (Го, а) есть недостижимые состояния тогда и только тогда, когда в графе G есть компоненты связности, отличные от полных графов с п вершинами при 1 п 3. Теорема 3. Количество графов G с п вершинами, образующих конечные динамические системы (Го, а), все состояния которых являются достижимыми, равно КСДоп = 1 + п + п L(n_3)/2J + E i=1 п - 2i ы L3J 3 В таблице приведены данные о количестве графов с п вершинами, 1 п 12, образующих конечные динамические системы (Го, а) со всеми достижимыми (граф Д) и недостижимыми (граф Н) состояниями, полученные с помощью вычислительных экспериментов. n Количество графов Д % Количество графов Н % 1 1 100 0 0 2 2 100 0 0 3 3 75 1 25 4 4 « 36 7 « 64 5 5 « 15 29 « 85 6 7 « 4 149 « 96 7 8 « 1 1036 « 99 8 10 « 0,1 12336 « 99,9 9 12 « 0,004 274656 « 99,996 10 14 « 0,0001 12005154 « 99,9999 11 16 « 0,000002 1018997848 « 99,999998 12 19 « 0,00000001 165091172573 « 99,99999999 Рис. 1. Граф G и карта конечной динамической системы (Го, а) Можно заметить, что при увеличении количества вершин в графе G в большинстве конечных динамических систем (Го. а) есть недостижимые состояния.

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