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

• Кабанов, Михаил Александрович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Кабанов, Михаил Александрович

ОГЛАВЛЕНИЕ

стр.

ВВЕДЕНИЕ

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

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

конгруэнций

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

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

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

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

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

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

5.3. Цепи

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

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

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

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

цепей колес

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Задачи об отказоустойчивости и факторизациях графов как математических моделей дискретных систем»

ВВЕДЕНИЕ

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

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

Графом (ориентированным графом) называется пара 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 рассматриваются следующие вопросы, связанные с К-конгруэнциями, для различных классов К графов:

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

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

- описание наименьшей К-конгруэнции графа О;

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

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

Особо следует выделить следующие результаты главы 1.

Определение 2.4 и теорема 2.2 второго параграфа описывают наименьшую Р-конгруэнцию к*. Оказывается, что циклом является фактор-граф по к сильно связного графа (теорема 2.4), а также графа, состоящего из двух сильно связных компонент, соединенных цепями (теорема 2.5). Теорема 2.6 устанавливает необходимые и достаточные условия для графа О, при которых фактор-граф О/л является циклом. Длину этого цикла позволяют вычислить теорема 2.7 и определение 2.6. В §2 также описываются графы, для которых решетка Б-конгруэнций двухэлементна (теорема 2.10) и одноатомна (теорема 2.11).

Теорема 3.6 §3 описывает графы, для которых решетка АС-конгруэнций двухэлементна. При этом оказывается (теорема 3.7), что только для таких графов решетка АС-конгруэнций имеет один атом и является цепью. Следует отметить теорему 3.8, которая утверждает, что решетка АС-конгруэнций модулярна. Также в §3 доказывается теорема 3.9 о перестановочности факторизаций по наименьшей функциональной и наименьшей ациклической конгруэнциям. Этот факт довольно интересен. Во-первых, классы функциональных и ациклических графов являются наиболее широкими из всех рассматриваемых в работе классов. Во-

вторых, теорема 3.9, устанавливает независимость К-конгруэнций этих классов друг от друга.

Теорема 4.4 описывает наименьшую С-конгруэнцию.

Описание наименьшей ОТ-конгруэнции является очень сложным. В связи с этим в параграфе 5, п.2, дается алгоритм 5.1 факторизации графа по наименьшей ОТ-конгруэнции. Этот алгоритм, позволяет объединить некоторые вершины графа таким образом, что в результате факторизации получается корневое дерево, т.е. граф с хорошо известными свойствами, и при этом, что очень важно в технической диагностике, легко диагностируемый граф. Следует добавить, что получаемое в результате факторизации корневое дерево из всех аналогичных фактор-графов исходного графа имеет максимальное число вершин и, следовательно, максимально сохраняет особенности исходного графа. Теорема 5.14 устанавливает условия, при которых решетка ОТ-конгруэнций графа является одноатомной и представляет собой цепь. Оказывается, что эти условия эквивалентны. Теорема 5.15 утверждает, что решетка ОТ-конгруэнций модулярна.

Перечисленные теоремы первой главы составляют ее основные результаты.

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

Глава 2 работы посвящена задаче нахождения оптимальных 1-отказоустойчивых реализаций (ОЮУР) графов из класса цепей колес. В первом параграфе главы 2 вводятся основные понятия, связанные с решаемой задачей, и приводится теорема, описывающая оптимальную 1-отказоустойчивую реализацию колеса. Эта теорема не имеет большого теоретического значения, однако она демонстрирует способ доказательства

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

Апробация работы. Результаты диссертации докладывались на студенческой конференции механико-математического факультета МГУ (Москва, 1994), на Пятом Межгосударственном семинаре "Дискретная математика и ее приложения" (Москва, 1995), на XI Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996), на заседаниях Саратовского городского алгебраического семинара (1995) и семинара по математической кибернетике при Саратовском университете (1997), на научно-практической конференции ВЦ СГУ (1997).

Основные результаты диссертации опубликованы в работах [33-37].

Список литературы диссертационного исследования кандидат физико-математических наук Кабанов, Михаил Александрович, 1998 год

ЛИТЕРАТУРА

1. Авиженис А. Отказоустойчивость - свойство, обеспечивающее постоянную работоспособность цифровых систем // Тр. Института инженеров по электротехнике и радиоэлектронике. - 1978. - Т.66, №10. -С.5-25.

2. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем.-М.: Наука. Физматлит, 1997. - 368с.

3. Богомолов A.M., Салий В.Н. Несколько задач из алгебры дискретных систем // Методы и системы технической диагностики. — Саратов, 1993. - Вып.10. - С.32-34.

4. Гессель М., Согомонян Е.С. Построение самотестируемых и самопроверяемых комбинационных устройств со слабонезависимыми выходами // Автоматика и телемеханика. - 1992. - №8. - С. 150-160.

5. Горелов О.И. Поиск дефектов в сложных технических системах методами анализа диагностических графов. Вычисление дефектных компонент // Автоматика и телемеханика. — 1987. - № 10. - С.155-165.

6. Горелов О.И. Поиск дефектов в сложных технических системах методами анализа диагностических графов. Вычисление дефектных компонент и межкомпонентных связей // Автоматика и телемеханика. -1989. -№ 9. -С. 148-159.

