Задачи об отказоустойчивости и факторизациях графов как математических моделей дискретных систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

У ,/ у? ^у

{/¿/ -г / у „А, _ ^ // р^ы СУ ^

САРАТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.Г.ЧЕРНЫШЕВСКОГО

На правах рукописи

КАБАНОВ Михаил Александрович

ЗАДАЧИ ОБ ОТКАЗОУСТОЙЧИВОСТИ И ФАКТОРИЗАЦИЯХ ГРАФОВ КАК МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДИСКРЕТНЫХ СИСТЕМ

01.01.09 - математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель -кандидат физико-математических наук, профессор В.Н.САЛИЙ

САРАТОВ -1998

ОГЛАВЛЕНИЕ

стр.

ВВЕДЕНИЕ ..............................................................................................................................................................................................3

ГЛАВА 1. Конгруэнции ориентированных графов ........................................................14

§1. Основные понятия и теорема о соответствии

конгруэнций ................................................................................................................................................................15

§2. Функциональные конгруэнции ....................................................................................................29

§3. Ациклические конгруэнции ..............................................................................................................46

§4. Циклические конгруэнции ..................................................................................................................56

§5. Древесные конгруэнции ......................... ........................................................................64

5.1. Входящие деревья ..............................................................................................................................64

5.2. Выходящие деревья ..........................................................................................................................67

5.3. Цепи ............................................................................................................................................................................79

ГЛАВА 2. Отказоустойчивость графов ...........................................................82

§1. Основные понятия и теорема об оптимальной

1-отказоустойчивой реализации колеса .................................... 82

§2. Оптимальные 1-отказоустойчивые реализации

цепей колес ................................................................................. 89

ЛИТЕРАТУРА ...............................................................................................................................105

ВВЕДЕНИЕ

За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов дискретной математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, химии и биологии, в теории расписаний и дискретной оптимизации.

Теория графов является существенной частью математического аппарата кибернетики. Этому способствует также тривиальность понятия графа, которое опирается на понятие множества: содержательно граф можно представить в виде объекта, состоящего из двух множеств - вершин и ребер.

Графом (ориентированным графом) называется пара 0 = (У,а), где V - конечное непустое множество, а а - отношение на V. Неориентированным графом называется граф, у которого отношение смежности а антирефлексивно и симметрично.

По мнению Е.С.Согомоняна и Е.В.Слабакова [21], на сегодняшний день решение проблемы технической диагностики, связанной с достижением высоких показателей надежности вычислительных систем, имеет два основных направления. Первое основано на использовании самопроверяемых средств функционального диагностирования. Второе основано на использовании отказоустойчивых избыточных структур. Настоящая работа содержит две главы. Каждая из глав посвящена некоторым аспектам соответствующего направления, которые получают

хорошую интерпретацию при представлении дискретных устройств графами.

Граф выступает в качестве математической модели реальных устройств при решении многих задач технической диагностики [5, 6, 30, 31]. Вершины графа ассоциируются со структурными элементами, а связи (ребра) графа отражают схему функционирования устройства. Однако довольно часто для решения конкретных задач возникает необходимость редукции такой модели. Так, П.П.Пархоменко [18] предложил способ редукции заданного графа при сохранении условий задания и учета всех неизбыточных маршрутов. Одним из способов редукции графа является его факторизация. В результате применения этого способа получается фактор-граф. Полученный граф сохраняет особенности исходного графа и при этом является графом с хорошо известными свойствами, что позволяет использовать его при решении многих задач. П.П.Пархоменко и Е.С.Согомонян рассмотрели специальный фактор-граф - обобщенный граф [17, 20]. Обобщенный граф имеет большое значение при решении многих задач технической диагностики. Например, П.П.Пархоменко и Е.С.Согомонян [17] предложили с использованием обобщенного графа диагностировать максимальные одновыходные подсхемы комбинационного устройства и строить схемы встроенного контроля дискретных устройств. На основе обобщенного графа М.Гессель и Е.С.Согомонян [4] провели анализ слабой независимости выходов комбинационного устройства для неисправности одиночных элементов. Д.В.Сперанский [22] предложил алгоритм построения обобщенного графа, программная реализация которого основана на использовании быстрых машинных команд.

Одной из наиболее распространенных моделей дискретных устройств является автомат. Автоматом (конечным автоматом без выходов, или полуавтоматом, или автоматом Медведева) называется тройка А = (8,Х,3), где Л" = {л-,,^,...,^} - конечное множество состояний автомата, X = {х1,хг,..,,хт) - конечное множество входных сигналов, а

8 :5 х X —» 5 - функция переходов. Если множество входных сигналов автомата одноэлементно, то автомат называется автономным.

Всякий автомат А = (8,Х,6) может быть представлен в виде таблицы с двумя входами. Другим способом представления автомата является диаграмма - граф с помеченными дугами. Вершины этого графа соответствуют состояниям автомата, и из вершины в вершину sJ

проводится дуга с меткой хеХ, если ¿>(л'.,.х)- л\. Под графом О

автомата А будем понимать граф, получаемый из диаграммы автомата А стиранием всех меток и слиянием параллельных дуг. Заметим, что граф автономного автомата, фактически, является его диаграммой. Таким образом, автономный автомат и его граф можно рассматривать как один и тот же объект. В общем случае, в графе автомата теряется различие между сигналами автомата. Поэтому граф О не дает полного представления об исходном автомате. Таким образом, граф автомата является упрощенной моделью автомата, сохраняя при этом схему его функционирования. Однако с использованием графа данного автомата появляется возможность исследовать свойства автомата с помощью методов теории графов.

Основным объектом исследования данной работы будут графы автоматов (автоматные графы). При этом следует отметить, что не всякий граф является автоматным. Теорема о характеризации автоматных графов (глава 1, §1) утверждает, что граф является автоматным тогда и только тогда, когда степень исхода всякой вершины этого графа не менее единицы. Поэтому некоторые определения теории графов будут формулироваться с учетом этой особенности автоматных графов.

Отношение эквивалентности р на множестве £ называется конгруэнцией автомата А = (8,Х,6), если оно устойчиво относительно функции переходов, т.е.

(Уя^ е е Х)((51;52) е р => (¿(515х),£(л'2,х)) е р).

Совокупность всех конгруэнции автомата А обозначим Con А. Известно, что множество конгруэнций автомата, упорядоченное теоретико-множественным включением, образует решетку.

Решетка Con А является важной характеристикой автомата. Поэтому класс задач, связанных с конгруэнциями автомата довольно широк. Методы получения всевозможных разбиений множества состояний автомата предложил Хартманис [27]. Эффективный алгоритм построения решетки Con А, "применимый как для машины, так и для ручного счета", предложил Фарр [25]. Маккензи доказано, что для всякого автомата существует автомат с четырьмя входными сигналами, имеющий такую же решетку конгруэнций [19]. С.Р.Когаловский и В.В.Солдатова [15] доказали, что всякая конечная решетка представима как решетка конгруэнций частичного автомата с двумя входными сигналами.

Алгеброй А называется пара (A, F), где А - непустое множество (носитель), a F — {/], ,..., fm} — конечный набор операций на А. Под п-арной операцией алгебры А понимается отображение /': А" -» А. При п = 1 операция / называется унарной. Алгебра, у которой все операции унарные, называется унарной алгеброй. Унарная алгебра с одной операцией называется унаром.

Пусть А = (A, F) и В = (B,F) - две однотипные алгебры (соответствующие операции в А и В имеют одинаковое обозначение). Гомоморфизмом алгебры А в алгебру В называется отображение <р:А-^В такое, что для любых а1за2,...,ая е А и и-арной операции / е F выполняется равенство: <p{f (аиа2,...,ап)) = /(^(¿^),<р(а2),...,(р{ап)). Гомоморфизм алгебры в себя называется эндоморфизмом.

Ядром отображения д>:А->В называется отношение Kerq> := {{а,Ъ) е Ах А \ <р{а) = <рф)}.

Отношение эквивалентности 0 на множестве А называется конгруэнцией алгебры А = {A,F), если оно устойчиво относительно всех

операций этой алгебры, т.е. для любых элементов ах,а2,...,ап,ЬХ,Ь2..,Ъп е А и любой п -арной операции / е I7 верно (а1,Ь1)ев&(а2,Ь2)ев8с...8с(ап,Ь^е9^{/(а1,а2,...,а^,/(Ь1,Ь2,...,Ьп))ев.

Всякий автомат можно рассматривать как унарную алгебру, а всякую конечную унарную алгебру можно рассматривать как автомат. Таким образом, класс автономных автоматов и класс конечных унаров, фактически, классы одних и тех же объектов. Известно [2], что гомоморфизмы и конгруэнции автомата - это в точности гомоморфизмы и конгруэнции унарной алгебры, соответствующей этому автомату. В частности, ядро всякого гомоморфизма автомата является конгруэнцией этого автомата и всякая конгруэнция автомата является ядром подходящего гомоморфизма этого автомата.

В виду сложности задач, связанных с различными свойствами решетки конгруэнции автомата, многие из них удалось решить лишь в частном случае автономного автомата. Известно описание автономных автоматов, у которых решетка конгруэнций является двухэлементной [19], одноатомной (Йоэли [32]), полумодулярной сверху (Берман [24]), решеткой с дополнениями, модулярной, дистрибутивной, цепью, решеткой Стоуна (Л.А.Скорняков и Д.П.Егорова [8], Д.П.Егорова [7]). Г.Ч.Куринной [16] описал автономные автоматы с изоморфными решетками конгруэнций и нашел условия, при которых автономный автомат определяется своей решеткой конгруэнций. Различные соответствия между решеткой подавтоматов и решеткой конгруэнций автономного автомата исследовала А.В.Киреева [13]. В.Н.Салий [19] описал класс полугрупп эндоморфизмов автомата с двухэлементной решеткой конгруэнций.

Несмотря на перечисленные выше результаты крут нерешенных задач, связанных с конгруэнциями (автоматов и алгебр) достаточно широк. Многие задачи решены лишь в частном случае автономных автоматов (унаров). В связи с этим в настоящей работе решаются некоторые задачи, касающиеся конгруэнций, для промежуточного объекта по отношению к автономным и произвольным автоматам - графа автомата. Напомним, что

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

Фактор-графом графа 0 = (У,а) по эквивалентности гсГхК называется граф О/т = (¥/т,а/т), где У/т - множество классов эквивалентности т,аа/т:= {(г(и),г(у)) : (Биг е т{и)У е г(у))((и',у') е а)}.

Конгруэнцию автомата абстрактно можно понимать как эквивалентность с заданным условием, которое определяется входными сигналами автомата. Однако в графе данного автомата получить это условие невозможно, так как в графе все дуги равнозначны. В связи с этим дополнительное условие для конгруэнции графа предлагается выбрать специальным образом. Если К - некоторый класс графов и О -произвольный граф, то К-конгруэнцией графа О называется отношение эквивалентности ж на множестве его вершин такое, что фактор-граф О/ж принадлежит К. А.М.Богомолов и В.Н.Салий [3] поставили задачу изучения К-конгруэнций графов для различных конкретных классов К. Случай, когда К - класс корневых деревьев (класс неориентированных графов), рассмотрела А.В.Киреева [11, 12]. Она же рассмотрела случай, когда К - класс турниров [9, 14]. Гилл и Флексер [26] решили некоторые задачи, связанные с циклическими конгруэнциями графов произвольных автоматов.

Перечисленные ранее задачи можно интерпретировать как алгебраические задачи, связанные с различными способами факторизации математических моделей дискретных устройств. В этом смысле описываемая далее задача носит комбинаторный характер.

Как уже отмечалось, один из распространенных способов достижения высоких показателей надежности вычислительных систем основывается на использовании отказоустойчивых избыточных систем. Понятие отказоустойчивости впервые было введено Авиженисом [23] как

"способность компьютеров выполнять корректно специальные алгоритмы, несмотря на отказы оборудования и ошибки программ". Обзорная статья Авижениса [1] посвящена основным аспектам отказоустойчивости. Она содержит обзор истории развития отказоустойчивых систем, методы реализации, а также направления дальнейших исследований. Понятие отказоустойчивости было формализовано Хейзом [28, 29]. Им было предложено представлять вычислительные системы и алгоритмы, выполнимые с помощью этих систем, в виде графов с метками. Метки обозначают типы вычислимых элементов (выполняемых операций). В частном случае (все метки совпадают) Хейзом были решены задачи об оптимальной отказоустойчивости для специальных классов графов - цепей и циклов [28]. Аналогичную задачу для класса функциональных графов решила А.В.Киреева [10]. В настоящей работе описаны оптимальные 1-отказоустойчивые графы для класса деревьев - цепей колес.

Несмотря на бурное развитие теории графов в течение последних десятилетий, существует ряд нерешенных задач, при решении которых возможно эффективное использование аппарата теории графов. Настоящая работа посвящена решению таких задач, связанных с технической диагностикой. В работе можно выделить две части. Первая часть посвящена решению задач, связанных с различными способами редукции (факторизации) графов как математических моделей различных объектов технической диагностики и теории автоматов. При этом понятийная система и постановка задач формулируются в соответствии с близкими задачами о конгруэнциях автоматов и алгебр. Вторая часть посвящена решению задач об отказоустойчивости графов, которые проистекают из задач, связанных с отказоустойчивостью вычислительных систем.

Работа состоит из введения, двух глав, содержащих 7 параграфов, и библиографии, включающей 32 наименования. Диссертация изложена на 108 страницах.

Далее кратко излагаются основные результаты диссертации.

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

В первом параграфе главы 1 формулируются основные понятия, используемые на протяжении всей главы. Теорема о характеризации автоматных графов устанавливает необходимое и достаточное условие для того, чтобы граф был автоматным графом. В первом параграфе также доказывается важная теорема 1.1o соответствии конгруэнции Эта теорема является основополагающей при исследовании упорядоченных множеств К-конгруэнций графов. Следствия этой теоремы позволяют сводить задачу описания упорядоченного множества К-конгруэнций графа G к задаче описания упорядоченного множества К-конгруэнций подходящего фактор-графа графа G, а также сводить задачу описания упорядоченного множества К-конгруэнций графа G, где К1 - подкласс класса К, к задаче описания упорядоченного множества К-конгруэнций подходящего фактор-графа графа О. Поэтому в каждом параграфе главы 1 используются результаты теоремы 1.1 о соответствии конгруэнции.

Различным классам К графов соответствуют разные параграфы главы 1, описывающие соответствующие К-конгруэнции. Так в §2 описываются К-конгруэнции для класса K=F функциональных графов; в §3 — для класса К=АС ациклических графов (графов, которые не содержат циклов); в §4 - для класса К=С циклов; в §5 - для классов К различных деревьев. Так как в классе ориентированных графов возможна различная интерпретация деревьев, то §5 состоит из трех подпунктов, в которых рассматриваются такие классы деревьев как входящие деревья (К=1Т), выходящие (корневые) деревья (К=ОТ) и цепи (КНР).

В параграфах 2-5 главы 1 рассматриваются следующие вопросы, связанные с К-конгруэнциями, для различных классов К графов:

- описание в терминах графа необходимых и достаточных условий, при которых эквивалентность на множестве �