Введение к работе
Актуальность темы. В последние десятилетия значительно расширилась область применения автоматизированных систем в различных областях деятельности человека В связи с этим возникает необходимость в повышенных требованиях надежности Одним из показателей надежности системы является ее отказоустойчивость Согласно Авиженису [16], отказоустойчивость - это свойство системы сохранять полностью свою работоспособность при наличии отказов Для обеспечения отказоустойчивости необходимо вводить в систему избыточные элементы, которые активируются при возникновении отказа
В 1976 году Хейз [19] формализовал понятие отказоустойчивости в терминах теории графов Он рассматривал дискретную систему в виде графа, вершинами которого являются элементы этой системы, а ребра представляют связи между элементами
Расширением «-вершинного графа G называется граф Н с и+1 вершинами такой, что G вкладывается в каждый максимальный подграф графа Н Для любого графа существует по крайней мере одно расширение, называемое тривиальным Это расширение получается соединением исходного графа G с одновершинным графом Хейз выделил из всего множества расширений графа G подмножество оптимальных В качестве критерия оптимальности он предложил минимальность количества ребер в расширении Такие расширения называются минимальными Задача описания минимальных расширений для произвольного графа остается нерешенной и представляется чрезвычайно трудной К настоящему времени в этом направлении получен ряд нетривиальных результатов
Хейз предложил процедуру нахождения одного из минимальных расширений для цикла МБ Абросимов обнаружил еще одну серию минимальных расширений для циклов Им же исследовались вопросы поведения конструкции минимальных расширений относительно операций над графами (см, например, [2,3]) Ряд работ посвящен нахождению минимальных расширений для класса деревьев - связных графов без циклов Так Фаррад и Доусон охарактеризовали минимальные расширения для звездных графов [18] Харари и Хуррум описали минимальные расширения для особого віща деревьев - гусениц [22] М А Кабанов указал одно из минимальных расширений для специального класса деревьев - цепей колес [6] М Б Абросимов нашел [2] минимальные расширения для сверхстройных деревьев особого вида
В 1993 году Харари и Хейз [20] отмечают, что отказать может не только элемент системы, связь между элементами тоже может оказаться поврежденной Поэтом>г они предлагают конструкцию реберных расширений (граф Неп вершинами называется реберным расширением л-вершинного графа G, если G вкладывается в любой граф, полученный из Н удалением одного ребра) Интересные результаты в этом направлении представлены Чоу
и Сю [17], которые рассматривали минимальные реберные расширения графов, представляющих собой решетку
Хотя дискретные системы, которые должны обладать свойством отказоустойчивости, сами по себе считаются достаточно надежными, но все же теоретически возможен отказ более чем одного элемента В связи с этим в 1993 и 1996 годах Харари и Хейз предложили модель соответственно реберных и вершинных ^'-расширений [20,21] Основные направления в этой области посвящены нахождению минимальных реберных fc-расширений для циклов (например, работа [20]) и некоторых классов деревьев (например, работа [23])
В 1996 году МФ Каравай [7] рассматривает вершинную отказоустойчивость, но с другой интерпретацией отказа элементов Если в графовой модели Хейза отказавший элемент удаляется вместе со всеми связями, то МФ Каравай рассматривает отказ элемента как «слипание» связей Им предложено использование теории симметрии для изучения вопросов отказоустойчивости (с учетом особенности рассматриваемых им отказов) дискретной системы
В работе [21] среди нерешенных проблем приводится задача выделения минимальных расширений, в которых добавочная вершина инцидентна всем добавочным ребрам В 2003 году В Н Салий [14] предлагает принципиально новый подход к оптимальности - так называемые неприводимые расширения Неприводимым расширением графа G назьтается такое его расширение Я, что при удалении любого ребра из Н полученный граф не будет расширением для G В рамках проблемы, указанной Харари и Хейзом, В Н Салий предложил конструкцию Т-неприводимого расширения Под Т-неприводимым расширением графа G понимается всякое его неприводимое расширение, полученное из тривиального расширения графа G удалением некоторого числа ребер Новая конструкция является оптимальной и в том смысле, что позволяет сохрашггь исходный граф Еще одним важным свойством предложенной модели является однозначность восстановимости графа по люболгу его Т-неприводимому расширению Заметим, что для нахождения Т-неприводимого расширения в настоящий момент не существует эффективного алгоритма, и переборный алгоритм сравним по сложности вычислений с проверкой графов на изоморфность Процедура же восстановления исходного графа по его Т-неприводимому расширению будет линейной относительно размерности графа, если известны степени всех вершин этого расширения
Все модели оптимальных расширений изначально предлагались для неориентированных графов Однако все они очевидным образом могут быть перенесены на случай ориентированных графов, с естественным усложнением всех задач Так, в 1995 году А В Киреева предложила алгоритм построения минимального расширения для произвольного функционального графа [8] Позже появляются результаты по вершинным и реберным расширениям для ориентированных циклов в работе Сунга, Лина и
других [24] М Б Абросимов в работе [4] описал минимальные расширения транзитивных турниров
В 2005 году конструкция Т-неприводимого расширения была обобщена на случай ориентированных графов в работе [9] В [10] был выделен класс всевозможных ориентации задашгай цепи и составлен каталог всех Т-неприводимых расширений для всех ориентации цепей с числом вершин не более 8 В работах [11-13] решена задача описания всех Т-неприводимых расширений для симметричных ориентации цепей Эти результаты автора в представляелгую работу не включены, так как проблема нахождения Т-неприводимых расширений для ориештгрованных графов -отдельная, не менее сложная задача, чем те, которые рассматриваются в диссертации
Обзор результатов по графовым моделям отказоустойчивости дискретных систем был представлен в докладе [15]
Цель работы. Выделить основные свойства Т-неприводимых расширений графов Рассмотреть Т-неприводимые расширения для связных графов и изучить поведение этой конструкции относительно графовой операции объединения
Научная новизна н выносимые на защиту положения. В работе получены следующие основные результаты
доказаны основные свойства Т-неприводимых расширений, в том числе критерий Т-неприводимости,
составлен каталог всех Т-неприводимых расширений для графов с числом вершин не более 6 и проведен статистический анализ, в том числе и по соотношению между множествами Т-нсприводимых и минимальных расширений,
рассмотрена задача нахождения Т-неприводимых расширений для важнейшего класса связных графов - деревьев, в том числе составлен каталог всех Т-неприводимых расшігоєний для деревьев с числом вершин не больше 10 и получены описания всех Т-неприводимых расширений для некоторых деревьев, таких как пальмы, полные бинарные деревья,
изучены некоторые свойства Т-неприводимых расширений относительно операции объединения графов, в частности, найдено Т-неприводимое расширение для объединения графа с одним из его Т-неприводимых расширений и решена задача нахождения Т-нсприводихМОго расширения для объединения графа без изолированных вершин с вполне несвязным графом,
предложен и обоснован алгоритм построения всех Т-неприводимых расширений для объединений полных графов и дана оценка их количества
Все вышеназванные результаты являются новыми Методы исследования. При решении перечисленных задач применялись методы теории графов, теории дискретных систем, теории вычислительных экспериментов, теории алгоритмов
Достоверность полученных результатов. Все полученные в диссертации теоретические результаты имеют строгое доказательство Кроме того,
достоверность теоретических результатов подтверждают вычислительные эксперименты
Теоретическая и практическая ценность. В работе представлены готовые процедуры построения Т-неприводимых расшіфении для конкретных видов графов Возможно использование предлагаемых результатов при построении оптимальных отказоустойчивых реализаций для дискретных систем, моделируемых графалш
Апробация работы. Результаты представляемой работы обсуждались на научном семинаре кафедры теоретических основ компьютерной безопасности и криптографии (СГУ, 2006 год) и на объединенном семинаре по дискретной математике и математической кибернетике (СГУ, 2007 год) Они докладывались на Межвузовских научных конференциях «Компьютерные науки и информационные технологии» (Саратов, 2004, 2005, 2006 годы), VI Международной конференции «Алгебра и теория чисел современные проблемы и приложения» (Саратов, 2004 год), Федеральной итоговой конференции Всероссийского конкурса на лучшие работы студентов по естественным наукам (Москва, 2004 год), II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт - Петербург, 2006 год), Международных конференциях студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2005, 2006, 2007 годы)
Исследования автора поддержаны грантом РФФИ 05-08-18082 Публикации. Основные результаты опубликованы в работах [А1-А12] Работа [А8] опубликована в издании, включенном в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук»
Структура и объем работы. Работа состоит из введения, трех глав, заключения, библиографии, включающей 37 наименований, и двух приложений Общий объем работы 110 стр
