Графовые модели отказоустойчивости тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АБРОСИМОВ Михаил Борисович

ГРАФОВЫЕ МОДЕЛИ ОТКАЗОУСТОЙЧИВОСТИ

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

АВТОРЕФЕРАТ

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

005545994

13 I ¡АР 20 и

МОСКВА 2013

Работа выполнена на кафедре теоретических основ компьютерной безопасности и криптографии в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Саратовский государственный университет им. Н.Г.Чернышевского»

Официальные оппоненты:

Бредихин Дмитрий Александрович, доктор физико-математических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный технический университет имени Гагарина Ю.А.». профессор.

Сперанский Дмитрий Васильевич, доктор технических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный университет путей сообщения», профессор.

Фомичев Владимир Михайлович, доктор физико-математических наук, профессор, Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский ядерный университет «МИФИ», профессор.

Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л.Соболева Сибирского отделения Российской академии наук

Защита состоится 30 мая 2014 г. в /' ч. 0° мин, на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, ауд. 685.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ им. М.В.Ломоносова.

Автореферат разослан «¿" » УС 2014 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Надежность является важнейшим аспектом при использовании вычислительных систем в критических областях. Движение (Avizienis, 1975) выделил два подхода для повышения надежности (reliability) реальных вычислительных систем: предотвращение ошибок и отказоустойчивость. Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоконадежных компонентов системы. На этом пути можно отметить большие успехи. Время наработки на отказ первых компьютеров измерялось минутами, а современных — годами.

Во втором направлении используется добавление в систему избыточных структур для придания ей дополнительных свойств отказоустойчивости. Понятие отказоустойчивости было определено Авиженисом как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют следующие уровни отказоустойчивости:

1) полная отказоустойчивость — система продолжает работать в присутствии ошибок без существенной потери функциональных свойств;

2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

Некоторое время назад стали рассматривать более общее понятие, чем надежность (reliability), - гарантоспособность (dependability). Под гарантоспособностью понимается комплексное свойство системы предоставлять требуемые услуги, которым можно оправданно доверять. В работе (Avizienis et al., 2004) дается подробная таксономия для гарантоспособности. В частности, надежность является атрибутом гарантоспособности, а отказоустойчивость -одним из средств ее достижения.

Интерпретация отказоустойчивости на языке теории графов представляется достаточно естественным подходом. В данной работе будет исследоваться конструкция минимального вершинного и реберного расширения графов, основанная на идеях формализации понятия полной отказоустойчивости технических систем, предложенных в 1976 г. Хейзом (Hayes, 1976).

Технической системе X сопоставим помеченный граф G(X), вершины которого соответствуют элементам системы X, ребра - связям между элементами, а метки указывают тип элементов. Под отказом элемента технической системы Б

понимается удаление соответствующей ему вершины из графа системы С(Е) и всех связанных с ней ребер.

Говорят, что система Е* является к-отказоустойчивой реализацией системы Е, если отказ любых к элементов системы приводит к графу, в который можно вложить граф системы Е с учетом меток вершин. Построение ¿-отказоустойчивой реализации системы Е можно представить себе как введение в нее определенного числа новых элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры. Следует заметить, что процесс реконфигурации в общем случае (с учетом частичной деградации функциональных возможностей системы) является достаточно сложной процедурой и составляет самостоятельную область исследования. Для нас далее представляет интерес оптимизация ¿-отказоустойчивой реализации.

Пусть в системе Е встречается г различных типов элементов. Очевидно, что любая ее ¿-отказоустойчивая реализация должна содержать не менее к дополнительных элементов каждого типа. Легко видеть, что такого числа дополнительных элементов достаточно для построения ¿-отказоустойчивой реализации системы Е. В самом деле, добавим к элементов каждого типа и соединим их все между собой и с элементами системы Е. Тогда любой отказавший элемент можно будет заменить одним из добавленных элементов соответствующего типа. Далее построенную таким образом ¿-отказоустойчивую реализацию будем называть тривиальной.

¿-отказоустойчивая реализация Е* системы Е, состоящей из г элементов различного типа, называется оптимальной, если система Е* отличается от системы £ на к элементов каждого из г типов системы Е, и среди всех ¿-отказоустойчивых реализаций с тем же числом элементов система Е* имеет наименьшее число ребер.

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

Данный подход впервые был изложен Хейзом в работе (Hayes, 1976). Там же были предложены процедуры построения оптимальной ¿-отказоустойчивой реализации для цепи, цикла и помеченного дерева. Позднее Хейз совместно с Харари обобщил модель на случай отказов связей между элементами, предложив понятие реберной отказоустойчивости (Нагагу, Hayes, 1993). Модель отказоустойчивости, в которой рассматриваются только отказы элементов, было предложено называть вершинной отказоустойчивостью (Нагагу, Hayes, 1996). Последующее расширение модели связано с рассмотрением как отказов элементов, так и отказов связей между ними. Подобная модель называется комбинированной отказоустойчивостью.

А. В. Киреева рассматривала вершинную отказоустойчивость в ориентированных графах (Киреева, 1995). Ею описана вершинная оптимальная 1-отказоустойчивая реализация произвольного функционального графа. Санг и другие (Sung et al., 1998) использовали модель Хейза для нахождения вершинной и реберной оптимальной 1-отказоустойчивой реализации ориентированного цикла.

Иногда рассматривают вершинную отказоустойчивость с несколько иной интерпретацией отказов элементов (например, (Каравай, 1996 ; Каравай, 2000)): отказавший элемент исключается из модели, однако все его связи сохраняются, что приводит к новой системе, в которой каждая пара элементов, связанных с отказавшим, также будет связана.

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

Деревья. Задачу описания оптимальных ¿-отказоустойчивых реализаций деревьев сформулировал Хейз (Hayes, 1976). Там же была предложена вершинная оптимальная 1-отказоустойчивая реализация для полного n-арного дерева с

5

метками. Харари и Хуррум (Нагагу, Khurum, 1995) описали схему построения оптимальной 1-отказоустойчивой реализации деревьев специального вида: гусениц и звездоподобных деревьев. Еще один результат для частного случая гусениц (цепи колес) был получен М. А. Кабановым (Кабанов, 1997). Звездоподобным (сверхстройным) деревьям в работе уделено достаточное внимание, так как они имеют большое практическое значение. Кван и Тойда (Kwan, Toida, 1982) описали схему построения оптимальной 2-отказоустойчивой реализации для полного бинарного дерева с метками. Сложность задачи для общего случая привела к понятию почти оптимальной к-отказоустойчивой реализации (Dutt, Hayes, 1990). Задача нахождения реберной оптимальной fc-отказоустойчивой реализации дерева с метками исследуется в работе (Ku, Hayes, 1996). Определенного успеха удалось добиться С. Г. Курносовой при описании Т-неприводимых 1-расширений полных бинарных деревьев (Курносова, 2006).

Циклы. Задача нахождения оптимальных ¿-отказоустойчивых реализаций циклов впервые была поставлена и решена Хейзом (для отказов элементов в (Hayes, 1976), а для отказов связей между элементами в (Haraiy, Hayes, 1993)). В работе (Нагагу, Hayes, 1996) Харари и Хейз поставили задачу нахождения для циклов оптимальных ¿-отказоустойчивых реализаций, отличных от тех, что были предложены в (Hayes, 1976). Махопадхья и Синха (Mukhopadhyaya, Sinha, 1992) указали первое такое семейство оптимальных 1-отказоустойчивых реализаций циклов. Число работ в этом направлении исчисляется десятками, однако только схемы построения, предложенные Хейзом, Махопадхья и Синхом, позволяют указать оптимальную [-отказоустойчивую реализацию для цикла с любым числом вершин, в том числе и для цикла с четным числом вершин. В работе предлагается новая схема построения оптимальной 1-отказоустойчивой реализации для цикла с любым числом вершин, отличная от всех известных схем.

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

Интересное применение Т-неприводимые расширения нашли в криптографии (Салий, 2003). Расширения графов можно рассматривать в контексте задач реконструкции, когда из заданного графа требуется построить новый граф, обладающий определенными свойствами (Салий, 2008). Многие результаты, полученные при исследовании оптимальных ¿-отказоустойчивых реализаций

6

графов, оказались тесно переплетены с результатами, полученными в рамках «чистой» теории графов. В рамках технической диагностики задача описания оптимальных ¿-отказоустойчивых реализаций рассматривается для графов, являющихся моделями технических систем, что накладывает ограничение на класс графов, представляющих интерес для исследования. Далее конструкция вершинной оптимальной ¿-отказоустойчивой реализации будет рассматриваться как абстрактная конструкция над графами, однако особое внимание будет уделено полезным с практической точки зрения классам графов, таким как звезды и их ориентации, цепи, циклы, звездоподобные (сверхстройные) деревья, турниры.

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

Автор выражает искреннюю благодарность заведующему кафедрой теоретических основ компьютерной безопасности и криптографии Саратовского госуниверситета, профессору Вячеславу Николаевичу Салию за внимание, помощь и поддержку во время исследований.

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

Методы исследований и достоверность теоретических результатов. В

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

Научная новизна и выносимые на защиту положения. Все основные результаты диссертации являются новыми. Укажем наиболее важные из них.

1. Доказана вычислительная сложность задач, связанных с расширениями графов. Установлено, что задача распознавания является ли предъявляемый граф

вершинным или реберным ¿-расширением заданного графа относится к классу МР-сложных задач.

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

3. Описаны все минимальные вершинные 1-расширения графов с числом дополнительных ребер не более 3.

4. Предложены новые семейства минимальных вершинных и реберных 1-расширений для циклов. Доказано, что эти минимальные 1-расширения отличны от других известных семейств Харари-Хейза и Махопадхья-Синха.

5. Найдены минимальные вершинные и реберные ¿-расширения для предполных графов. В случае вершинных ¿-расширений задача решена полностью.

6. Описаны минимальные вершинные и реберные 1-расширения сверхстройных деревьев, для которых число дополнительных ребер минимально возможное.

7. Исследована связь минимальных ¿-расширений ориентированных графов и соответствующих им неориентированных графов (их симметризаций). С помощью полученных результатов описаны минимальные вершинные и реберные ¿-расширения ориентированных звезд и турниров.

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

Апробация работы. Результаты работы докладывались на VI и VIII Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2001 и 2003), Международной конференции «Дискретный анализ и исследование операций» 00011-2004 (Новосибирск, 2004), Б0011-2010 (Алтай, 2010), на Второй международной научно-практической конференции «Исследование, разработка и

