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

• Автор: Кабанов, Михаил Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Саратов
• Количество страниц: 108 с. : ил.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ
ГЛАВА 1. Конгруэнции ориентированных графов
§1. Основные понятия и теорема о соответствии
конгруэнций
§2. Функциональные конгруэнции
§3. Ациклические конгруэнции
§4. Циклические конгруэнции
§5. Древесные конгруэнции
5.1. Входящие деревья
5.2. Выходящие деревья

ГЛАВА 2. Отказоустойчивость графов
§1. Основные понятия и теорема об оптимальной
1-отказоустойчивой реализации колеса
§2. Оптимальные 1-отказоустойчивые реализации
цепей колес
ЛИТЕРАТУРА

ВВЕДЕНИЕ
За последние десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов дискретной математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, химии и биологии, в теории расписаний и дискретной оптимизации.
Теория графов является существенной частью математического аппарата кибернетики. Этому способствует также тривиальность понятия графа, которое опирается на понятие множества: содержательно граф можно представить в виде объекта, состоящего из двух множеств - вершин и ребер.
Графом (ориентированным графом) называется пара 0 = (У,а), где V - конечное непустое множество, а а - отношение на V. Неориентированным графом называется граф, у которого отношение смежности а антирефлексивно и симметрично.
По мнению Е.С.Согомоняна и Е.В.Слабакова [21], на сегодняшний день решение проблемы технической диагностики, связанной с достижением высоких показателей надежности вычислительных систем, имеет два основных направления. Первое основано на использовании самопроверяемых средств функционального диагностирования. Второе основано на использовании отказоустойчивых избыточных структур. Настоящая работа содержит две главы. Каждая из глав посвящена некоторым аспектам соответствующего направления, которые получают

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

длины р, соединяющий ит с некоторой вершиной таєж*(у/). Так как
сильно связный граф С нетривиален, то степень исхода любой вершины графа О больше нуля и, значит, существует некоторый маршрут (у0,у15
длины р + т, соединяющие и0 с у0 и ит с уи. Так как (й0,ми)е/, то, по определению к , и (у0,ут)елг*, т.е. вершины г0 и Ут из одного к -блока и (у0
Так как множество М; не зависит от і, то далее вместо множеств М,. будем рассматривать множество М
Среди элементов множества М1, очевидно, есть и п, поэтому п есть наибольший общий делитель множества М1.
Перечислим элементы множества М,. По условию граф О содержит цикл Сг. Так как отношение к рефлексивно, то число г входит в М
Рассмотрим в графе О произвольный маршрут (1) еСг)&(а„..,ин гСг)
Вершина ик лежит в одном я-*-блоке с вершиной V є Сг, такой что с1С (и,у)=к. При этом длина части цикла, соединяющей одну вершину с друтой равна | (и,ик)~ к |. А это значит, что число ( {и.ик)-к |, если
оно положительно, входит в М,. Если (іс {и,ик)-к ) = 0, то можно считать, что расстояние от у до ик равно г, а этот случай был рассмотрен ранее. Далее, для любой вершины графа О, не входящей в Сг, найдется маршрут вида (1), содержащий эту вершину. Таким образом, маршруты вида (1) и цикл Сг описывают все множество М,. При этом п = НОД М, = НОД (М и {/-}).□
Теорема 2.4 каждому нетривиальному сильно связному графу сопоставляет некоторое число. Это число характеризует цикличность графа, т.е. это число шагов (дуг) через которое мы попадаем из некоторой