7. Егорова Д.П. Структура конгруэнций унарной алгебры // Упорядоч. множества и решетки. - Саратов, 1978. - Вып.5. - С. 11-44.

8. Егорова Д.П., Скорняков Л.А. О структуре конгруэнций унарной алгебры // Упорядоч. множества и решетки. - Саратов, 1977. - Вып.4. -С.28-40.

9. Киреева A.B. Конгруэнции турниров // Студенты - ускорению научного прогресса. - Саратов, 1990. - Вып.2. - С.3-5.

Ю.Киреева A.B. Отказоустойчивость в функциональных графах // Упорядоч. множества и решетки. - Саратов, 1995. - Вып.11. - С.32-38.

П.Киреева A.B. О конгруэнциях и автоморфизмах корневых деревьев // Теория полугрупп и ее приложения. - Саратов, 1991. - Вып. 10. — С.37-42.

П.Киреева A.B. О конгруэнциях корневых деревьев // XI Всесоюзная конференция по проблемам теоретической кибернетики: Тезисы докл., 4.1. - Волгоград, 1990. - С.23.

13.Киреева A.B. О некоторых соответствиях между решеткой подавтоматов и решеткой конгруэнций автомата // Упорядоч. множества и решетки. - Саратов, 1991. - Вып.10. - С.51-56.

14.Киреева A.B. Решетка конгруэнций турнира // Студенты - ускорению научного прогресса. - Саратов, 1991. - Вып.З. - С.3-7.

15.Когаловский С.Р., Солдатова В.В. О решетках конгруэнций частичных алгебр . П // Упорядоч. множества и решетки. - Саратов, 1991. - Вып. 10. - С.56-69.

16.Куринной Т.Ч. Об определимости унара конгруэнциями // Изв. вузов. Математика. - 1981. - №3. - С.76-78.

17.Пархоменко П.П. Согомонян Е.С. Основы технической диагностики. М: Энергоиздат, 1981. - 319с.

18.Пархоменко П.П. Компактная форма задания всех неизбыточных маршрутов в орграфе // Автоматика и телемеханика. - 1994. - №5. -С.109-121.

19.Салий В.Н. Универсальная алгебра и автоматы. Саратов: Изд-во Саратовск. Ун-та, 1988. - 72с.

20.Согомонян Е.С. Построение самопроверяемых схем встроенного контроля для комбинационных устройств // Автоматика и телемеханика. - 1974. - №2. - С.121-133.

21.Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. - М.: Радио и связь, 1989. - 207с.

22.Сперанский Д.В. Об одном алгоритме построения обобщенного графа цифрового устройства // Идентификация и моделирование управляющих систем. - Донецк, 1997. - Т.1. - С.44-49.

23.Avizienis A. Fault tolerant computing - An overview // IEEE Computer. -1971,-Vol.4.-P.5-8.

24.Berman J. On the congruence lattices of unary algebras // Proc. Amer. Math. Soc. - 1972. - Vol.36, №1. - P.34-38.

25.Farr E.H. Lattice properties of sequential machines // J. Assoc. Comput. Mach. - 1963. - Vol.10, №3. - P.365-385.

26.Gill A., Flexer R. Periodic decomposition of sequential machines // J. Assoc. Comput. Mach. - 1967. - Vol.15. - P.666-676.

27.Hartmanis J. On the state assignment problem for sequential machines, I // ШЕ Trans. EC-10 (1961).

28.Hayes J.P. A graf model for fault-tolerant computing system // IEEE Trans. Comput. - 1976. - Vol.C-25, №9. - P.875-884.

29.Hayes J.P. Fault tolerants in computers and graphs // Proc. 1st Est. Conf. Graphs and Appl. Tartu - Kaariku, May 12-19,1991. - Tartu, 1993. P.77-89.

30.МаеЫе E., Moritzen K., Wirl K. A graph model for diagnosis and reconfiguration and its application to a fault-tolerant multiprocessor system // IEEE Proc. 16th Symposium on Fault-Tolerant Computing. - 1986. - P.292-297.

31.Preparata F.P., Metze G., Chien P.T. On the connection assignment problem of diagnosable systems // IEEE Trans. Electr. Сотр. 1967. -Vol.EC-16. - P.848-854.

32.Yoely M. Subdirectly irreducible unary algebras // Amer. Math. Monthly. -1967. - Vol.74, №8. - P.957-960.

Результаты диссертации опубликованы в следующих работах:

33.Кабанов М.А. Функциональные конгруэнции ориентированных графов // Упорядоченные множества и решетки. - Саратов, 1995. - Вып.11. -С. 15-23.

34.Кабанов М.А. О конгруэнциях ориентированных графов // Тезисы докладов на XI международной конференции по проблемам теоретической кибернетики. — Ульяновск, 1996. - С.81-82.

35.Кабанов М.А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. — Саратов, 1997. -Вып.1. - С.50-58.

36.Кабанов М.А. Ациклически простые графы // Математика, механика и их приложения: Материалы науч.-практ. конф., Саратов, октябрь 1997г.

- Саратов: Изд-во Сарат. ун-та, 1998. - С.68-69.

37.Кабанов М.А. О конгруэнциях ориентированных графов // Теоретические задачи информатики и ее приложений. - Саратов, 1998.

- Вып.2. - С.37-47.