применение высоких технологий в промышленности» (Санкт-Петербург, 2006), на Международной научно-методической конференции «Актуальные проблемы математики, механики, информатики» (Пермь, 2006), на XII (Нижний Новгород, 1999), XIV (Пенза, 2005), XV (Казань, 2008) и XVI (Нижний Новгород, 2011) Международных конференциях «Проблемы теоретической кибернетики», на II-ХП Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография» (2002-2013), на Международных научных конференциях «Компьютерные науки и информационные технологии» памяти А.М.Богомолова (Саратов, 2007, 2009, 2012), на Международных конференциях «Дискретная математика, алгебра и их приложения» (Минск, 2009, 2013), на XI Белорусской математической конференции (Минск, 2012), в университете Пьера и Мари Кюри (Париж, Франция, 2012), в Генгском университете (Гент, Бельгия, 2013), на научно-исследовательском семинаре «Дискретная математика и математическая кибернетика» кафедры математической кибернетики Московского государственного университета им. М.ВЛомоносова (Москва, 2013), на научных и учебных семинарах кафедры теоретических основ компьютерной безопасности и криптографии Саратовского государственного университета им. Н.Г.Чернышевского.

Имеются практические внедрения результатов диссертации, которые подтверждаются 7 актами о внедрении.

Материалы диссертации используются в 3 курсах, читаемых автором в Саратовском государственном университете им. Н.Г.Чернышевского.

Результаты исследований использовались в разработке программ для ЭВМ «Универсальный компьютерный тренажерный комплекс» (свидетельство об официальной регистрации программы для ЭВМ № 2004612135 от 17.09.2004 г.) и «Универсальный тренажерный комплекс» (свидетельства о государственной регистрации программы для ЭВМ № 2008610432 от 23.01.2008 г., № 2011611763 от 25.02.2011 г. и № 2012619028 от 05.10.2012), «TKDiff» (свидетельство о государственной регистрации программы для ЭВМ №2012613443 от 11.04.2012), «КИРАС» (свидетельство об официальной регистрации программы для ЭВМ № 2003611900 от 15.06.2004 г.), «КИРАС с функциями коммерческого учета ресурсов и диспетчерского управления» (свидетельство об официальной регистрации программы для ЭВМ № 2007611352 от 28.04.2007 г.) и «Система поддержки и принятия решений КИРАС-А» (свидетельство о государственной регистрации программы для ЭВМ № 2009610352 от 14.01.2009), а также в

9

проектах, реализованных на основе указанных программ для ООО «Сарагговоргсинтез» (г.Саратов), ООО «СНВ» (г.Саратов), ЗАО «Сибур-Химпром» (г.Пермь), ОАО «Уралоргсинтез» (г.Чайковский), ООО «Томскнефтехим» (г.Томск), ОАО «Новокуйбьпневский НПЗ» (г.Новокуйбышевск) и ОАО «РЖД» (г.Москва).

Работа была поддержана грантом РФФИ 05-08-18082.

Публикации. По теме диссертации автором опубликовано 74 научные работы, включая 1 монографию, 4 свидетельства о государственной регистрации программы для ЭВМ, 68 печатных работ в журналах и сборниках, из которых 18 включены в список научных изданий, рекомендованных ВАК РФ для опубликования результатов диссертаций. Материалы диссертации использованы в 1 учебном пособии.

Личный вклад автора. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, содержащих в совокупности 18 параграфов, заключения, списка использованных источников, включающего 180 источников, и приложения. Общий объем составляет 269 страниц, включая 74 рисунка и 8 таблиц. Содержание работы

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

В первой главе приводятся основные понятия теории графов. Рассматриваются модели отказоустойчивости как средство обеспечения надежности гарантоспособных систем. Вводятся соответствующие графовые модели. Основные определения по теории графов используются согласно (Богомолов, Салий, 1997) или (Харари, 2009).

Результаты главы 1 опубликованы в работе [1].

Граф G* = (V*, а) называется вершинным (реберным) к-расширением (к — натуральное) графа G = (V, а), если граф G вкладывается в каждый граф, получающийся из графа G* удалением любых его к вершин (ребер). Очевидно, что ¿-расширение должно содержать не менее к дополнительных элементов - вершин

или ребер соответственно. Для построения вершинного ¿-расширения этого оказывается и достаточно: если к произвольному графу Б добавить ¿ вершин и соединить их ребрами между собой и с остальными вершинами графа б, то построенный граф, как можно заметить, будет являться вершинным (и реберным) ¿-расширением графа С. Такое расширение называется тривиальным к-расши-ренигм. Нетрудно показать, что выполняется

ТЕОРЕМА 1.3.1. Вершинное к-расширение любого графа является и его реберным к-расширением.

Вершинное (реберное) к-расширение (к - натуральное) графа С = (V, сг) называется неприводимым, если никакая его собственная часть не является вершинным (реберным) ¿-расширением графа б.

Граф С," называется точным вершинным (реберным) к-расширением графа Сг, если любой граф, получающийся удалением произвольных ¿ вершин (ребер) графа б*, изоморфен графу С.

Граф С* = (V*, а) называется минимальным вершинным к-расширением п-вершинного графа б = (V, а), если выполняются следующие условия:

1) граф <3* является вершинным к-расширением графа <7;

2) граф б* содержит п + к вершин, то есть |У*| = |У| + к;

3) а имеет минимальную мощность среди всех графов, удовлетворяющих условиям 1) и 2).

Граф С* = (V*, а ) называется минимальным реберным к-расширением п-вершинного графа С = (У, а), если выполняются следующие условия:

1) граф Б* является реберным ¿-расширением С;

2) граф Б" содержит п вершин, то есть \У*\ = \У\;

3) а имеет минимальную мощность среди всех графов, удовлетворяющих

условиям 1) и 2).

В определении минимального вершинного 1-расширения в первую очередь минимизируется количество вершин. Это означает, что могут существовать расширения графов (как вершинные, так и реберные), которые имеют меньшее количество ребер, чем минимальные расширения. С практической точки зрения вершины обычно моделируют более дорогие компоненты, чем ребра: например,

процессоры или компьютеры по сравнению с соединяющими их линиями. Поэтому основное внимание уделяется преимущественно именно минимальным расширениям. Однако можно поменять местами и поставить на последнее место требование минимизации числа вершин или вообще убрать его — такие расширения назовем экстремальными.

Граф = (V*, а ) называется экстремальным вершинным (реберным) к-рас-ширением графа С = (V, сё), если среди всех вершинных (реберных) ¿-расширений графа О граф б* имеет минимально возможное число ребер.

Иногда на расширения накладываются и другие требования, обусловленные практическими потребностями, например, ограничение на максимальную степень вершины.

Во второй главе рассматриваются вершинные расширения графов.

Результаты главы 2 опубликованы в работах [1-3,8,9,11,14,16-19].

Пусть С - некоторый граф, а Н — его минимальное вершинное ¿-расширение. Обозначим через (<7)** результат операции получения минимального вершинного ¿-расширения графа (7. Тогда, если граф С/ имеет единственное минимальное вершинное ¿-расширение, то (б)*4 = Я. В противном случае результат операции получения минимального вершинного ¿-расширения считается неопределенным для графа в. Будем использовать для операции получения минимального вершинного 1-расширения обозначение (б)*.

Граф может иметь несколько неизоморфных неприводимых вершинных к-расширений с различным числом ребер. Граф также может иметь неизоморфные минимальные вершинные ¿-расширения, однако число ребер у них будет одинаковым. Заметим, что число ребер минимального вершинного ¿-расширения графа не более чем у его тривиального ¿-расширения, то есть

|ог*| < |ог|++ • Будем говорить, что минимальное вершинное ¿-расширение содержит |а*|-|а| дополнительных ребер. Обозначим через ес(С, к) число дополнительных ребер минимального вершинного ¿-расширения графа б:

0<ес(С,к)<\у\к + '~к.

Для любого графа, кроме вполне несвязного, количество дополнительных ребер больше 0. Далее будут описаны графы, у которых

12

О < ес(ХЗ,1) < 3.

Общая схема рассуждений для доказательства того, что граф С* является минимальным вершинным ¿-расширением графа б:

1. Показать, что граф С* является вершинным ¿-расширением графа б.

2. Показать, что не существует вершинного ¿-расширения графа б с меньшим числом ребер, чем у графа С*.

В некотором смысле доказательство того, что граф С? является неприводимым вершинным ¿-расширением графа О, несколько проще:

1. Показать, что граф б* является вершинным ¿-расширением графа й.

2. Показать, что в графе б* нет ребра {м, у}, такого, что граф в* - {и, у} является вершинным ¿-расширением графа С.

На шаге 2 достаточно исследовать только части данного графа.

Леммы 2.1.1-2.1.5 о свойствах минимальных вершинных ¿-расширений используются почти во всех доказательствах работы.

ЛЕММА 2.1.1. Минимальное вершинное к-расширение графа без изолированных вершин не содержит вершин со степенью ниже к + 1.

ЛЕММА 2.1.2. Пусть наибольшая из степеней вершин графа <7 есть .у, и в точности т вершин имеют такую степень, тогда минимальное вершинное к-рас-ширение графа С содержит, по крайней мере, ¿ + т вершин степенью не ниже 5.

ЛЕММА 2.1.3. Если максимальная степень вершины графа б есть ¿>0, то его минимальное вершинное к-расширение б* содержит не менее кс1 дополнительных ребер.

ЛЕММА 2.1.4. Если минимальная степень вершины графа б есть с1>0, то его минимальное вершинное к-расширение б* не содержит вершин степени ниже с1 + к

ЛЕММА 2.1.5. Если максимальная степень вершины минимального вершинного 1-расширения графа есть (1, то число дополнительных ребер в расширении не меньше <1.

С помощью лемм легко аналитически установить вид минимальных вершинных ¿-расширений для некоторых классов графов.

ТЕОРЕМА 2.1.1. Минимальное вершинное к-расширение, причем единственное с точностью до изоморфизма, полного п-вершинного графа Кп есть полный (п + к)-вершинный граф К^ь то есть справедливо соотношение:

ТЕОРЕМА 2.1.2. Минимальное вершинное k-расширение, причем единственное с точностью до изоморфизма, вполне несвязного п-вершинного графа Оп есть вполне несвязный (п + к)-вершинный граф 0П¥к, то есть справедливо соотношение: (0„)*1 = Оп+к.

Заметим, что минимальные вершинные ¿-расширения и полного, и вполне несвязного графов являются также их точными вершинными и Т-неприводимыми ¿-расширениями.

ТЕОРЕМА 2.13 (Hayes, 1976). Минимальное вершинное 1-расширение п-вершинной цепи Р„ есть (п + 1)-вершинный цикл С„+1.

ТЕОРЕМА 2.1.5 (Hayes, 1976). Для любого натурального к минимальное вершинное к-расширение (п+1)-вершинного цикла Сп+1 есть минимальное вершинное (¿+1 ^-расширение п-вершинной цепи Р„ и наоборот.

В четвертом параграфе будет показано, что циклы имеют в общем случае более одного минимального вершинного 1-расширения, поэтому и цепи в общем случае имеют более одного минимального вершинного 2-расширения. Совершенно аналогично теоремам 2.1.3 и 2.1.4 можно доказать утверждение о Т-неприводимом 1-расширении цепи.

ТЕОРЕМА 2.1.6. Единственным с точностью до изоморфизма Т-неприводимым 1-расширением п-вершинной цепи Рп является (п + 1 )-вершинный цикл С„+1.

Для цикла, также как и для любого другого однородного графа, конструкция Т-неприводимого 1-расширения не представляет особенного интереса, так как всегда совпадает с тривиальным 1-расширением.

ТЕОРЕМА 2.1.7. Единственным с точностью до изоморфизма Т-неприводимым 1-расширением однородного п-вершинного графа является тривиальное 1-расширение.

Заметим, что вопрос о Т-неприводимом ¿-расширении при ¿ > 1 не является столь тривиальным. Так, например, цикл С4 имеет Т-неприводимым 2-расши-

рением граф вида 02 + С4, а Т-неприводимым З-расширением - тривиальное 3-расширение.

Интересно было бы описать графы, которые имеют минимальное вершинное 1-расширение с одним дополнительным ребром, двумя и т.д. Уже для трех дополнительных ребер эта задача оказывается сложной. Для связных графов минимальное вершинное 1-расширение содержит не менее 2 дополнительных ребер, поэтому только несвязные графы могут иметь минимальное вершинное 1-расширение с одним дополнительным ребром.

ТЕОРЕМА 2.1.8. Графы со степенным множеством {1,0} и только они имеют минимальное вершинное 1-расширение, которое отличается на одно дополнительное ребро, причем это расширение единственно с точностью до изоморфизма.

ТЕОРЕМА 2.1.9. Среди связных графов только цепи имеют минимальное вершинное 1-расширение, которое отличается на два дополнительных ребра, причем это расширение единственно с точностью до изоморфизма.

ТЕОРЕМА 2.1.10. Среди несвязных графов без изолированных вершин только графы вида Р„ и и... и Ся+1 при п > 1 имеют минимальное вершинное 1-расширение, которое отличается на два дополнительных ребра, причем это расширение имеет вид и Сл+1 и... и Сл41 и оно единственно с точностью до изоморфизма.

Замечание.В теоремах 2.1.9 и 2.1.10 минимальные вершинные 1-расши-рения являются и точными вершинными 1-расширениями.

ТЕОРЕМА 2.1.11. Связные графы, имеющие минимальные вершинные \-pac-ширения с тремя дополнительными ребрами, могут иметь только следующий вид:

1) полный граф

2) графы с вектором степеней вида (3,...,3,2,2,2), имеющие точное вершинное \-расширение;

3) графы с вектором степеней (3,3,3, ...,3,2,...,2,1) особого вида.

Замечание. Полученные результаты удалось перенести и на

ориентированные графы [18, 19]. Описание графов, минимальное вершинное 1-расширение которых отличается на 4 и более дополнительных ребер, приводит к рассмотрению слишком большого числа случаев. Интересной представляется задача описания графов, для которых минимальным вершинным 1-расширением

является тривиальное 1-расширение. Такие графы существуют, например, почти все предполные графы имеют единственное минимальное вершинное ¿-расширение, которым является тривиальное ¿-расширение (см. параграф 2.5).

Интересно было бы установить связь конструкции минимального вершинного ¿-расширения с алгебраическими операциями над графам, а именно: если известны все минимальные вершинные ¿-расширения графов О] и С2, то можно ли аналитически указать минимальное вершинное ¿-расширение для графов, являющихся дополнениями и Сг или графов С\ + Сг и О, иОг?

Для изучения связи конструкции минимального вершинного ¿-расширения и операции дополнения графа сформулируем общую постановку задачи.

Задача .Дан граф й и все его минимальные вершинные к-расширения. В каком случае дополнение одного га минимальных вершинных к-расширений графа О является минимальным вершинным к-расширением дополнения графа С?

Будем говорить, что граф С обладает свойством дополнительности к-расширения, если дополнение хотя бы одного его минимального вершинного ¿-расширения является минимальным вершинным ¿-расширением дополнения графа О. При ¿ = 1 будем говорить, что граф обладает свойством дополнительности расширения. Заметим, что если граф обладает свойством дополнительности ¿-расширения, то и его дополнение также обладает этим свойством.

Нетрудно видеть, что графы, обладающие свойством дополнительности к-расширения, существуют. Рассмотрим полный п-вершинный граф Кп и его дополнение - вполне несвязный п-вершинный граф Оп. При любом ¿>0 эти графы имеют по теоремам 2.1.1 и 2.1.2 единственные с точностью до изоморфизма минимальные вершинные ¿-расширения: Кп+к для К„ и Оп+* для Оп, которые являются дополнительными графами. Далее этот случай будем называть тривиальным и не будем больше им интересоваться.

ТЕОРЕМА 2.1.15 (Критерий существования нетривиального решения задачи). Для того чтобы граф С обладал свойством дополнительности расширения, необходимо и достаточно, чтобы граф О имел степенное множество вида {Ь,Ь - 1}, причем число вершин степени Ь- 1 в точности равнялось Ь, а его минимальное вершинное 1-расширение было однородным графом порядка Ь. При этом и граф С, и его дополнение имеют единственные с точностью до

изоморфизма минимальные вершинные \-расширения, поэтому справедлива запись: (G* )'= (G')'.

ТЕОРЕМА 2.1.16. При к > 1 только полный и вполне несвязный графы обладают свойством дополнительности к-расширения.

Понятие точного вершинного ¿-расширения было введено Харари и Хейзом в работе (Нагагу, Hayes, 1996). Там же приводятся следующие примеры графов, обладающих точным вершинным ¿-расширением: минимальное вершинное ¿-расширение полного и-вершинного графа Кп - полный (л + ¿)-вершинный граф Кп+к -является его точным вершинным ¿-расширением; (п + 1)-вершинный цикл С„+1 является точным вершинным 1-расширением для и-вершинной цепи Р„. Далее в работе (Нагагу, Hayes, 1996) Харари и Хейз ставят вопрос описания точных вершинных ¿-расширений графов. Из результатов, полученных Раджави и Розенталем (Radjavi, Rosenthal, 1972), можно сделать вывод, что для неориентированных графов никакой граф кроме Оп и Кп не может быть точным вершинным ¿-расширением при ¿>1. Для ориентированных графов ситуация оказывается более интересной, это подробнее рассматривается в параграфе 2.7. Неожиданным является обнаруженное в ходе вычислительного эксперимента совместно с А.А.Долговым и описанное затем в работе (Долгов, 2010) семейство турниров, которое обладает особым свойством. Неориентированный граф может иметь точное вершинное ¿-расширение либо только при ¿=1, либо при всех натуральных значениях ¿ (полные и вполне несвязные графы). Турниры из описанного А. А. Долговым семейства имеют точное вершинное 1- и 2-расши-рение, но не имеют точного вершинного ¿-расширения при ¿ > 2.

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

ТЕОРЕМА 2.1.17. Граф G тогда и только тогда имеет точное вершинное k-расширение, когда он обладает свойством дополнительности к-расширения.

Следствием из теорем 2.1.15, 2.1.16 и 2.1.17 является:

ТЕОРЕМА 2.1.18. Если п-вершинный граф G имеет точное вершинное к-расширение G*, то при п > 1 граф G* является единственным с точностью до изоморфизма минимальным вершинным к-расширением графа G.

Заметим, что если бы существовал граф, имеющий неизоморфные точные вершинные 1-расширения, то он не был бы вершинно реконструируемым, то есть его нельзя было бы с точностью до изоморфизма восстановить по списку максимальных подграфов. Теорема 2.1.18 сформулирована для неориентированных графов, а для орграфов подобный результат пока неизвестен. Удалось показать, что все известные семейства орграфов, имеющих точные вершинные 1-расширения, удовлетворяют теореме 2.1.18. Более того, все семейства Стокмейера нереконструируемых орграфов (Stockmeyer, 1981) не являются точными вершинными 1-расширениями.

ТЕОРЕМА 2.1.19. Граф G является точным вершинным 1-расширением тогда и только тогда, когда он является вершинно-симметрическим.

Таким образом, всякий вершинно-симметрический граф является точным вершинным 1-расширением, однако не всякий такой граф является точным реберным 1-расширением. На

Рис. 2.1.13. Графы ТВ-IP: не являющий- Рис" 2ЛЛЗ-а приведен

ся (а) и являющийся (б) ТР-1Р минимальный по числу вершин

вершинно-симметрический граф, не являющийся точным реберным 1-расширением. Интересно, что этот граф также является минимальным вершинным 1-расширением цикла С; и минимальным реберным 1-расширением цикла Се (см. параграфы 2.4 и 3.4). На рис. 2.1.13, б изображено еще одно точное вершинное 1-расширение, которое является и точным реберным 1-расширением, — граф К^ъ- Заметим, что граф является минимальным реберным 1-расширением цикла С6, однако не является минимальным вершинным 1-расширением цикла С5.

В параграфе 2.2 доказывается, что задача распознавания вершинного ¿-расширения является NP-полной, а также рассматриваются оптимизационные варианты задачи.

ЗАДАЧА: ВЕРШИННОЕ ¿-РАСШИРЕНИЕ УСЛОВИЕ. Даны графы G = (V,a)nH= (С/, fi).

ВОПРОС. Верно ли, что граф G является вершинным ¿-расширением графа W

ТЕОРЕМА 2.2.1. Задача ВЕРШИННОЕ к-РАСШИРЕНИЕ является NP-полной.

В параграфе 23 исследуются неизоморфные минимальные вершинные расширения. Все графы с числом вершин меньше 5 имеют единственное с точностью до изоморфизма минимальное вершинное 1-расширение. Описываются минимальные по числу вершин и ребер графы с неизоморфными минимальными вершинными 1-расширениями.

В параграфе 2.4 рассматриваются минимальные вершинные 1-расширения циклов.

В работе (Hayes, 1976) Хейз предложил процедуру для построения минимального вершинного ¿-расширения цикла. В работе (Harary, Hayes, 1996) Харари и Хейз поставили вопрос о существовании минимальных вершинных 1-расширений, неизоморфных минимальным вершинным 1-расширениям, предложенным ранее Хейзом. Расширениям циклов посвящено достаточно много работ. В этом параграфе рассматриваются основные известные схемы построения минимальных вершинных 1-расширений циклов и предлагается новая схема.

Из результатов Хейза следует, что минимальное вершинное 1-расширение п-вершинного цикла имеет вектор степеней (4, 3") при четном п и (3"+1) при нечетном п. Это представляет большой интерес, так как известны алгоритмы, которые позволяют относительно эффективно строить кубические графы (Brinkmann, 1996 ; Brinkmann, 2011). С помощью этих алгоритмов удалось построить все минимальные вершинные и реберные 1-расширения циклов с числом вершин до 26.

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

Результаты, полученные Хейзом, позволяет строить минимальное вершинное 1-расширение для цикла с любым числом вершин. Таким же свойством обладает и

семейство, описанное в работе (МикЬорасШуауа, БтЬа, 1992). В работе описывается новое семейство, полученное автором.

ТЕОРЕМА 2.4.7. Гамтьтоновы графы, изображенные на рис. 2.4.9, представляют собой минимальные вершинные 1-расширения п-вершинного (и > 3) цикла при п четном (рис. 2.4.9, а)ип нечетном (рис. 2.4.9, б).

У4 у(„+1)/2-| %+т

а б

Рис. 2.4.9. Минимальные вершинные 1-расширения циклов

Доказывается, что это семейство отлично от схем Хейза и Махопадхья-Синха (теоремы 2.4.8,2.4.9). Как следствие получается

ТЕОРЕМА 2.4.10. Любой цикл Сп при п > 5 имеет, по крайней мере, два неизоморфных минимальных вершинных 1-расширения.

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

Граф, каждый максимальный подграф которого является гамильтоновым, называется гипоциклическим. Негамильтонов граф, каждый максимальный подграф которого является гамильтоновым, называется гипогамильтоновым.

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

Оказалось, что граф Петерсена является минимальным вершинным 1-расширением 9-вершинного цикла. Следовательно, среди циклов с числом вершин

меньшим 10 только 9-вершинный цикл имеет негамильтоново минимальное вершинное 1-расширение.

Параграф 2.5 посвящен минимальным вершинным ¿-расширениям предполных графов.

Назовем предполным граф вида К\ + С, где б — произвольный граф. В предполном графе есть хотя бы одна вершина, смежная со всеми остальными. Количество предполных графов с заданным числом вершин достаточно велико.

Утверждение. Число всех неизоморфных п-вершинных предполных графов равно числу всех неизоморфных (и — \)-вершинных графов.

Для предполных графов удалось полностью решить задачу описания всех минимальных вершинных ¿-расширений при любом натуральном к. Независимо аналогичный результат был представлен в работе (С1юис1ит, Sivagumnathan, 2000). Оказывается, что почти все предполные графы имеют единственное с точностью до изоморфизма минимальное вершинное 1-расширение, которым является тривиальное 1-расширение.

ТЕОРЕМА 2.5.2. Относительно предполных графов справедливы следующие утверждения.

1. При четном п и любом натуральном к каждый п-вершинный предполный граф С имеет единственное с точностью до изоморфизма минимальное вершинное к-расширение — тривиальное к-расширение.

2. При нечетном п:

а) при четном к число минимальных вершинных к-расширений предполного

графа О в точности равно числу неизоморфных минимальных вершинных (к — 1)-расширений О, причем каждое из минимальных вершинных к-расширений графа С есть тривиальное 1-расширение соответствующего минимального вершинного (к— Х)-расширения О;

б) при нечетном к:

0 если предполный граф С является частью графа Спр\ и отличается от него на т ребер, то

— при к < 2т — 1 граф С имеет единственное с точностью до изоморфизма минимальное вершинное к-расширение — тривиальное к-расширение;

— при к = 2т — 1 граф И имеет два с точностью до изоморфизма минимальных вершинных к-расширения: тривиальное к-расши-рение и граф /гп+ь„+Ь2,-

— при к > 2т — 1 граф G имеет единственное минимальное вершинное к-расширение - граф /?„+(;,„+*>2/ м) любой другой предполный граф G имеет единственное минимальное вершинное к-расширение, являющееся тривиальным к-расширением.

В заключении параграфа исследуется гипотеза, высказанная автором в 2001 году при исследовании связи конструкции вершинного расширения и алгебраической операции соединения графов.

Пусть G — произвольный граф, a G* - некоторое его минимальное вершинное 1-расширение. Было высказано предположение, что граф вида G + G* +...+G* = G + (G')m всегда имеет единственное минимальное вершинное 1-расширение, и оно может быть представлено в виде G* + G' +...+G' = (G*)m+I, то есть справедлива запись: (G+G* +...+ G*)* -G* +G' + ...+G*.

Удалось доказать, что такое утверждение справедливо для почти всех предполных графов (теорема 2.5.7), однако в общем утверждение выполняется не для всех графов. Теорема 2.5.5 описывает семейство графов, для которых минимальное вершинное 1-расширение графов вида G+G" имеет вид отличный от <а+(Т, теорема 2.5.6 описывает семейство графов, для которых графы вида G+G* имеют два неизоморфных минимальных вершинных 1-расширения.

В параграфе 2.6 исследуются минимальные вершинные 1-расширения деревьев. Класс деревьев является одним из наиболее интересных классов графов с теоретической точки зрения. На практике также часто возникают задачи, связанные с системами, представимыми деревьями. С практической точки зрения наибольший интерес представляют звездообразные, или сверхстройные деревья и, в частности, сами звезды.

В работе (Hayes, 1976) отмечается важность задачи определения минимального вершинного 1-расширения для деревьев. В той же работе была предложена процедура построения минимального вершинного 1-расширения для одного частного случая — дерева с метками. Кван и Тойда (Kwan, Toida, 1982) предложили конструкцию минимального 2-расширения для симметричного неоднородного дерева (вершины равноудаленные от корня имеют одинаковые метки). Для звезд полное описание минимальных вершинных 1-расширений было найдено в (Farrag, Dawson, 1989). Харари и Хуррум (Нагагу, Khurum, 1995) предложили схему построения минимальных вершинных 1-расширений для двух частных случаев деревьев: «гусениц» и звездоподобных деревьев. М. А. Кабанов в

(Кабанов, 1997) предложил процедуру построения для одного частного случая дерева без меток - «цепи колес» - объединение и-вершинных звездных графов («колес») с отождествлением вершин таким образом, что центры колес образуют цепь. В той же работе указывается, что цепи колес могут иметь неизоморфные минимальные вершинные расширения, а также приводится соответствующий пример. В общем виде задача построения минимального вершинного ¿-расширения дерева (с метками или без) остается нерешенной. В работе (Dutt, Hayes, 1990) Дат и Хейз вводят понятие «почти оптимального минимального вершинного 1-расширения» и предлагают процедуру его построения для дерева с метками или без. С. Г. Курносовой удалось описать Т-неприводимые расширения полных бинарных деревьев (Курносова, 2006). Приводимые далее результата позволяют построить минимальное вершинное 1-расширение еще для одного частного случая дерева - сверхстройного дерева.

Звезда является частным случаем предполного графа и может быть записана в виде Кт + Оп, где Оп - вполне несвязный граф. В работе (Farrag, Dawson, 1989) рассматривалась отказоустойчивость систем с выделенным сервером, который связан с клиентами. Клиенты между собой не связываются. Очевидно, что графом такой системы будет являться звезда.

Теоремы 2.6.1 и 2.6.2 дают полное описание минимальных вершинных к-расширений звезд как следствия результатов параграфа 2.5.

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

На сверхстройное дерево можно смотреть как на объединение цепей с общей концевой вершиной. При этом дерево можно закодировать вектором, состоящим из длин цепей в порядке невозрастания: (шь т*)> где т\ >...>тк. Очевидно, что такое кодирование сверхстройных деревьев при к> 2 является взаимно однозначным.

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

485. В случае если к одному модулю сбора информации подключается несколько таких линий, то граф такой системы будет представлять собой сверхстройное дерево [4, 6].

Через ес(С) обозначается количество дополнительных ребер минимального вершинного 1-расширения графа С.

Основной результат параграфа может быть сформулирован следующим образом. Для произвольного сверхстройного дерева Гсправедливо неравенство:

к+\<ес(Т)<к + р + \

>

где р - число сложных вершин дерева Г. Вершина Уу сверхстройного дерева Т

называется сложной, если среди длин цепей дерева Т нет цепи длины у - 1 или Щ -/

Далее в параграфе описываются деревья, на которых достигается нижняя оценка. С практической точки зрения наибольший интерес представляют сверхстройные деревья, минимальные вершинные 1-расширения которых имеют вектор степеней вида ((к + 1)2,2т+к). Теорема 2.6.6 даёт полное описание таких сверхстройных деревьев.

ТЕОРЕМА2.6.6.Пусть Т — сверхстройное дерево вида (т^.....т*) ик>2.

Дерево Т тогда и только тогда имеет минимальное вершинное 1-расширение с к + 1 дополнительным ребром и вектором степеней ((к + 1)2,2т+к), когда выполняется условие

(VI = 1....Д : т, > 1) (V/ = 2,...,/71,) (31 < / < £) (т, = ./-IV т, = т, -]).

Необходимо заметить, что в работе (Нагагу, КТшгит, 1995) доказывается утверждение, что минимальное вершинное 1-расширение сверхстройного дерева с к цепями и р сложными вершинами содержит в точности к + р +1 дополнительных ребер.

При р = 0 это утверждение совпадает с теоремой 2.6.6. Однако при р> О схема доказательства в работе (Нагагу, Югигат, 1995) исследует вариацию вершинного 1-расширения с вектором ((к + 1)2,2т+к). Пусть - сложная вершина, тогда предлагается добавить ребро из вершины старшей степени в вершину Далее авторы статьи утверждают, что построенный граф будет являться минимальным вершинным 1-расширением заданного сверхстройного дерева. Приводится контрпример к утверждению Харари-Хуррума.

Так, сверхстройное дерево (5,1,1) имеет одну сложную вершину, но имеет единственное минимальное вершинное 1-расширение вида 0?,Ъ2,2т*к~2), отличающееся на 4 дополнительных ребра.

Сверхстройное дерево (3,2,2) также имеет одну сложную вершину, но имеет 2 минимальных вершинных 1-расширения вида (к2,32,2т+к'2) и одно вида ((к + 1),к,3,2т*к~'), отличающиеся на 4 дополнительных ребра.

Наконец, сверхстройное дерево (4,3,2) имеет одну сложную вершину, но имеет 4 минимальных вершинных 1-расширения вида (к2,32,2т+к~2), отличающиеся на 4 дополнительных ребра.

Еще один интересный пример представляет собой сверхстройное дерево (5,2,2). Можно заметить, что оно имеет 2 сложные вершины, но его 37 минимальных вершинных 1-расширений отличаются на 5, а не на 6 дополнительных ребер. Аналогичная ситуация с деревьями (6,1,1) или (3,3,2), у которых также по две сложные вершины, но минимальные вершинные 1-расширения отличаются на 5 дополнительных ребер.

В параграфе 2.7 рассматриваются результаты по минимальным вершинным ¿-расширениям орграфов.

Леммы 2.1.1-2.1.5 также могут быть применены к орграфам. Дополнительно формулируются вспомогательные леммы, специфические для орграфов.

ЛЕММА 2.7.1. Если минимальная из полустепеней исхода (захода) вершин графа О есть й> О, то его минимальное к-расширение не содержит вершин с полустепенью исхода (захода) ниже <1 + к.

ЛЕММА 2.7.2. Если орграф имеет 5 петель, то его вершинное к-расширение имеет не менее к + $ петель.

Далее доказывается лемма, которая устанавливает интересную связь между минимальными вершинными ¿-расширениями неориентированных и ориентированных графов. Эта лемма и следствия из нее позволяют перенести многие результаты от неориентированных графов к их ориентациям. Напомним, что симметризацией ориентированного графа С = (У,аг) называется неориентированный граф б = (У,а*), получающийся заменой дуг ребрами и удалением петель:

ЛЕММА 2.7.3. Пусть й' - минимальное вершинное к-расширение орграфа в. Тогда симметризация орграфа С' является вершинным к-расширением симметризации орграфа б.

Следствие 1. Число дополнительных дуг минимального вершинного к-расши-рения орграфа О не менее числа дополнительных ребер минимального вершинного к-расширения симметризации орграфа О.

Следствие 2. Пусть граф О* является минимальным вершинным к-расширением графа С, диграф Н есть некоторая ориентация графа О, а диграф Н* есть некоторая ориентация графа О*. Тогда если Н* является вершинным к-расширением диграфа Н, то Н* является и минимальным вершинным к-расширением диграфа Н.

Для изучения точных вершинных расширений орграфов имеет место

ТЕОРЕМА 2.7.2. Пусть С" - точное вершинное к-расширение орграфа в. Тогда симметризация О* является точным вершинным к-расширением симметризации О.

Теорема 2.7.2 дает способ получения точных вершинных расширений орграфов заданием ориентации ребер соответствующих точных неориентированных расширений. Для неориентированных графов было показано, что дополнение графа, имеющего точное вершинное ¿-расширение, также имеет точное вершинное ¿-расширение. Аналогичное утверждение справедливо и для орграфов (теорема 2.7.3). Обратным орграфом, или обращением орграфа С = (У,а) называется орграф Я=(У,Д), получающийся заменой ориентации всех дуг С: /? = «"' = {(и, г)е V хУ: (у,м)е а].

ТЕОРЕМА 2.7.4. Пусть Б' — точное вершинное к-расширение орграфа б. Тогда обращение б* является точным вершинным к-расширением обращения б.

Очевидно, что точное вершинное ¿-расширение графа с числом вершин большим 1 является и его минимальным вершинным ¿-расширением. Для неориентированных графов точное вершинное ¿-расширение в этом случае и единственно. Для ориентированных графов в общем случае это не так. Турнир с петлями или без имеет два минимальных вершинных

является точным (рис. 2.7.3): циклическую и

А А

Рис. 2.7.3. Турнир Т2 и два его точных вершинных 1-расширения

Для точных вершинных 1-расширений прослеживается интересная связь с вершинной реконструируемостью. Так, если граф имеет более одного точного вершинного 1-расширения, то он не является реконструируемым. Для неориентированных графов гипотеза Келли-Улама утверждает реконструируемость всех графов с числом вершин больше 2. В теореме 2.1.18 доказывается, что все неориентированные графы с числом вершин больше 1 имеют единственное с точностью до изоморфизма точное вершинное 1-расширение. Совместно с А.А.Долговым были проверены все известные семейства нереконструируемых орграфов (БЮсктеуег, 1981). Оказалось, что эти орграфы не являются точными вершинными 1-расширениями. Это позволяет высказать гипотезу, что теорема 2.1.18 справедлива и для орграфов с числом вершин больше 2.

Для орграфов удалось найти еще одно семейство графов, которые имеют точные вершинные ¿-расширения при любом натуральном к.

ТЕОРЕМА 2.7.6. Единственным минимальным вершинным к-расширением транзитивного турнира Тп при п > 2 является транзитивный турнир Тп+к. Причем это расширение является и его точным вершинным к-расширением.

Доказанная теорема означает, что кроме полных и вполне несвязных графов существует еще одно бесконечное семейство графов, имеющих точные вершинные ¿-расширения при любом натуральном к. А. А. Долгову удалось доказать, что других семейств не существует. Однако оказалось, что существуют орграфы, которые имеют точное вершинное ¿-расширение только при к = 1 и при к = 2 (Долгов, 2010).

Рассмотрим р-вершинный граф С = (V, а), где р - простое и р > 2. Пусть

V = {у0, VI.....} - множество вершин С. Из вершины V,- в вершину Vj есть дуга

только в том случае, когда (/ — 0 - квадратичный вычет по модулю р, то есть по

27

1-расширения, каждое из которых транзитивную тройки.

О-ю

теореме Эйлера (j - ifp 1)/2 = 1 (mod р). Известно, что при р = An + 3 полученный граф будет являться турниром, он называется турниром квадратичных вычетов QT(p) (Morris, 2006).

Турнир QT(7) изображен на рис. 2.7.4.

Рис. 2.7.4. Турнир (2Т(7) и его точные вершинные 1- и 2-расширения

Оказывается (Долгов, 2010), что граф 0Т(р) является точным вершинным 1-расширением, а если р - простое число вида 4и + 3, то 0Т(р) является точным вершинным 1- и 2-расширением для подходящих турниров.

Таким образом, турниры, которые являются точными 2-расширениями, существуют при числе вершин 7, 11, 19, 23, 31, ... Соответственно, существуют турниры с числом вершин 5, 9, 17, 21, 29, ..., которые имеют точные вершинные ¿-расширения только при /с = 1 и £ = 2, а при & > 2 не имеют точных вершинных ¿-расширений.

Ориентированной звездой будем называть орграф, симметризацией которого является звезда. Ориентированную звезду будем обозначать Т^^р, где т и и -число вершин с единственной соответственно исходящей и входящей дугой, а р-число вершин с одной входящей и одной исходящей дугой. Направленной звездой будем называть ориентированную звезду, являющуюся диграфом, и обозначать „ (у направленной звезды р = 0). Вершину, являющуюся концом или началом каждой дуги звезды, будем называть центральной. Теоремы 2.7.8-2.7.10 описывают минимальные вершинные ¿-расширения направленных звезд.

В третьей главе рассматриваются реберные расширения графов. По своей структуре третья и вторая главы идентичны.

Результаты главы 2 опубликованы в работах [1, 3,10, 11,13,15].

Заметим, что число ребер минимального реберного ¿-расширения графа заранее оценить очень сложно, так как граф может вообще не иметь реберного к-расширения с тем же числом вершин, что у него. Если граф имеет минимальное реберное ¿-расширение с \а'\ ребрами, то будем говорить, что это расширение

содержит |а*|-|а| дополнительных ребер. Для любого графа, кроме вполне

несвязного, количество дополнительных ребер больше 0.

Схема многих теорем о реберных расширениях следует аналогичной схеме для вершинных расширений.

Заметим, что минимальное реберное ¿-расширение отличается от исходного графа на некоторое число дополнительных ребер, и только вполне несвязный граф изоморфен любому своему минимальному реберному ¿-расширению.

В работе (Нашу, Hayes, 1993) авторы нашли минимальные реберные ¿-расширения для некоторых видов графов, в том числе для цепей и циклов.

ТЕОРЕМА 3.1.1 (Harary, Hayes, 1993). Минимальное реберное 1-расширение п-вершинной цепи Рп есть п-вершинный цикл С„.

Для реберных расширений задача описания графов, которые имеют минимальные реберные 1-расширения с малым числом ребер, является более сложной, чем для вершинных 1-расширений. Очевидно, что если граф G имеет минимальное реберное 1-расширение G* с одним дополнительным ребром, то граф G* будет точным реберным 1-расширением графа G.

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

Доказывается следующая

ТЕОРЕМА 3.1.3. Однородный граф G является точным реберным 1-расши-рением тогда и только тогда, когда он является реберно-симметрическим.

Следующая известная теорема (Харари, 2003) устанавливает связь между реберно-симметрическими и вершинно-симметрическими графами:

ТЕОРЕМА 3.1.4. Реберно-симметрический граф без изолированных вершин является или вершинно-симметрическим, или двудольным.

Из этой теоремы очевидным образом получается следующая

ТЕОРЕМА 3.1.5. Пусть однородный граф G является точным реберным 1-расширением, тогда он является ши точным вершинным 1-расширением, или двудольным графом.

Реберно-симметрический граф, не являющийся вершинносимметри-ческим,

называется полусимметрическим. В книге (Б. Бйепа, 1990) доказывается, что минимальным по числу вершин полусимметрическим графом (а следовательно, и минимальным по числу вершин точным реберным 1-расширением, которое не является точным вершинным 1-расширением) является 20-вер шинный граф Фолкмана, изображенный на рис. 3.1.2.

Рис. 3.1.2. Граф Фолкмана В книге (Харари, 2009) приводится ряд

утверждений о свойствах симметрических графов, которые с учетом установленных соответствий могут быть сформулированы следующим образом:

ТЕОРЕМА 3.1.6. а) Если С - однородное п-вершинное точное реберное 1-расширение и степень (1 каждой вершины нечетна, то граф С является точным вершинным 1-расширением.

б) Если граф б — однородное п-вершинное точное реберное 1-расширепие и степень каждой вершины четна, причем й > р!2, то граф О является точным вершинным 1-расширением.

И, наконец, имеет место следующая

ТЕОРЕМА 3.1.7. Для каждого п > 20, кратного 4, существует однородное п-вершинное точное реберное 1-расширение, не являющееся точным вершинным 1-расширением.

В параграфе 3.2 доказывается, что задача распознавания вершинного ¿-расширения является ИР-полной, а также рассматриваются оптимизационные варианты задачи.

ЗАДАЧА: РЕБЕРНОЕ ¿-РАСШИРЕНИЕ УСЛОВИЕ. Даны графы О = (У,а) и Н= (£/,/?).

ВОПРОС. Верно ли, что граф С является реберным ¿-расширением графа Я?

ТЕОРЕМА 3.2.1. Задача РЕБЕРНОЕ к-РАСШИРЕНИЕ является МР-полной.

В параграфе 3.3 исследуются неизоморфные минимальные реберные расширения. Описываются минимальные по числу вершин и ребер графы с неизоморфными минимальными реберными 1-расширениями.

В параграфе 3.4 рассматриваются минимальные реберные 1-расширения циклов. Большинство схем построения минимальных вершинных 1-расширений, которые были рассмотрены в главе 2, позволяют строить и минимальные реберные 1-расширения для циклов с числом вершин на 1 больше. Однако схема автора таким свойством не обладает. Предлагается новая схема, построения минимальных реберных 1-расширений циклов.

ТЕОРЕМА 3.4.7. Гамшьтоновы графы, изображенные на рис. 3.4.3, представляют собой минимальные реберные 1-расширения п-вершинного (п > 3) цикла при п четном (рис. 3.4.3, а)ип нечетном (рис. 3.4.3, б).

^/2-1

Рис. 3.4.3. Минимальные реберные 1-расширения циклов

Доказывается, что схема из теоремы 3.4.7 отлична от схем Хейза и Махопадхья-Синха (теоремы 3.4.8, 3.4.9). Как следствие получается

ТЕОРЕМА3.4.10.Любой цикл Сп при п>5 имеет, по крайней мере, два неизоморфных минимальных реберных 1-расширения.

Аналогичный результат имеет место и для минимальных вершинных 1-расширений циклов (см. теорему 2.4.10).

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

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

ЛЕММА 3.5.1. Пусть п-вершинный предполный граф б имеет в точности р полных вершин. Если граф <7 имеет минимальное реберное к-расширение, то оно содержит не менее р + 2к полных вершин.

Следствие 1. Если п-вершинный предполный граф й имеет в точности р полных вершин, тогда граф С7 не имеет минимальных реберных к-расширений при

, п-р

к>-—.

2

Следствие 2. Пусть п-вершинный предполный граф имеет вид Кр + С„. Если он имеет минимальное реберное к-расширение, то оно имеет вид Кр+2к + где Сп_2к - подходящий (п — 2к)-вершинный граф.

Далее теоремы 3.5.1-3.5.4 полностью решают задачу описания минимальных реберных ¿-расширений графов вида Кт + Рп и Кт + С„ .

В параграфе З.б исследуются минимальные реберные 1-расширения деревьев. Как и в параграфе 2.6 исследуются звезды и сверхстройные деревья. Для звёзд получено полное решение.

ТЕОРЕМА 3.6.1. При к < п/2 граф Кт+2к + <?п-2* является единственным минимальным реберным к-расширением графа Кт + Оп. При к > п/2 граф Кт + Оп не имеет минимальных реберных к-расширений.

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

ТЕОРЕМА 3.6.2. Минимальное реберное 1-расширение сверхстройного

дерева Т с вектором степеней (к,2.....2) содержит не менее чем (к + 1)/2 при

нечетном ки (к + 2)12 при четном к дополнительных ребер.

ТЕОРЕМА 3.6.3. Сверхстройное дерево Тс вектором цепей (ти...,тк) тогда и только тогда имеет минимальное реберное 1-расширение с вектором степеней (к + 1,2,. ..,2), отличающееся от Тна (к + 1)/2 дополнительных ребер, когда

1) среди его цепей есть цепи всех длин от 1 до т\ (максимальной длины цепи);

2) цепь максимальной длины т\ единственна-,

3) все остальные цепи можно разбить на пары так, чтобы их длины в сумме давали т\.

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

ТЕОРЕМА 3.7.1. Единственным с точностью до изоморфизма минимальным реберным \-расширением п-вершинного турнира является полный п-вершинный граф без петель. При к > 1 п-вершинный турнир не имеет минимальных реберных к-расширений.

Теоремы 3.7.2-3.7.5 описывают минимальные вершинные и реберные к-расширения направленных и ориентированных звезд.

В заключении рассматривается вопрос о возможности нахождения минимального вершинного (реберного) ¿-расширения графа, если известны минимальные вершинные (реберные) расширения графа при значениях меньших к. Представляется интуитивно очевидным, что минимальное вершинное (реберное) 1-расширение минимального вершинного (реберного) (к- ^-расширения будет являться минимальным вершинным (реберным) ¿-расширением. Доказывается, что в общем случае это неверно. Эти результаты были опубликованы в работах [1,3].

Список литературы

Av&enis A. Fault-tolerance and fault-intolerance : Complementary approaches to reliable computing // Proc.

Intern. Conf. on Reliable Software. - New York: ACM, 1975. - P. 458-464. AvizienisA., Laprie J.-C., RandeU В., Landwehr C. Basic Concepts and Taxonomy of Dependable and Secure

Computing // ШЕЕ Transactions on Dependable and Secure Computing. - 2004. - № 1. - P. 11-33. Brinkmarm G. Fast generation of cubic graphs // J. Graph Theory. - 1996. - Vol. 23, № 2. - P. 139-149. Brmkmann G., Goedgebeur J„ McKay B. D. Generation of cubic graphs // Discrete Math. Theor. CompuL Sci. -

2011. - Vol. 13, № 2. - P. 69-80. Choudum S. A, Sivagunmathan S. Optimal fault-tolerant networks with a server II Networks. - 2000. - Vol. 35, №2.-P. 157-160.

Dutt S., Hayes J. P. On designing and reconfiguring fc-fault-tolerant tree architectures // IEEE Trans. CompuL -

1990. - Vol. 39. - P. 490-503. Farrag A. A., Dawson R. J. Designing optimal fault-tolerant star networks // Networks. - 1989. - Vol. 19. - P. 707-716.

Harary F., Hayes J. P. Edge fault tolerance in graphs /I Networks. - 1993. - Vol. 23. - P. 135-142.

Harary F„ Khurum M. One node fault tolerance for caterpillars and stariike trees // Internet J. CompuL Math. -

1995.-Vol. 56.-P. 135-143. Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. -1996. - Vol. 27. - P. 19-23. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. CompuL - 1976. - Vol.C.-25, №9.-P. 875-884.

Hayes J. P. Computer architecture and organization. - New York: McGraw-Hill, 1998.

KuH. K., Hayes J. P. Optimally edge fault-tolerant trees//Networks. - 1996.-Vol. 27. - P. 203-214.

Kwan С. L. Toida S. An optimal 2-FT realization of symmetric hierarchical tree systems // Networks. - 1982. -Vol. 12.-P. 231-239.

Morris J. Automorphism Groups of Circulant Graphs - a Survey // Graph Theory in Paris. - Paris : Birkhauser Basel, 2006.-P. 311-325.

Mukhopadhyaya K, Sinha B. P. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies // Inform. Process. Lett. - 1992. - Vol. 44. - P. 95-99.

Radjavi #., Rosenthal P. Graphs with isomorphic subgraphs // London Math. Soc. (2). - 1972. - Vol. 6. - P. 70-72.

Skiena S. Implementing Discrete Mathematics : Combinatorics and Graph Theory with Mathematica. - Reading, MA: Addison-Wesley, 1990.

StockmeyerP. A census of non-reconstmctable digraphs : six related families // J. Comb. Th. B. - 1981. -Vol. 31.-P. 232-239.

Sung T.Y., Lin C. Y., Chuang Y. C., HsuL H. Fault tolerant token ring embedding in double loop networks // Inform. Process. Lett. - 1998. - Vol. 66. - P. 201-207.

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

Долгов А. А. Семейство точных 2-расширений турниров // Прикладная дискретная математика. - 2010. -№9. -С. 96-99.

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

Каравай М Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. - 1996. - № 6. - С. 159-173.

Каравай М. Ф. Инвариантно-групповой подход к исследованию к-отказо-устойчивых структур II Автоматика и телемеханика. - 2000. - № 1. - С. 144-156.

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

Курносова С. Г. Построение Т-неприводимых расширений для класса полных бинарных деревьев // Вести, молодых ученых «Ломоносов». - М.: МАКС Пресс, 2006. - Вып. Ш. - С. 58-66.

Салий В. Н. Доказательства с нулевым разглашением в задачах о расширениях графов // Вести. Томск, гос. ун-та. Приложение. - 2003. - № 6. - С. 63-65.

Салий В. Н. Оптимальные реконструкции графов // Современные проблемы дифференциальной геометрии и обшей алгебры. - Саратов: Изд-во Сарат. ун-та, 2008. - С. 59-65.

Харари Ф. Теория графов. — 4-е изд. - М.: Едиториал УРСС, 2009.

Список основных публикаций по теме диссертации Монография

1. Абросимов М. Б. Графовые модели отказоустойчивости. - Саратов : Изд-во Сарат. ун-та, 2012. - 192 С.

Статьи в рецензируемых научных журналах, включенных в перечень ВАК

2. Абросимов М Б. Минимальные /¡-расширения предполных графов // Изв. вузов. Математика. - 2003. -

№6(493).-С. 3-11.

3. Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Изв. Сарат. ун-та. Нов.

сер. Сер. Математика. Механика. Информатика. - 2006. - Т. 6, вып. 1/2. - С. 86-91.

4. Абросимов М.Б., Гшъман Е.А. Некоторые решения на основе SCADA-системы «КИРАС» //

Автоматизация в промышленности. - 2007. - № 4. - С. 63-64.

5. Абросимов М.Б., Гильман Е.А., Кривоносое А.А. Инструментальные средства для моделирования ТП и

разработки тренажерных комплексов // Автоматизация в промышленности. - 2007. - №8. - 43-45.

6. Абросимов МБ., Гильман Е.А. Мнемосхемные комплексы на основе SCADA- системы «КИРАС»//

Автоматизация в промышленности. - 2008. - № 1. - С. 54-55

7. Абросимов МБ., Гильман Е.А. Новые возможности инструментальных средств УТК для разработки

тренажерных комплексов П Автоматизация в промышленности. - 2008. - № 7. - С. 54-55.

8. Абросимов М R, Долгов А. А О реконструируемое™ малых турниров // Изв. Сарат. ун-та. Нов. сер.

Сер. Математика. Механика. Информатика. - 2009. - Т. 9, вып. 2. - С. 94-98.

9. Абросимов М Б., Долгов А. А О бесконтурных точных расширениях// Изв. Сарат. ун-та. Нов. сер. Сер.

Математика. Механика. Информатика. - 2010. - Т. 10, вып. 1. - С. 83—88. Ю.Абросимов М Б. Минимальные реберные расширения некоторых предполных графов // Прикладная

дискретная математика. — 2010. —№ 1.—С. 105-117. П.Абросимов МБ. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки.

- 2010. - Т. 88, вып. 5. - С. 643-650.

\2.Абросимов МБ., Гильман Е.А., Кривоносое А.А., Ерхов А.В. О разработке и внедрении тренажера для установки дегидрирования изобутана // Автоматизация в промышленности. - 2010. - № 7. - С. 66-68. ХЪ.Абросимов М Б. Минимальные реберные расширения направленных и ориентированных звезд // Прикладная дискретная математика. - 2011. - № 2. - С. 77-89.

14.Абросимов М Б. Минимальные вершинные расширения направленных звезд // Дискрет, матем. — 2011.

— Т. 23, № 2. — С. 93-102.

15.Абросимов MR О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2011. - Т. 11, вып. 3, ч. 2. - С. 111-117.

16.Абросимов М Б. Характеризацня графов с заданным числом дополнительных ребер минимального вершинного 1-расширения // Прикладная дискретная математика. - 2012. -№ 1. - С. 111-120.

17. Абросимов MR О числе дополнительных ребер минимального вершинного 1-расширения

сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. -2012.-Т. 12, вып. 2.-С. 103-113. \&.Абросимов М Б., Моденова О. В. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. - 2013. - Т. 13., вып. 2, ч. 2. - С. 3-9.

19.Абросимов М Б., Моденова О. В. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1-расширении // Прикладная дискретная математика. - 2013. — N° 3. - С. 68-75.

Свидетельства о регистрации программных комплексов

20.Абросимов М Б., Бондаренко П. П. Исследование минимальных вершинных и реберных 1-расширений цепей с вершинами двух типов // Свидетельство о государственной регистрации программы для ЭВМ № 2010616497, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 30.09.2010.

21.Абросимов М Б. Построитель минимальных вершинных и реберных 1-расширений графов // Свидетельство о государственной регистрации программы для ЭВМ № 2011610846, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 19.01.2011.

22.Абросимов М Б., Моденова О. В. Исследование минимальных вершинных 1-расширений орграфов // Свидетельство о государственной регистрации программы для ЭВМ № 2012612065, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 22.02.2012.

23. Абросимов М Б., Комаров Д. Д. Поиск минимальных реберных и вершинных 1-расширений графов //

Свидетельство о государственной регистрации программы для ЭВМ № 2012661394, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 13.12.2012.

Напечатано с готового оригинал-макета

Подписано в печать 25.02.2014г. Формат 60x90 1/16. Усл.печл. 2,0. Тираж 70экз. Заказ 025.

Издательство ООО 'МАКС Пресс" Лицеюия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы,МГУ им. МВ. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Саратовский государственный университет им. Н. Г. Чернышевского»

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

05201450663

АБРОСИМОВ

ГРАФОВЫЕ МОДЕЛИ ОТКАЗОУСТОЙЧИВОСТИ

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

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

Саратов 2013

ОГЛАВЛЕНИЕ

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

ГЛАВА 1. ОСНОВНЫЕ СВОЙСТВА........................................................13

1.1. Основные понятия теории графов..................................................13

1.2. Отказоустойчивость.........................................................................24

1.3. Расширения графов..........................................................................36

1.4. Вычислительная сложность............................................................39

ГЛАВА 2. ВЕРШИННЫЕ РАСШИРЕНИЯ...............................................43

2.1. Основные определения и свойства................................................43

2.2. Сложность задачи............................................................................82

2.3. Неизоморфные расширения............................................................85

2.4. Циклы................................................................................................91

2.5. Предполные графы........................................................................108

2.6. Деревья............................................................................................137

2.7. Орграфы..........................................................................................159

Г Л А В А 3. РЕБЕРНЫЕ РАСШИРЕНИЯ...................................................178

3.1. Основные определения и свойства..............................................178

3.2. Сложность задачи..........................................................................185

3.3. Неизоморфные расширения..........................................................190

3.4. Циклы..............................................................................................193

3.5. Предполные графы........................................................................201

3.6. Деревья............................................................................................211

3.7. Орграфы..........................................................................................221

ЗАКЛЮЧЕНИЕ...............................................................................................240

СПИСОК ЛИТЕРАТУРЫ..............................................................................244

ПРИЛОЖЕНИЕ...............................................................................................262

ВВЕДЕНИЕ

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

Авиженис (Avizienis, 1975) выделил два подхода для повышения надежности (reliability) реальных вычислительных систем: предотвращение ошибок и отказоустойчивость.

Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоконадежных компонентов системы. На этом пути можно отметить большие успехи. Время наработки на отказ первых компьютеров измерялось минутами, а современных - годами.

Во втором направлении используется добавление в систему избыточных структур для придания ей дополнительных свойств отказоустойчивости. Понятие отказоустойчивости было определено Авиженисом как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют следующие уровни отказоустойчивости:

1) полная отказоустойчивость - система продолжает работать в присутствии ошибок без существенной потери функциональных свойств;

2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

Некоторое время назад (Laprie, 1985 ; Dependability ..., 1992 ; Avizienis et al., 2004 ; Харченко, 2006 ; Харченко, 2009) стали рассматривать более общее понятие, чем надежность (reliability), - гарантоспособность (dependability). Под гарантоспособностью понимается комплексное свойство системы предоставлять требуемые услуги, которым можно оправданно доверять. В работе (Avizienis et al., 2004) дается подробная таксономия для гарантоспособности. В частности, надежность является атрибутом гарантоспособности, а отказоустойчивость - одним из средств ее достижения.

В данной работе будет исследоваться конструкция минимального вершинного и реберного расширения графа, основанная на идеях формализации понятия полной отказоустойчивости технических систем, предложенных в 1976 г. Хейзом (Hayes, 1976).

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

Говорят, что система X* является k-отказоустойчивой реализацией системы X, если отказ любых к элементов системы X* приводит к графу, в который можно вложить граф системы X с учетом меток вершин. Построение ^-отказоустойчивой реализации системы X можно представить себе как введение в неё определенного числа новых элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры. Следует заметить, что процесс реконфигурации в общем случае (с учетом частичной деградации функциональных возможностей системы) является достаточно сложной процедурой и составляет самостоятельную область исследования (см. например, Livingston, Stout, 1988 ; Dutt,

Hayes, 1991 ; Graham et al., 1993 ; Пархоменко, 2000). Для нас далее представляет интерес оптимизация Ar-отказоустойчивой реализации.

Пусть в системе X встречается t различных типов элементов. Очевидно, что любая ее ^-отказоустойчивая реализация должна содержать не менее к дополнительных элементов каждого типа. Легко видеть, что такого числа дополнительных элементов достаточно для построения ^-отказоустойчивой реализации системы X. В самом деле, добавим к элементов каждого типа и соединим их все между собой и с элементами системы X. Тогда любой отказавший элемент можно будет заменить одним из добавленных элементов соответствующего типа. Далее построенную таким образом ^-отказоустойчивую реализацию будем называть тривиальной.

^-отказоустойчивая реализация X системы X, состоящей из t элементов различного типа, называется оптимальной, если система X* отличается от системы X на к элементов каждого из t типов системы X и среди всех ^-отказоустойчивых реализаций с тем же числом элементов система X* имеет наименьшее число ребер.

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

Данный подход впервые был изложен Хейзом в работе (Hayes, 1976). Там же были предложены процедуры построения оптимальной ^-отказоустойчивой реализации для цепи, цикла и помеченного дерева. Позднее Хейз совместно с Харари обобщил модель на случай отказов связей между элементами, предложив понятие реберной отказоустойчивости

(Harary, Hayes, 1993). Модель отказоустойчивости, в которой рассматриваются только отказы элементов, было предложено называть вершинной отказоустойчивостью (Harary, Hayes, 1996). Последующее расширение модели связано с рассмотрением как отказов элементов, так и отказов связей между ними. Подобная модель, называемая комбинированной отказоустойчивостью, рассматривается в работах (Sung et al., 1998 ; Wang et al., 1998, 2000 ; Huang et al., 1999 ; Hung et al., 2000, 2001 ; Sung et al., 2000 ; Hsu, Lin, 2009).

A. В. Киреева рассматривала вершинную отказоустойчивость в ориентированных графах (Киреева, 1995). Ею описана вершинная оптимальная 1 -отказоустойчивая реализация произвольного функционального графа. Санг и другие (Sung et al., 1998) использовали модель Хейза для нахождения вершинной и реберной оптимальной 1 -отказоустойчивой реализации ориентированного цикла.

Иногда рассматривают вершинную отказоустойчивость с несколько иной интерпретацией отказов элементов (например, (Каравай, 1996 ; Каравай, 2000)): отказавший элемент исключается из модели, однако все его связи сохраняются, что приводит к новой системе, в которой каждая пара элементов, связанных с отказавшим, также будет связана.

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

6

Деревья. Задачу описания оптимальных ^-отказоустойчивых реализаций деревьев сформулировал Хейз (Hayes, 1976). Там же была предложена вершинная оптимальная 1-отказоустойчивая реализация для полного агарного дерева с метками. Харари и Хуррум (Harary, Khurum, 1995) описали схему построения оптимальной 1-отказоустойчивой реализации деревьев специального вида: гусениц и звездоподобных деревьев. Еще один результат для частного случая гусениц (цепи колес) был получен М. А. Кабановым (Кабанов, 1997). Звездоподобным (сверхстройным) деревьям далее будет уделено достаточное внимание. Кван и Тойда (Kwan, Toida, 1982) описали схему построения оптимальной 2-отказоустойчивой реализации для полного бинарного дерева с метками. Сложность задачи для общего случая привела к понятию почти оптимальной к-отказоустойчивой реализации (Dutt, Hayes, 1990). Задача нахождения реберной оптимальной ^-отказоустойчивой реализации дерева с метками исследуется в работе (Ku, Hayes, 1996). Определенного успеха удалось добиться С. Г. Курносовой при описании Т-неприводимых 1-расширений полных бинарных деревьев (Курносова, 2005, а ; Курносова, 2006).

Циклы. Задача нахождения оптимальных ^-отказоустойчивых реализаций циклов впервые была поставлена и решена Хейзом (для отказов элементов в (Hayes, 1976), а для отказов связей между элементами в (Harary, Hayes, 1993). В работе (Harary, Hayes, 1996) Харари и Хейз поставили задачу нахождения оптимальных ^-отказоустойчивых реализаций циклов, отличных от тех, что были предложены в (Hayes, 1976). Махопадхья и Синха (Mukhopadhyaya, Sinha, 1992) указали первое такое семейство оптимальных 1-отказоустойчивых реализаций циклов. Ряд других семейств приводится в работах (Paoli et al., 1984, 1986 ; Wang et al., 1998, 2000 ; Hung et al., 1999, 2000, 2001 ; Sung et al., 2000 ; Абросимов, 2000, a ; Hsu, Lin, 2009). Заметим, что только схемы построения, предложенные Хейзом, Махопадхья и Синхом, позволяют указать оптимальную 1-отказоустойчивую реализацию для цикла с любым числом вершин, в том числе и для цикла с четным числом вершин.

Далее будет предложена еще одна схема построения оптимальной 1-отказоустойчивой реализации для цикла с любым числом вершин, отличная от схемы Хейза.

Отдельно следует выделить исследования, связанные с нахождением оптимальной 1-отказоустойчивой реализации ориентированного цикла, в работе (Sung et al., 1998).

Особый интерес в рамках данного направления представляет описание негамильтоновых минимальных вершинных 1-расширений циклов. Эти исследования тесно связаны с поиском гипогамилътоновых графов, то есть негамильтоновых графов, каждый максимальный подграф которых является гамильтоновым.

Задача нахождения гипогамильтоновых графов была сформулирована в 1963 году Сусельером (Sousselier, 1963). Год спустя Годин, Херц и Росси (Gaudin et al., 1964) показали, что наименьшим гипогамильтоновым графом является граф Петерсена. Позднее исчерпывающий компьютерный поиск показал, что не существует гипогамильтоновых графов с числом вершин 11, 12 (Herz et al., 1966), 14 (Collier, Schmeichel, 1978) и 17 (Aldred et al., 1997). С другой стороны, были найдены гипогамильтоновы графы с числом вершин и = 10, 13, 15 и 16, а также для всех п > 18 (Herz et al., 1967 ; Lindgren, 1967 ; Bondy, 1972 ; Chvatal, 1973 ; Thomassen, 1974, а, б ; Doyen, van Diest, 1975 ; Holton, Sheehan, 1993). Подробный обзор вопроса можно найти в книге Хол-тона и Шихана (Holton, Sheehan, 1993), последний результат - об отсутствии 17-вершинных гипогамильтоновых графов — содержится в работе Алдреда, Маккея и Вормальда (Aldred et al., 1997).

Интересное применение Т-неприводимые расширения нашли в криптографии (Салий, 2003). Расширения графов можно рассматривать в контексте задач реконструкции, когда из заданного графа требуется построить новый граф, обладающий определенными свойствами (Салий, 2008). Многие результаты, полученные при исследовании оптимальных ^-отказоустойчивых реализаций графов, оказались тесно переплетены с результатами, получен-

ными в рамках «чистой» теории графов. В рамках технической диагностики задача описания оптимальных ^-отказоустойчивых реализаций рассматривается для графов, являющихся моделями технических систем, что накладывает ограничение на класс графов, представляющих интерес для исследования. Далее конструкция вершинной оптимальной ^-отказоустойчивой реализации будет рассматриваться как абстрактная конструкция над графами, однако особое внимание будет уделено полезным с практической точки зрения классам графов, таким как звезды и их ориентации, цепи, циклы, звездоподобные (сверхстройные) деревья, турниры.

Научная новизна и выносимые на защиту положения. Все основные результаты диссертации являются новыми. Укажем наиболее важные из них.

1. Доказана вычислительная сложность задач, связанных с расширениями графов. Установлено, что задача распознавания является ли предъявляемый граф вершинным или реберным ^-расширением заданного графа относится к классу ЫР-сложных задач. Оптимизационные варианты задачи (распознавание минимального или неприводимого расширения) не принадлежат классу М3. Полученные результаты означают, что общего решения задачи построения минимальных или неприводимых к-расширений для произвольного графа, по-видимому, не существует. Задача распознавания точного вершинного или реберного к-расширения имеет такую же сложность, как и задача проверки изоморфизма графов.

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

3. Описаны все минимальные вершинные 1-расширения графов с числом дополнительных ребер не более 3.

4. Предложены новые семейства минимальных вершинных и реберных 1-расширений для циклов. Доказано, что эти минимальные 1-расширения отличны от других известных семейств Харари-Хейза и Махопадхья-Синха.

5. Найдены минимальные вершинные и реберные ^-расширения для предполных графов. В случае вершинных ^-расширений задача решена полностью. Оказалось, что почти все предполные графые имеют единственное с точностью до изоморфизма минимальное вершинное к-расширение, которым является тривиальное ^-расширение.

6. Описаны минимальные вершинные и реберные 1-расширения сверхстройных деревьев, для которых число дополнительных ребер минимально возможное.

7. Исследована связь минимальных ^-расширений ориентированных графов и соответствующих им неориентированных графов (их симметри-заций). С помощью полученных результатов описаны минимальные вершинные и реберные ^-расширения некоторых классов ориентированных графов: звезд и турниров.

Личный вклад автора. Все выносимые на защиту результаты диссертации принадлежат лично автору.

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

Достоверность полученных результатов. Все полученные в диссертации результаты имеют строгое математическое доказательство.

Апробация работы. Результаты работы докладывались на VI и VIII Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2001 и 2003), Международной конференции «Дискретный анализ и исследование операций» DOOR-2004 (Новосибирск, 2004), DOQR-2010 (Алтай, 2010), на Второй меж-

дународной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006), на Международной научно-методическ