Главная >> Диссертации - все темы

Pages: |

| 2 | 3 | 4 | 5 |

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

-- [ Страница 1 ] --

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Саратовский государственный университет им. Н. Г. Чернышевского»

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

М. Б. АБРОСИМОВ

ГРАФОВЫЕ МОДЕЛИ

ОТКАЗОУСТОЙЧИВОСТИ

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

Саратов 2013

ВВЕДЕНИЕ

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

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

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

Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоконадежных компонентов системы.

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

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

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

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

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

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

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

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

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

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

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

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

Данный подход впервые был изложен Хейзом в работе (Hayes, 1976).

Там же были предложены процедуры построения оптимальной k-отказоустойчивой реализации для цепи, цикла и помеченного дерева. Позднее Хейз совместно с Харари обобщил модель на случай отказов связей между элементами, предложив понятие реберной отказоустойчивости (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).

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

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

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

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

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

Циклы. Задача нахождения оптимальных k-отказоустойчивых реализаций циклов впервые была поставлена и решена Хейзом (для отказов элементов в (Hayes, 1976), а для отказов связей между элементами в (Harary, Hayes, 1993). В работе (Harary, Hayes, 1996) Харари и Хейз поставили задачу нахождения оптимальных k-отказоустойчивых реализаций циклов, отличных от тех, что были предложены в (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, а ; Hsu, Lin, 2009). Заметим, что только схемы построения, предложенные Хейзом, Махопадхья и Синхом, позволяют указать оптимальную 1-отказоустойчивую реализацию для цикла с любым числом вершин, в том числе и для цикла с четным числом вершин.

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

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

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

Задача нахождения гипогамильтоновых графов была сформулирована в 1963 году Сусельером (Sousselier, 1963). Год спустя Годин, Херц и Росси (Gaudin et al., 1964) показали, что наименьшим гипогамильтоновым графом является граф Петерсена. Позднее исчерпывающий компьютерный поиск показал, что не существует гипогамильтоновых графов с числом вершин 11, (Herz et al., 1966), 14 (Collier, Schmeichel, 1978) и 17 (Aldred et al., 1997). С другой стороны, были найдены гипогамильтоновы графы с числом вершин n = 10, 13, 15 и 16, а также для всех n 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). Многие результаты, полученные при исследовании оптимальных k-отказоустойчивых реализаций графов, оказались тесно переплетены с результатами, полученными в рамках «чистой» теории графов. В рамках технической диагностики задача описания оптимальных k-отказоустойчивых реализаций рассматривается для графов, являющихся моделями технических систем, что накладывает ограничение на класс графов, представляющих интерес для исследования.

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

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

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

Задача распознавания точного вершинного или реберного kрасширения имеет такую же сложность, как и задача проверки изоморфизма графов.

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

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

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

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

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

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

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

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

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

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

DOOR-2004 (Новосибирск, 2004), DOOR-2010 (Алтай, 2010), на Второй международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2006), на Международной научно-методической конференции «Актуальные проблемы математики, механики, информатики» (Пермь, 2006), на XII (Нижний Новгород, 1999), XIV (Пенза, 2005), XV (Казань, 2008) и XVI (Нижний Новгород, 2011) Международных конференциях «Проблемы теоретической кибернетики», на II-XII Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография» (2002на Международных научных конференциях «Компьютерные науки и информационные технологии» памяти А.М.Богомолова (Саратов, 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), а также в проектах, реализованных на основе указанных программ для ООО «Саратоворгсинтез»

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

(г.Москва).

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

Структура диссертации. Диссертация состоит из введения, трех главах, заключения, списка использованных источников и приложения. Полный ее объём – 269 страниц.

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

1.1. Основные понятия теории графов 1.1.1. Неориентированные графы Неориентированным графом (везде далее просто графом, или неографом) называется пара G = (V, ), где – симметричное и антирефлексивное отношение на множестве вершин V. Если (u, v), то говорят, что вершины u и v смежны и эти вершины соединены ребром (u, v). При этом (u, v) и (v, u) это одно и то же ребро, которое обозначают {u, v}. Говорят, что ребро {u, v} инцидентно каждой из вершин u и v. Графы в указанном смысле иногда называются простыми (нет петель и кратных ребер). Далее для графа через V(G), а число ребер – через. Граф, любые две вершины которого смежны, называется полным и обозначается K|V |. По определению, K |V | = G (V, V V ), где через обозначено тождественное отношение на множестве V. Граф без ребер, то есть с пустым отношением смежности, называется вполне несвязным, или нульграфом, и обозначается O|V |. Граф называется двудольным, если множество его вершин V может быть разбито на два подмножества вершин V1 и V2, такие что концы любого ребра графа принадлежат разным подмножествам. Если граф содержит все ребра, соединяющие вершины из множеств V1 и V2, то он называется полным двудольным графом и обозначается Km,n, где m и n – число вершин в множествах V1 и V2. Граф вида K1,n называется звездой, звездным графом, или колесом. Основные определения мы используем в соответствии с книгами (Богомолов, Салий, 1997) или (Харари, 2009). Данные по числу различных объектов даются преимущественно по работе (Sloane, Plouffe, 1995) и сопровождаются соответствующей ссылкой на сайт числовых последовательностей «Integer Sequences»:

http://oeis.org/.

Степенью вершины v в неориентированном графе G будем называть количество вершин в G, смежных с v, и обозначать через d(v). Набор чисел, являющихся степенями вершин графа G, называют его степенным множеством, а вектор, составленный из степеней вершин графа G в порядке убывания, – вектором степеней. Говорят, что граф является реализацией своих вектора степеней и степенного множества.

Два графа G1 = (V1, 1) и G2 = (V2, 2) называются изоморфными, если можно установить взаимно однозначное соответствие f : V1 V2, сохраняющее отношение смежности: (u, v) 1 (f(u), f(v)) 2, для любых u, v V1.

В этом случае пишут G1 G2.

Граф, вершинам которого приписаны метки, называется помеченным.

Непомеченным или абстрактным графом называется класс изоморфных графов. Количество непомеченных графов с ростом числа вершин быстро растет: 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168 1.

Изоморфное отображение графа на себя называется автоморфизмом.

Тождественное отображение : V V является автоморфизмом для любого графа. Автоморфизмы графа образуют группу. Граф, имеющий только тождественный автоморфизм, называется асимметричным, или тождественным. Минимальным тождественным графом является одновершинный граф.

Тождественных графов с числом вершин 2, 3, 4, 5 не существует, а, начиная с См. последовательность A000088: http://oeis.org/A 6 вершин, количество тождественных графов быстро увеличивается: 8, 152, 3696, 135004, 7971848, 805364776 2.

Две вершины u и v называются подобными, если существует автоморфизм f, такой что f (u) = v. Граф, все вершины которого подобны, называется вершинно-симметрическим. Два ребра {u1, v1} и {u2, v2} называются подобными, если существует автоморфизм, который переводит одно ребро в другое. Граф, все ребра которого подобны, называется реберносимметрическим.

Инвариантом графа G называется набор его характеристик, одинаковых для всех изоморфных ему графов. Инвариантами графа являются, например, число вершин графа, количество дуг или ребер. Полным инвариантом называется такой инвариант, который определяет граф однозначно с точностью до изоморфизма. Одним из известных числовых инвариантов является максимальный (минимальный) матричный код графа.

Матрица отношения смежности графа называется его матрицей смежности. Пусть G = (V, ) – n-вершинный граф. Тогда его матрица смежности A = M() имеет размерность n n, а на позиции (i, j) стоит 1, если есть дуга (vi, vj) и 0 в противном случае:

Если выписать элементы матрицы смежности по строкам, то получится некоторое двоичное число – код графа:

Само по себе это число не является инвариантом, так как матрицы смежности у изоморфных графов могут различаться, однако если среди всех изоморфных графов выбрать матрицу смежности с максимальным (максиСм. последовательность А003400: http://oeis.org/A мальный код) или минимальным (минимальный код) значением кода, то получится инвариант, причем полный. Очевидно, что для n-вершинного графа размер кода будет n2 бит. Для некоторых классов графов, например для неориентированных графов, достаточно хранить только часть матрицы смежности, расположенную над главной диагональю. В этом случае размер кода будет составлять n(n – 1)/2 бит.

Если вектор степеней имеет единственную реализацию, то говорят, что вектор степеней определяет униграф. Все графы с числом вершин до 5 являются униграфами. Далее число униграфов по сравнению с общим числом графов растет существенно медленнее: 1, 2, 4, 11, 28, 72, 170, 407, 956, 2252 3.

Однородным (или регулярным) n-вершинным графом Rn,p порядка p называют граф, в котором все степени вершин равны p. Однородный граф порядка называется кубическим. Очевидно, что кубические графы существуют только при четном количестве вершин, начиная с 4. Единственный кубический 4вершинный граф – полный граф K4. С ростом числа вершин количество кубических графов быстро растет: 1, 2, 6, 21, 94, 540, 4207, 42110, 516344 4. Однородный граф порядка 4 называется биквадратным. Биквадратные графы существуют при любом количестве вершин, начиная с 5. Единственный биквадратный 5-вершинный граф – полный граф K5. С ростом числа вершин количество биквадратных графов быстро растет: 1, 1, 2, 6, 16, 60, 266, 1547, 15280899376 5.

Путем в графе G = (V, ) называется последовательность вершин и ребер вида v 0, {v 0, v1 }, v1,..., {v n 1, v n }, v n. При этом говорят, что v0 – начальная вершина пути, а vn – конечная. Говорят также, что путь соединяет вершины v и vn, и вершина vn достижима из v0. Путь в графе можно задавать перечислением входящих в него вершин в порядке их прохождения: v0,…,vn. Путь, каСм. последовательность A122423: http://oeis.org/A См. последовательность A005638: http://oeis.org/A См. последовательность A033301: http://oeis.org/A ждая вершина которого принадлежит не более чем двум его ребрам, считается простым. Если начальная вершина простого пути совпадает с конечной, путь называют циклом, в противном случае – цепью. Цикл или цепь, содержащие все вершины графа, называются гамильтоновыми. Граф, содержащий гамильтонов цикл, также называется гамильтоновым. Цепи и циклы, кроме указанного выше смысла, могут иметь еще интерпретацию как графы специального вида.

Цепью Pn называется граф G = (V, ), где V = {v1, v2, …, vn}, и = {(vi, vj): |i – j| = 1}, а циклом Cn – граф G = (V, ), где V = {v1, v2, …, vn}, и = {(vi, vj): |i – j| = 1} {(v1, vn), (vn,v1)}.

Дополнением графа G = (V, ) называется граф G' = (V, ' ), где ' = (V V ) /( ). Граф, изоморфный своему дополнению, назовем самодополнительным.

Соединением двух графов G1 = (V1, 1 ) и G 2 = (V2, 2 ), не имеющих общих вершин, называется граф Очевидно, что операция соединения двух графов коммутативна.

Соединением n графов Gi = (Vi, i ), не имеющих общих вершин, назовем граф G1 + G2 +... + Gn := (...( G1 + G2 ) +...) + Gn.

ЛЕММА 1.1.1. Операция соединения n графов ассоциативна и коммутативна. Причем имеет место следующее соотношение:

Доказательство очевидно.

Будем обозначать через Gm соединение m графов G1,…,Gm, таких, что никакие два из них не имеют общих вершин, и каждый граф Gi изоморфен графу G.

Объединением двух графов G1 = (V1, 1 ) и G 2 = (V2, 2 ) называется граф G1 G 2 := (V1 V 2, 1 2 ). Далее, если явно не указано обратное, мы будем полагать, что множества V1 и V2 не пересекаются.

Объединением графов G1 = (V1, 1 ), …, Gn = (Vn, n ) называется граф Очевидно, что операция объединения графов коммутативна.

Будем обозначать через mG объединение m графов G1,…,Gm, таких, что никакие два из них не имеют общих вершин, и каждый граф Gi изоморфен графу G.

Будем считать, что каждая вершина достижима из самой себя. Тогда отношение достижимости является отношением эквивалентности на множестве вершин графа. Классы этого отношения называются компонентами связности графа. Граф с универсальным отношением достижимости называется связным. Связный граф без циклов называется деревом. Дерево с одной вершиной называется тривиальным. Корневым называется дерево с выделенной вершиной, а эта выделенная вершина называется корнем. Вершины степени 1, кроме корневой, называются листьями. Высота корневого дерева есть наибольшая из длин цепей от корневой вершины до листьев. Дерево без выделенной вершины называется свободным. Приведем количество связных n-вершинных графов и свободных деревьев7:

Подразбиением ребра {u, v} в графе называется операция, состоящая из удаления ребра {u, v}, добавления новой вершины w и двух ребер {u, w} и {v, w}. Два графа называются гомеоморфными, если они могут быть См. последовательность A001349: http://oeis.org/A См. последовательность A000055: http://oeis.org/A получены из одного графа с помощью последовательности подразбиений ребер.

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

На сверхстройное дерево можно смотреть как на объединение цепей с общей концевой вершиной. При этом дерево можно закодировать вектором, состоящим из длин цепей в порядке невозрастания:

(m1, …, mk), где m1 … mk. Очевидно, что такое кодирование сверхстройных деревьев при k > 2 является взаимно однозначным. В самом деле, любому вектору (m1, …, mk) будет соответствовать единственное с точностью до изоморфизма сверхстройное дерево с числом вершин m1 +… + mk + 1. В этом дереве корневая вершина остальные m1 +… + mk – k вершин будут иметь степень 2.

Будем называть такой код вектором цепей.

Пример. На рис. 1.1.1 изображено сверхстройное дерево с 12 вершинами, являющееся объединением четырех цепей с общей концевой вершиной: P5, P4, P3 и P3. Это дерево имеет вектор цепей (4,3,2,2) и вектор степеней (4,27,14).

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

Доказательство. Необходимость. Пусть T – сверхстройное дерево, а v – его корень. Из определения сверхстройного дерева следует, что степень вершины v является наибольшей среди степеней остальных вершин. Пусть u – произвольная вершина, смежная с v. По определению, она либо является листом, либо имеет степень 2. Но тогда есть еще в точности одна вершина смежная с u, кроме v. Продолжая рассуждение, приходим к выводу, что в дереве T количество листьев равно степени корневой вершины v.

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

Таким образом, вектор степеней сверхстройного дерева имеет вид (k,2,…, 2,1,…,1), где k > 2 и количество листьев равно k. Кратко вектор степеней сверхстройного дерева может быть записан в виде (k,2m,1k). Среди сверхстройных деревьев есть представители других хорошо известных семейств графов.

Мы рассматриваем сверхстройные деревья, у которых степень корневой вершины k > 2. Однако если это ограничение убрать, то при k = или k = 2 сверхстройное дерево является цепью Pn.

Если m = 0, то сверхстройное дерево является звездой K1,k.

Вектора цепей подсказывают способ перечисления всех сверхстройных деревьев с заданным числом вершин n. Так как n = m1 + … + mk + 1, то, построив все разложения числа n – 1 на три и более слагаемых, мы найдем все возможные вектора цепей n-вершинных сверхстройных деревьев.

Количество сверхстройных деревьев с числом вершин 4,5,... есть 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, 127, 168, 222, 288, 375, 480 8,...

Вершина v в графе G называется точкой сочленения, если ее удаление увеличивает число компонент связности. Связный граф без точек сочленения называется неразделимым. Ребро {u, v} в графе G называется мостом, если его удаление увеличивает число компонент связности.

См. последовательность A004250: http://oeis.org/A Если после удаления любых k вершин вместе с инцидентными им ребрами граф остается связным, то говорят, что он k-вершинно связный. Наибольшее k, при котором граф G k-вершинно связный, называется вершинной связностью графа G. Граф с точкой сочленения имеет вершинную связность равную 1.

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

В связном графе расстояние d(u, v) между вершинами u и v есть длина кратчайшей цепи, соединяющей эти вершины. Расстояние от вершины u графа G = (V, ) до наиболее удаленной от неё вершины называется эксцентриситетом e(u) вершины u: e(u ) = max d (u, v ).

Наименьший из эксцентриситетов вершин называется радиусом r(G) графа G, а наибольший – диаметром d(G):

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

Подграфом графа G = (V, ) называется пара G' = (V', '), где V' V и ' = (V 'V ' ). Подграф графа G называется максимальным, если он получается из G удалением одной вершины и всех связанных с ней ребер. Будем обозначать через G – v максимальный подграф, получающийся из графа G удалением вершины v. Через G – F, где F V, будем обозначать подграф, получающийся из графа G удалением всех вершин из F.

Вложением графа G1 = (V1, 1) в граф G2 = (V2, 2) называется такое вершин u, v V1 выполняется следующее условие:

1.1.2. Ориентированные графы Ориентированным графом (далее, для краткости, орграфом) называется пара G = (V, ), где V – конечное непустое множество (множество вершин), V V – отношение на множестве вершин V, называемое отношением смежности. Пара (u, v) называется дугой графа с началом в u и концом v. Дуга вида (u, u ) называется петлей. Вершина, не являющаяся началом никакой дуги, кроме, быть может, петли, называется стоком, а вершина, не являющаяся концом никакой дуги, кроме, быть может, петли, называется источником. Полустепенью исхода d + (v ) вершины v называется число дуг, имеющих вершину v своим началом. Полустепенью захода d (v ) вершины v называется число дуг, имеющих вершину v своим концом. Орграф с универсальным отношением смежности называется полным и обозначается K |V |. По определению K|V | = G (V,V V ).

Орграф G = (V, ) называется направленным графом, или диграфом, если отношение антисимметрично. Полный направленный граф называется турниром. В каждой вершине турнира есть петля, однако при изображении Рис. 1.1.2. 3-вершинные турниры (u, w). На рис. 1.1.2 изображены 3-вершинные турниры, которые называются транзитивной тройкой и циклической тройкой соответственно.

Далее приведено количество n-вершинных орграфов9, диграфов10 и турниров11:

Орграфы 1 3 16 218 Маршрутом в орграфе G = (V, ) называется последовательность дуг (v 0, v1 ), (v1, v 2 ),..., (v n 1, v n ). При этом говорят, что v0 – начальная вершина маршрута, а vn – конечная. Говорят также, что вершина vn достижима из v0.

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

Симметризацией орграфа G = (V, ) называется граф G = (V, ( 1 ) \ ), то есть симметризация орграфа получается заменой дуг ребрами и удалением петель. Например, симметризацией полного орграфа K |V | будет полный неограф K|V |.

См. последовательность A000055: http://oeis.org/A См. последовательность A001174: http://oeis.org/A См. последовательность A000568: http://oeis.org/A Орграф называется связным, если его симметризация является связным графом. Орграф называется сильносвязным, или сильным, если все его вершины взаимно достижимы.

Большинство понятий, сформулированных в предыдущем разделе параграфа для неориентированных графов, без изменений переносятся и на ориентированные графы. Там, где различия существенны, мы будем уточнять отдельно.

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

1.2. Отказоустойчивость В технике большое значение имеют высоконадежные системы, которые могут сохранять работоспособность, даже если некоторые их компоненты выходят из строя. Первые компьютеры, появившиеся в 1940-х годах, отличались своей ненадежностью (Carter, Bouricius, 1971). Например, ENIAC12 – первый электронный цифровой компьютер был построен в 1946 г. и состоял из почти 18000 ламп. Его среднее время наработки на отказ составляло 7 минут, а за 4 года работы задачи решались правильно в 54% случаев. В последующих компьютерах надежность существенно возросла. Разработка EDVAC13 была завершена в 1949 г. при участии фон Неймана. В отличие от ENIAC это был компьютер, основанный на двоичной системе счисления, а не на десятичной. В EDVAC использовалось 2 АЛУ14, результаты работы которых сравнивались для обнаружения отказа. UNIVAC I15 появился в 1951 г. В нем также было реализовано дублирование элементов, кроме этого использоENIAC, сокр. от англ. Electronic Numerical Integrator and Computer.

EDVAC, сокр. от англ. Electronic Discrete Variable Automatic Computer.

АЛУ – арифметико-логическое устройство.

UNIVAC I, сокр. от англ. UNIVersal Automatic Computer I.

вались коды с коррекцией ошибок и контролем четности для передачи и хранения информации. Прошло более 60 лет с момента появления компьютеров.

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

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

В последующие годы исследования в области надежности вычислительных систем проводились весьма интенсивно. Некоторое время назад (Laprie, 1985 ; Dependability …, 1992 ; Aviienis et al., 2004 ; Харченко, 2006 ;

Теслер, 2008 ; Харченко, 2009) стали рассматривать более общее понятие, чем надежность (reliability), – гарантоспособность (dependability). В работе (Aviienis et al., 2004) дается подробная таксономия для гарантоспособности и сопутствующих понятий.

Под системой понимается сущность, которая взаимодействует с другими сущностями, в том числе и с другими системами. Вычислительные системы характеризуются своими фундаментальными свойствами: функциональностью, производительностью, гарантоспособностью, безопасностью и стоимостью. Функциональная спецификация описывает функции системы с точки зрения функциональности и производительности. Под поведением (behavior) системы понимается то, каким образом она реализует свои функции. Поставляемые системой услуги (service) – это поведение системы с точки зрения ее пользователей, то есть потребителей услуг. Обслуживание считается правильным, если предоставленные услуги соответствуют функциям системы. Под гарантоспособностью (dependability) понимается комплексное свойство системы предоставлять требуемые услуги, которым можно оправданно доверять. Свойствами гарантоспособности являются:

готовность (availability) – готовность к правильному обслуживанию;

надежность (reliability) – непрерывность правильного обслуживания;

безопасность (safety) – отсутствие катастрофических последствий для пользователей и окружающей среды;

целостность (integrity) – отсутствие некорректных изменений системы;

обслуживаемость (maintainability) – способность подвергаться модификациям и ремонту.

Угрозами гарантоспособности являются сбои, ошибки и отказы.

Отказ (failure) означает, что предоставляемые системой услуги отличаются от правильных. Отказ означает, что поведение системы в одном или более состояний отличается от ожидаемого поведения при правильном обслуживании. Это отличие называется ошибкой (error). Установленная или гипотетическая причина ошибки называется сбоем (fault). Сбой системы может быть внутренним и внешним. Внутренний сбой может не приводить к ошибке и отказу системы. Отказоустойчивость (fault tolerance) означает возможность избежать отказа системы в присутствии сбоя. Очевидно, что отказоустойчивость является важнейшей предпосылкой для гарантоспособности больших систем. В качестве других средств достижения гарантоспособности отмечаются: предотвращение сбоев (fault prevention), устранение сбоев (fault removal) и предсказание сбоев (fault forecasting).

Считается, что первая теоретическая работа по исследованию отказоустойчивости принадлежит фон Нейману (von Neumann, 1956). Он предложил и исследовал концепцию тройной модульной избыточности, которая и сейчас не утратила актуальности.

Понятие отказоустойчивости было введено Авиженисом (Aviienis, 1967 ; Авиженис, 1978) как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки.

Выделяют два уровня отказоустойчивости:

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

аппаратная избыточность (hardware redundancy) – добавляются копии критических компонентов системы;

программная избыточность (software redundancy) – различные версии программ для выполнения критических операций;

информационная избыточность (information redundancy) – коды для обнаружения и исправления ошибок;

временная избыточность (time redundancy) – повторные выполнения критических операций.

Иногда выделяют и другие уровни. Так, в работе (Теслер, 2008) автор приводит 13 видов избыточности, отдельно выделяя коммуникационную, алгоритмическую, архитектурную избыточности. Каждому из указанных выше уровней посвящены обширные исследования. Более того, в рамках каждого уровня существует множество различных моделей для исследования и построения отказоустойчивых систем. Так, в рамках аппаратной избыточности выделяют статические и динамические модели.

Статическая избыточность означает, что избыточные компоненты используются как постоянная часть системы. Простейшим примером является следующая схема (n-модульная избыточность16): предположим, что некоторый модуль генерирует сигнал X. Разместим n 3 копий этого модуля, сконфигурировав систему так, чтобы все модули работали параллельно. Выходы модулей подаются на вход специального устройства «голосования», выходом из которого является сигнал, чаще других встретившийся на входе. Таким образом, ошибка, порожденная отказавшим модулем, будет маскироваться модулем голосования. При n = 3 получается тройная модульная избыточность17. На рис. 1.2.1 изображены 3 модуля M. Из выходов X1, X2 и X3 этих модулей выбирается такой, который встречается чаще. Устройство голосования Voter в двоичном случае описывается хорошо известной формулой:

Выше уже приводился пример с компьютером EDVAC: использовалось 2 АЛУ, результаты работы которых сравнивались для обнаружения отказа.

Это, однако, не дает отказоустойчивости. В чешском компьютере SAPO использовалась тройная модульная избыточность (Svoboda, 1989), и это позвоN-modular redundancy, NMR (англ.).

Triple modular redundancy, TMR (англ.).

ляет считать SAPO первым отказоустойчивым компьютером. Компонентой может быть не только физический модуль. Разновидностью данной схемы является мультиверсионное (многоверсионное) программирование 18, впервые предложенное в 1977 году Авиженисом и Ченом (Aviienis, Chen, 1977) для программной избыточности: решение задачи пишется независимо, например, N различными группами программистов. Далее эти N различных программ запускаются параллельно. Если выходы программ различаются, то правильным считается тот результат, который встречается чаще. В (Aviienis, Chen, 1977) предполагается, что ошибки, допушенные в реализации, будут отличаться у различных разработчиков, однако эта гипотеза часто оспаривается (см., например, (Knight, Leveson, 1986)). Тем не менее мультиверсионное программирование получило широкое распространение: 2, 3 и 4 версии программы управляют движением поездов и осуществляют контроль полетов (Aviienis, 1995). Дальнейшим развитием идеи является многоверсионное проектирование: различные версии программ реализуют различные алгоритмы и исполняются на различных платформах. Например, система противоаварийной защиты, разработанная фирмой Westinghause, состоит из двух компонент на основе микропроцессоров фирм Intel и Motorola, а программная часть написана на языках С++ и Ada (Харченко, 2009).

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

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

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

N-version programming или multiversion programming (англ.).

3. Восстановление – выполняется приведение системы в рабочее состояние.

Простейшим примером для данной схемы является дублирование устройств. В 1987 году Петтерсон, Гибсон и Катц (Patterson et al., 1988) предложили решение для повышения надежности хранения информации на жестких дисках: RAID – Redundant Array of Inexpensive Disks (избыточный массив недорогих дисков). Со временем RAID стали расшифровывать как Redundant Array of Independent Disks (избыточный массив независимых дисков). RAID представляет собой объединение нескольких жестких дисков в один массив, который воспринимается как единое целое. Существуют различные уровни спецификации RAID. Например, RAID 019 повышает скорость работы дисков без отказоустойчивости: информация разбивается на блоки и записывается на несколько дисков одновременно. В контексте нашего рассмотрения представляет интерес RAID 120, который обеспечивает отказоустойчивость дублированием дисков: информация параллельно записывается на 2n дисков вместо n. В случае выхода из строя одного диска контроллер обнаруживает это и выдает оповещение, однако работа продолжается. Отказавший диск заменяется исправным, на него копируется информация, и отказоустойчивость восстанавливается. На рис. 1.2.2 показан пример системы с двумя дублированными модулями.

Striping (англ.) — «чередование».

Mirroring (англ.) — «зеркалирование».

этих системах была использована достаточно распространенная схема соединения процессоров по топологии гиперкуба. К каждому вычислительному узлу Рис. 1.2.3. Кластер из 16 процессоров чим процессором (рис. 1.2.3).

В случае отказа одного рабочего процессора он заменяется избыточным процессором, и система перестраивает таблицу связей процессоров, так чтобы исключить работу отказавшего процессора. Многие современные суперкомпьютеры используют аналогичные схемы. Например, архитектура Blue Gene фирмы IBM, на основе которой построено несколько десятков суперкомпьютеров, входящих в рейтинг 500 самых мощных общественно известных компьютерных систем мира21. В этой архитектуре один вычислительный модуль состоит из 16 рабочих процессоров, одного системного и одного избыточного.

Рассмотрим модель отказоустойчивости, основанную на графах. Технической системе сопоставляется помеченный граф G(), вершины которого соответствуют элементам системы, ребра (или дуги) – связям между элементами, а метки указывают тип элементов. Под полным отказом элемента системы понимается удаление соответствующей ему вершины из графа системы G() и всех связанных с ней ребер. При полном отказе элемент пеhttp://www.top500.org/ рестает функционировать и информация через него не распространяется.

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

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

Рассмотрим простейшую систему из 4-х однотипных элементов и 3-х связей, графом которой является цепь P4 (рис. 1.2.4, а). Для получения 1-отказоустойчивой реализации достаточно построить новую систему, составленную из двух экземпляров исходной (рис. 1.2.4, б), однако в такой системе будет в два раза больше элементов и связей по сравнению с исходной.

Если взять систему из 5 элементов, в которой каждый элемент связан с каждым (рис. 1.2.4, в), то такая система, очевидно, также будет 1-отказоустойчивой реализацией, однако количество дополнительных связей составит 7.

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

Рис. 1.2.4. Цепь P4 и ее 1-отказоустойчивые реализации Если элементы системы имеют разный тип, то количество избыточных элементов в отказоустойчивой реализации будет больше по сравнению с системой из однотипных элементов. Пусть в системе из рассмотренного примера Рис. 1.2.5. Цепь P4 с вершинами двух типов Пусть в системе встречается t различных типов элементов. Очевидно, что любая ее k-отказоустойчивая реализация должна содержать не менее k дополнительных элементов каждого типа. Легко видеть, что такого числа дополнительных элементов достаточно для построения k-отказоустойчивой реализации системы. В самом деле, добавим k элементов каждого типа и соединим их все между собой и с элементами системы. Тогда любой отказавший элемент можно будет заменить одним из добавленных элементов соответствующего типа. Построенную таким образом (тривиальную) k-отказоустойчивую реализацию можно использовать для оценки числа дополнительных вершин и ребер k-отказоустойчивых реализаций.

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

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

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

Edge fault tolerance (англ.).

Node fault tolerance (англ.).

Недостатком полной отказоустойчивости является ее повышенная стоимость, обусловленная необходимостью введения избыточных элементов и связей. Например, суперкомпьютер последнего поколения серии Blue Gene/Q, созданной фирмой IBM в 2011 г., содержит 65 536 рабочих процессоров и 4096 избыточных процессоров, которые активируются при выходе из строя основных процессоров. В обычном режиме избыточные процессоры не функционируют. В текущем рейтинге, составленном в июне 2013 г., этот компьютер занимает 37-ю позицию с результатом 715.6 Тфлопс24. В данное время самый мощный суперкомпьютер этой серии Sequoia был создан в 2012 г. для Ливерморской национальной лаборатории. Он состоит из 1 572 864 рабочих процессоров и 98 304 избыточных. Его производительность составляет 17 Пфлопс, что почти в два раза превышало производительность суперкомпьютера Fujitsu K computer, который на момент появления Sequoia был самым производительным. В данный момент Sequoia занимает третью строчку, почти в два раза уступая по производительности суперкомпьютеру Tianhe-225.

При амортизации отказов система сохраняет работоспособность, возможно, с частичной потерей функций. Например, система считается работоспособной, если соответствующий ей граф является связным. Система называется вершинной (реберной) k-отказоустойчивой, если после отказа k элементов (связей) система остается работоспособной. Так как минимально связным графом является дерево, то при исследовании такой отказоустойчивости исследуются задачи определения вершинной и реберной k-связности определенных графов (гиперкубы, торы, закольцованные деревья и др.) и вложения в них деревьев (Despain, Patterson, 1978 ; Horowitz, Alessandro, Флопс (FLOPS – от англ. Floating point OPerations per Second) – единица, используемая для измерения производительности компьютеров, показывающая, сколько операций с плавающей запятой в секунду выполняет данная вычислительная система.

http://www.top500.org/list/2013/06/ ; Grey et al., 1984 ; Srinivasan, Sood, 1990) или других структур (Livingston, Stout, 1988 ; Dutt, Hayes, 1991 ; Graham et al., 1993 ; Пархоменко, 2000).

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

1.3. Расширения графов Граф G* = (V*, *) называется вершинным (реберным) k-расширением (k – натуральное) графа G = (V, ), если граф G вкладывается в каждый граф, получающийся из графа G*, удалением любых его k вершин (ребер). Очевидно, что k-расширение должно содержать не менее k дополнительных элементов – вершин или ребер соответственно. Для построения вершинного k-расширения этого оказывается и достаточно: если к произвольному графу G добавить k вершин и соединить их ребрами между собой и с остальными вершинами графа G, то построенный граф, как можно заметить, будет являться вершинным (и реберным) k-расширением графа G. Такое расширение называется тривиальным k-расширением. Легко показать, что выполняется ТЕОРЕМА 1.3.1. Вершинное k-расширение любого графа является и его реберным k-расширением.

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

Пусть граф G* содержит p ребер: e1,…, ep. Если p < k ребер, то, удалив из графа G* по одной вершине каждого ребра, мы получим вполне несвязный граф, в который граф G вкладываться не может. Следовательно, число ребер графа G* больше k.

Выберем произвольные k ребер графа G*: e1,…, ek. Покажем, что граф G* – {e1,…, ek} допускает вложение графа G. Выберем множество F из k вершин графа G*, так чтобы в это множество попало по крайней мере по одной концевой вершине из ребер e1,…, ek. По условию граф G* – F допускает вложение графа G, однако легко видеть, что сам граф G* – F вкладывается в граф G* – {e1,…, ek}. Таким образом, граф G* – {e1,…, ek} допускает вложение графа G. В силу произвольности выбора ребер e1,…, ek получаем, что граф G* является реберным k-расширением графа G.

Заметим, что обратное теореме 1.3.1 утверждение в количества дополнительных вершин. На рис. 1.3.1, а представлен граф P3, его реберные 1-расширения (см. рис. 1.3.1, б и 1.3.1, в), которые не являются вершинными 1-расширениями, и вершинное 1-расширение (см. рис. 1.3.1, г). Для реберного k-расширения может быть недостаточно k дополнительных ребер. Рассмотрим далее оптимизационную задачу: будем уменьшать количество ребер в произвольном k-расширении до тех пор, пока у него будет сохраняться свойство «быть k-расширением». Получившийся граф назовем неприводимым k-расширением. Если в качестве исходного вершинного k-расширения было выбрано тривиальное, то неприводимое вершинное k-расширение называется Тнеприводимым k-расширением. Среди всех неприводимых k-расширений можно выбрать минимальные – те, которые будут иметь минимально возможное число вершин и ребер.

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

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

Граф G* = (V*, *) называется минимальным вершинным k-расширением n-вершинного условия:

граф G* является вершинным k-расширением графа G;

граф G* содержит n + k вершин, то есть |V*| = |V| + k;

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

Граф G* = (V*, *) называется минимальным реберным k-расширением n-вершинного условия:

граф G* является реберным k-расширением G;

граф G* содержит n вершин, то есть |V*| = |V|;

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

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

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

граф G* является вершинным (реберным) k-расширением графа G;

граф G* содержит не более n + k + p вершин, то есть |V*| |V| + k + p;

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

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

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

1.4. Вычислительная сложность В этом параграфе обсудим некоторые общие вопросы, связанные с определением эффективности алгоритмов и вычислительной сложности. Схематично введем основные понятия в соответствии с работами (Гэри, Джонсон, 1982 ; Пападимитру, Стайглиц, 1995), опуская некоторые формальные детали.

Под массовой задачей понимается некоторый общий вопрос, на который требуется дать определенный ответ. Например, найти вершинное k-расширение графа. Также задача содержит определенные параметры, например, граф, для которого требуется найти вершинное k-расширение. Индивидуальная задача получается из массовой, если всем параметрам задачи указаны конкретные значения. В нашем случае это означает задание конкретного графа.

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

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

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

Говорят, что f(n) = O(g(n)), если найдется такая константа c > 0 и такое число n0, что 0 f(n) cg(n) для всех n n0.

Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна O(p(n)), где p(n) – некоторая полиномиальная функция, а n – параметр, описывающий размерность задачи. Алгоритмы, временная сложность которых не поддается такой оценке, называются экспоненциальными. Большинство экспоненциальных алгоритмов представляют собой перебор всех возможных вариантов решения. Говорят, что задача разрешима за полиномиальное время, если существует полиномиальный алгоритм для ее решения. Традиционно полиномиальные алгоритмы считаются хорошими или эффективными, а задачи, для которых не существует полиномиальных алгоритмов решения, называются труднорешаемыми.

Для графов в качестве характеристики размерности индивидуальной задачи обычно используются либо количество вершин n, либо количество ребер m. Для кодирования графа обычно используется матрица смежности, что требует n2 бит, или список ребер, что требует m log2n бит. При «разумных ограничениях» схемы кодирования для одной задачи отличаются не более чем «полиномиальным образом», то есть любой алгоритм, имеющий полиномиальную временную сложность при одной схеме кодирования, будет также обладать полиномиальной временной сложностью при других схемах кодирования. Таким образом, выяснение вопроса, является ли данная задача труднорешаемой, не зависит от выбора конкретной схемы кодирования.

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

Основы теории NP-полных задач заложил С. Кук в работе 1971 г., где доказал, что задача выполнимости булевой формулы является NP-полной.

Затем Карп доказал NP-полноту 21 задачи. В книге Гэри и Джонсона (Гэри, Джонсон, 1982) содержится уже более 300 NP-полных задач. Так, среди задач теории графов можно отметить такие NP-полные задачи: задача о клике, о гамильтоновом цикле, о вершинном покрытии.

В теории сложности рассматриваются задачи распознавания свойств или задачи принятия решений, то есть такие задачи, решениями в которых является ответ «да» или «нет». Класс P26 определяется как класс задач принятия решений, разрешимых за полиномиальное время. Неформально класс P – polinomial (полиномиальные).

NP27 можно определить как класс задач принятия решений, для которых за полиномиальное время можно проверить правильность решения при наличии сертификата решения. Класс P очевидно входит в класс NP: P NP. Если P NP, то задачи из NP \ P являются труднорешаемыми.

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

Рассмотрим известную NP-полную задачу:

ИЗОМОРФИЗМ ПОДГРАФУ

УСЛОВИЕ. Даны графы G = (V, ) и H = (U, ).

ВОПРОС. Верно ли, что в графе G есть часть, изоморфная графу H?

К этой задаче, очевидно, можно полиномиально свести задачу о клике:

верно ли, что заданный граф содержит полный подграф с заданным числом вершин? Интересно, что для относительно похожей по формулировке задачи, в которой требуется ответить на вопрос об изоморфизме данных графов, пока не удалось доказать, что она принадлежит к классу P или является NPполной. Частным случаем задачи об изоморфизме подграфу является другая хорошо известная NP-полная задача:

ГАМИЛЬТОНОВ ЦИКЛ

УСЛОВИЕ. Дан граф G = (V, ).

ВОПРОС. Верно ли, что в графе G имеется гамильтонов цикл?

Задача о гамильтоновом цикле остается NP-полной, если граф G является планарным или кубическим графом.

NP – nondeterministic polinomial (недетерминированные полиномиальные).

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

2.1. Основные определения и свойства Назовем граф GR = (VR, R) вершинным k-расширением (k – натуральное) графа G = (V, ), если граф G можно вложить в каждый подграф графа GR, получающийся удалением любых его k вершин и всех связанных с ними ребер. Заметим, что определение не теряет смысла и при k = 0. Мы будем рассматривать преимущественно графы без меток, однако, если вершины имеют метки, то подразумевается вложение с учетом меток. Если F – некоторый набор вершин графа G, то есть F V, то будем обозначать через G – F граф, получающийся из G удалением всех вершин, принадлежащих F, и связанных с ними ребер. Очевидно, что число вершин любого вершинного kрасширения графа по крайней мере на k вершин каждого типа больше, чем у самого графа. На рис. 2.1.1, а изображена цепь P4, а на рис. 2.1.1, б–д – несколько ее вершинных 1-расширений. Пунктиром обозначаются дополнительные вершины и ребра.

Рис. 2.1.1. Цепь P4 (а) и ее вершинные 1-расширения (б–д) Вершинное k-расширение графа G = (V, ) называется неприводимым, если никакая его собственная часть не является вершинным k-расширением графа G. Например, расширения на рис. 2.1.1, б и д являются неприводимыми 1-расширениями цепи P4, а на рис. 2.1.1, в и г – таковыми не являются.

Граф G t* называется точным вершинным k-расширением графа G, если любой граф, получающийся удалением произвольных k вершин графа G t*, изоморфен графу G. Граф на рис. 2.1.1, д является точным вершинным 1-расширением цепи P4. Очевидно, что точные вершинные k-расширения могут быть только у графов с вершинами одного типа.

Граф Gt = (Vt, t) называется тривиальным k-расширением графа G = (V, ), если граф Gt получается из графа G добавлением k вершин каждого типа, соединением их со всеми вершинами графа G и друг с другом. Для графов с вершинами одного типа граф Gt есть соединение графа G и полного графа Kk = (Vk, k):

Очевидно, что тривиальное k-расширение графа является и его вершинным k-расширением, однако в общем случае оно может не являться неприводимым. На рис. 2.1.1, г показано тривиальное 1-расширение цепи P4, и оно не является неприводимым, так как его часть – граф на рис. 2.1.1, д – тоже является 1-расширением цепи P4. Неприводимое вершинное k-расширение, которое является частью тривиального k-расширения, называется Тнеприводимым k-расширением.

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

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

2. граф G* содержит минимально возможное число вершин;

3. * имеет минимальную мощность при выполнении условий 1) и 2).

Приведенное определение является общим, однако в настоящей работе рассматриваются преимущественно графы с вершинами одного типа, поэтому определение можно переформулировать следующим образом: граф G* = (V*, *) называется минимальным вершинным k-расширением n-вершинного графа G = (V, ) с вершинами одного типа, если выполняются следующие условия:

1. граф G* является вершинным k-расширением графа G;

2. граф G* содержит n + k вершин, то есть |V*| = |V| + k;

3. * имеет минимальную мощность при выполнении условий 1) и 2).

Будем считать, что граф является минимальным вершинным 0-расширением для самого себя. Очевидно, что для любого графа минимальное вершинное k-расширение всегда существует и, как будет видно в дальнейшем, в общем случае не одно. Введем частичную операцию получения минимального вершинного k-расширения графа, считая ее неопределенной для графов, которые имеют более одного минимального вершинного k-расширения.

Пусть G – некоторый граф, а H – его минимальное вершинное k-расширение. Обозначим через (G)*k результат операции получения минимального вершинного k-расширения графа G. Тогда, если граф G имеет единственное минимальное вершинное k-расширение, то (G )*k = H. В противном случае результат операции получения минимального вершинного k-расширения считается неопределенным для графа G. Будем использовать для операции получения минимального вершинного 1-расширения обозначение (G)*.

Граф может иметь несколько неизоморфных неприводимых вершинных k-расширений с различным числом ребер. Граф также может иметь неизоморфные минимальные вершинные k-расширения, однако число ребер у них будет одинаковым. Заметим, что число ребер минимального вершинного k-расширения графа не более чем у его тривиального k-расширения, то есть * + V k + k. Будем говорить, что минимальное вершинное k-расширение содержит * дополнительных ребер. Обозначим через ec(G, k) число дополнительных ребер минимального вершинного k-расширения графа Для любого графа, кроме вполне несвязного, количество дополнительных ребер больше 0. Далее будут описаны графы, у которых Из определения следует очевидный переборный Алгоритм 2.1.1. Построение всех минимальных вершинных k-расширений для заданного графа G, отличного от вполне несвязного.

3. Строим все графы, получающиеся из графа G добавлением k вершин и m дополнительных ребер.

4. Выбираем среди построенных на шаге 3 графов вершинные k-расширения графа G.

5. Если на шаге 4 не было найдено графов, то переходим на шаг 2.

6. Среди графов, выбранных на шаге 4, оставляем по одному представителю от изоморфных графов. Полученные графы будут являться минимальными вершинными k-расширениями графа G.

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

Будем говорить: вершинное расширение, тривиальное расширение, минимальное вершинное расширение, имея в виду вершинное 1-расширение, тривиальное 1-расширение и минимальное вершинное 1-расширение соответственно.

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

Заметим, что все графы с числом вершин меньше 5 имеют единственное с точностью до изоморфизма минимальное вершинное 1-расширение. В работе (Абросимов, 2000, в) приведены минимальные вершинные 1-расширения для графов с числом вершин 5 и 6.

Докажем несколько вспомогательных утверждений о свойствах минимальных вершинных k-расширений.

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

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

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

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

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

Доказательство. Пусть граф G есть n-вершинный граф из условия соответствующей леммы.

Докажем более общие утверждения – все леммы справедливы не только для минимальных вершинных k-расширений, но для любых вершинных Т-неприводимых k-расширений.

Пусть G* – (n + k)-вершинное неприводимое вершинное k-расширение графа G.

Лемма 2.1.1 является частным случаем леммы 2.1.4.

Если бы число вершин степени не ниже s в G* было меньше k + m, то, удалив k таких вершин (если число вершин меньше k, в этом случае можно удалить все вершины степени не ниже s и подходящее количество любых других вершин), был бы получен граф, в котором было бы менее m вершин степени не ниже s. В такой граф нельзя вложить граф G.

Минимальные вершинные 1-расширения 2-, 3- и 4-вершинных графов После удаления любых k вершин из графа G* в получившемся графе должна оставаться по-крайней мере одна вершина степени d. Будем выбирать для удаления из графа G* последовательно k вершин наибольшей степени.

Так как степень каждой вершины не меньше d, то и количество удаленных ребер – не менее kd.

Пусть G* имеет вершину v степени ниже d + k. Рассмотрим подграф, получающийся из G* удалением k смежных с v вершин (если степень вершины v меньше k, то в этом случае можно удалить все смежные с ней вершины и подходящее количество любых других вершин, кроме v). Он будет содержать вершину степени ниже d и в него нельзя будет вложить граф G.

Удаление вершины v наибольшей степени d из графа G* приводит к удалению и d ребер, а по условию граф G* – v допускает вложение графа G.

З а м е ч а н и е 1. Утверждения лемм останутся справедливыми, если вместо минимального вершинного k-расширения рассматривать любое вершинное k-расширение с таким же числом вершин, то есть на k больше, чем у заданного графа (например, Т-неприводимое расширение).

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

леммы формулируются и доказываются для графов с вершинами одного типа. Например, леммы 2.1.1 и 2.1.4 для графов с вершинами разных типов утрачивают свою справедливость. На рис. 2.1.2 представлены соответствующие примеры – полные графы K2 (см. рис. 2.1.2, а) и K3 (см.

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

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

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

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

В некотором смысле доказательство того, что граф G* является неприводимым вершинным k-расширением графа G, несколько проще:

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

Показать, что в графе G* нет ребра {u, v}, такого, что граф G* – {u, v} является вершинным k-расширением графа G.

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

Леммы 2.1.1–2.1.5 позволяют несколько повысить эффективность алгоритма 2.1.1 выбором значения m на шаге 1 и построением на шаге 3 графов с необходимыми свойствами. Еще больше повысить эффективность поиска всех неизоморфных минимальных вершинных k-расширений можно, если заранее известен вектор степеней любого возможного минимального вершинного k-расширения. Подобная ситуация, как будет видно в дальнейшем, возникает, например, при поиске минимальных вершинных расширений циклов (параграф 2.4 данной главы) или при нахождении графов, являющихся точными вершинными расширениями.

Очевидным образом формулируется Алгоритм 2.1.2. Построение всех минимальных вершинных k-расширений для графа G с заданным вектором степеней.

1. Строятся все неизоморфные реализации заданного вектора степеней.

2. Среди построенных графов отбираются вершинные k-расширения Поскольку на шаге 1 требуется организовать поиск всех реализаций для заданного вектора степеней, то этот алгоритм, хотя и позволяет существенно сократить поиск, может быть использован по-прежнему только для небольших значений n (см. например, (Bender, Canfield, 1978)).

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

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

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

Удаление k вершин из полного графа Kn+k приведет к полному графу Kn, то есть граф Kn+k является вершинным k-расширением графа Kn и отличается на k дополнительных вершин.

Пусть G* – минимальное вершинное k-расширение полного n-вершинного графа Kn. По лемме 2.1.4 (n + k)-вершинный граф G* не может содержать вершин степени ниже n – 1 + k, таким образом, полный (n + k)-вершинный граф действительно является минимальным вершинным k-расширением графа Kn.

ТЕОРЕМА 2.1.2. Минимальное вершинное k-расширение, причем единственное с точностью до изоморфизма, вполне несвязного n-вершинного графа On, есть вполне несвязный (n + k)-вершинный граф On+k, то есть справедливо соотношение:

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

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

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

Доказательство. Непосредственной проверкой убеждаемся, что цикл Cn+1 является вершинным 1-расширением цепи Pn. Минимальность следует из лемм 2.1.1, 2.1.3 или 2.1.4.

ТЕОРЕМА 2.1.4. Минимальное вершинное 1-расширение n-вершинной цепи Pn единственно с точностью до изоморфизма, то есть справедливо соотношение:

Доказательство. Пусть граф G* является минимальным вершинным 1расширением цепи Pn. Очевидно, что G* является связным графом, причем по лемме 2.1.4 степень любой его вершины не меньше двух. По теореме 2.1. цикл Cn + 1, содержащий n + 1 ребро, является минимальным вершинным 1расширением цепи Pn, следовательно, граф G* также содержит n + 1 ребро, и, значит, степень любой его вершины в точности равна двум. Заметим, что G* не дерево и, следовательно, содержит цикл некоторой длины k. Если k < n + 1, то нарушается условие связности графа G*, следовательно, k = n + 1, то есть G* изоморфен Cn + 1.

Из леммы 2.1.1 или 2.1.4 следует, что любое минимальное вершинное k-расширение цепи Pn не содержит вершин степени ниже k + 1. Хейз в работе (Hayes, 1976) доказал следующее утверждение:

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

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

Т-неприводимым 1-расширением n-вершинной цепи Pn является (n + 1)-вершинный цикл Cn+1.

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

Т-неприводимым 1-расширением однородного n-вершинного графа является тривиальное 1-расширение.

Доказательство. Пусть G – однородный n-вершинный граф порядка m, а G* – его Т-неприводимое 1-расширение. Очевидно, что G* является связным графом, причем по лемме 2.1.4 степень любой его вершины не меньше m + 1.

Это означает, что из добавленной вершины есть ребро в каждую вершину графа G.

Заметим, что вопрос о Т-неприводимом k-расширении при k > 1 не является столь тривиальным. Так, например, цикл C4 имеет Т-неприводимым 2расширением граф вида O2 + C4, а Т-неприводимым 3-расширением – тривиальное 3-расширение.

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

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

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

Доказательство. Рассмотрим произвольный граф G. Обозначим через d максимальную из степеней его вершин. Пусть далее G* – минимальное вершинное 1-расширение графа G, которое отличается от него на одно дополнительное ребро. Граф G отличен от вполне несвязного, так как минимальное вершинное 1-расширение вполне несвязного графа по теореме 2.1. не имеет дополнительных ребер. Следовательно, d > 0.

По лемме 2.1.3 d < 2, так как в противном случае число дополнительных ребер минимального вершинного 1-расширения было бы больше единицы. Итак, установлено, что d = 1.

Если граф не содержит изолированных вершин, то его степенное множество будет иметь вид {1} – это графы, являющиееся объединением некоторого количества полных 2-вершинных графов K2. По лемме 2.1.1 минимальное вершинное 1-расширение любого такого графа не содержит вершин со степенью ниже 2, а по лемме 2.1.5 количество дополнительных ребер будет также не менее 2. Таким образом, только графы со степенным множеством {1,0} могут иметь минимальное щееся на одно дополнительное ребро.

Покажем, что они действительно имеют такое расширение, причем единственное.

Граф G со степенным множеством {1,0} можно представить в виде K 2... K 2 O p, где p > 0 (см. рис. 2.1.3, а). На рис. 2.1.3, б представлено минимальное вершинное 1-расширение графа G, которое отличается как раз на одно дополнительное ребро. Легко видеть, что других минимальных вершинных 1-расширений граф G иметь не может: при p > 1 минимальное вершинное 1-расширение будет иметь степенное множество {1,0}, а при p = 1 – степенное множество {1}.

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

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

Так как граф G связный, то d > 0. По лемме 2.1.3 d < 3, так как в противном случае число дополнительных ребер минимального вершинного 1-расширения было бы больше двух. Итак, установлено, что d = 1 или d = 2.

Рассмотрим оба случая.

Если d = 1, то граф G это 2-вершинная цепь P2, которая имеет единственное минимальное вершинное 1-расширение – цикл C3, причем количество дополнительных ребер в точности равно двум.

Если d = 2, то граф G может иметь степенное множество либо {2}, либо {2,1}. В первом случае по лемме 2.1.4 его минимальное вершинное 1-расширение не может содержать вершин степени ниже 3, а по лемме 2.1. получаем, что и количество дополнительных ребер должно быть не менее трех.

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

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

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

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

Как было установлено в доказательстве предыдущей теоремы, граф G* является однородным графом порядка 2, а граф G имеет степенное множество вида {2,1}. По условию граф G* отличается от графа G на одну дополнительную вершину и два дополнительных ребра, следовательно, в графе G может быть только две вершины степени 1, которые соединяются в графе G* ребрами с дополнительной вершиной. Из этих рассуждений можно сделать несколько выводов:

1) граф G имеет единственную компоненту, которой является цепь, а все остальные компоненты являются циклами;

2) все компоненты графа G* являются циклами;

3) граф G* – единственное минимальное вершинное 1-расширение графа G.

Докажем, что все компоненты связности графа G* изоморфны.

Обозначим через Pn компоненту связности графа G, являющуюся цепью. Рассмотрим удаление произвольной вершины v в графе G*. Граф G* – v имеет столько же ребер, сколько и граф G, причем граф G вкладывается в граф G* – v, следовательно, G* – v изоморфен графу G. Но тогда компонента графа G* с удаленной вершиной v изоморфна цепи Pn, то есть исходная компонента в графе G* была циклом Cn+1. В силу произвольности выбора получаем, что все компоненты связности в графе G* изоморфны циклу Cn+1, то З а м е ч а н и е. В теоремах 2.1.9 и 2.1.10 минимальные вершинные 1расширения являются и точными вершинными 1-расширениями.

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

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

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

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

Доказательство. Рассмотрим произвольный связный n-вершинный граф G. Пусть G* – минимальное вершинное 1-расширение графа G, которое отличается на три дополнительных ребра. По лемме 2.1.3 в графе G не может быть вершин со степенью больше 3. Перечислим все возможные степенные множества для графа G и затем последовательно их рассмотрим: {1}, {2}, {2,1}, {3}, {3,1}, {3,2}, {3,2,1}. Заметим, что по лемме 2.1.5 в графе G* не можеть быть вершины со степенью больше 3. Кроме того, если в графе G* есть вершина v степени 3, то граф G* – v будет изоморфен графу G: действительно, граф G должен вкладываться в любой максимальный подграф графа G*, но граф G* – v содержит столько же ребер, сколько и граф G, откуда и следует их изоморфизм.

{1}: из связных графов такое степенное множество может иметь только цепь P2, единственное минимальное вершинное 1-расширение которой есть цикл C3.

{2}: из связных графов такое степенное множество могут иметь только циклы Cn. По леммам 2.1.4 и 2.1.5 граф G* должен быть кубическим графом.

Посчитаем количество ребер в графах G и G*: n и 3(n + 1)/2. Тогда количество дополнительных ребер графа G* составит (n + 3)/2. В данном случае только при n = 3 число дополнительных ребер будет равно трем. Цикл C3 изоморфен полному графу и его минимальное вершинK3, ное 1-расширение – полный граф K4 – отличается на три дополнительных ребра. Это пункт 1 из формулировки теоремы.

{2,1}: из связных графов такое степенное множество может иметь только цепь Pn. Единственное минимальное вершинное 1-расширение цепи Pn – цикл Cn+1, и оно отличается на 2 дополнительных ребра.

{3}: по лемме 2.1.4 в графе G* степень вершин будет не ниже 4, а по лемме 2.1.5 число дополнительных ребер тогда будет также не менее 4, следовательно, этот случай исключается.

{3,1}: с учетом леммы 2.1.4 граф G* может иметь степенное множество вида {3} или {3,2}. Первое степенное множество соответствует кубическому графу и в данном случае не подходит, так как при удалении одной вершины кубического графа не может получиться граф с вершиной степени 1. Итак, граф G* может иметь только степенное множество вида {3,2}. Рассмотрим удаление из графа G* произвольной вершины v степени 3. Как было отмечено ранее, граф G* – v изоморфен графу G. Если бы вершина v была смежна хотя G* – v, а значит, и в графе G была бы вершина степени 2, что невозможно. Но тогда в графе G* вершина v должна была быть смежна только с вершинами степени 2. В силу произвольности выбора вершины степени 3 получаем, что граф G* в данном случае может иметь только вид K3,2 = O3 + O2 (см.

Pages: |

| 2 | 3 | 4 | 5 |

Главная >> Диссертации - все темы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«БИКСОЛТ АЛЕКСАНДРА МОИСЕЕВНА ОРГАНИЗАЦИОННО-ПРАВОВЫЕ МЕХАНИЗМЫ ОГРАНИЧЕНИЯ КУРЕНИЯ ТАБАКА В РОССИЙСКОЙ ФЕДЕРАЦИИ 14.02.03. Общественное здоровье и здравоохранение Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : академик...»

«УДК ФИЛИППЕНКО Людмила Викторовна ИНТЕГРАЛЬНЫЕ СВЕРХПРОВОДНИКОВЫЕ ПРИЕМНЫЕ СТРУКТУРЫ НА ОСНОВЕ ВЫСОКОКАЧЕСТВЕННЫХ ТУННЕЛЬНЫХ ПЕРЕХОДОВ Специальность 01.04.01 – Приборы и методы экспериментальной физики Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель : профессор, д.ф.-м.н. Кошелец В.П. МОСКВА – 2009 СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ стр. П1...»

«МАРЧУКОВА Светлана Марковна РАЗВИТИЕ ИДЕИ ПАНСОФИЙНОСТИ В ПЕДАГОГИЧЕСКИХ ТРУДАХ Я.А. КОМЕНСКОГО 13.00.01 – Общая педагогика, история педагогики и образования (педагогические наук и) Диссертация на соискание ученой степени доктора педагогических наук Научный консультант доктор педагогических наук, профессор И.И. Соколова Санкт – Петербург 2014 Оглавление Стр. Введение Глава 1. Основы...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Чарычанская, Ирина Всеволодовна Языковые средства выражения коммуникативного намерения переводчика Москва Российская государственная библиотека diss.rsl.ru 2006 Чарычанская, Ирина Всеволодовна Языковые средства выражения коммуникативного намерения переводчика : [Электронный ресурс] : Дис. . канд. филол. наук : 10.02.19. Воронеж: РГБ, 2005 (Из фондов Российской Государственной Библиотеки) Филологические науки. Художественная литература ...»

«Савинов Андрей Владимирович ПРИЧИНЕНИЕ ВРЕДА ПРИ ЗАДЕРЖАНИИ ЛИЦА, СОВЕРШИВШЕГО ПРЕСТУПЛЕНИЕ, КАК ОБСТОЯТЕЛЬСТВО, ИСКЛЮЧАЮЩЕЕ ПРЕСТУПНОСТЬ ДЕЯНИЯ. Специальность 12.00.08 – уголовное право и криминология; уголовноисполнительное право. Диссертация на соискание учёной степени кандидата юридических наук Научный руководитель – Заслуженный деятель науки РФ, заслуженный юрист РФ, доктор юридических наук, профессор Б. В. Коробейников Москва СОДЕРЖАНИЕ...»

«vy vy из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Степанова^ Елена Васильевна 1. Коммуникативная готовность дошкольника к учебной деятельности 1.1. Российская государственная библиотека diss.rsl.ru 2003 Степанова^ Елена Васильевна Коммуникативная готовность дошкольника к учебной деятельности[Электронный ресурс]: Дис. канд. психол. наук : 19.00.07.-М.: РГБ, 2003 (Из фондов Российской Государственной библиотеки) Педагогическая психология Полный текст: littp: //diss. rsl....»

«Батусова Екатерина Сергеевна ПРАВОВОЕ РЕГУЛИРОВАНИЕ СРОЧНЫХ ТРУДОВЫХ ДОГОВОРОВ В РОССИИ И НЕКОТОРЫХ ЗАРУБЕЖНЫХ СТРАНАХ (СРАВНИТЕЛЬНО-ПРАВОВОЕ ИССЛЕДОВАНИЕ) 12.00.05 - трудовое право; право социального обеспечения Диссертация на соискание ученой степени кандидата юридических наук Научный руководитель доктор юридических наук, профессор Ю.П.Орловский Москва - СОДЕРЖАНИЕ Введение.. Глава 1. История развития...»

«БОЧКОВ ВЛАДИМИР СЕРГЕЕВИЧ ПОВЫШЕНИЕ ИЗНОСОСТОЙКОСТИ НАКЛЕПОМ ФУТЕРОВОК ШАРОВЫХ МЕЛЬНИЦ ПРИ ПРОВЕДЕНИИ ИХ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ Специальность 05.05.06 – Горные машины ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук Научный руководитель доктор...»

«МИНАЕВ АЛЕКСАНДР НИКОЛАЕВИЧ ПОВЕДЕНИЕ ЛОСЯ В УСЛОВИЯХ ДОМЕСТИКАЦИИ (биотелеметрическое исследование) Специальность 03.00.08 зоология Диссертация на соискание ученой степени кандидата биологических наук Москва - 1992. -2ОГЛАВЛЕНИЕ Стр. Введение........... Глава 1. Материал и методика....... Глава 2. Система радиоопределения Лось-2 и оптимальные методы работы с ней...»

«МОХАММАДИ ЛЕЙЛА НАСРОЛЛАХ ИЗМЕНЕНИЕ ЖЕСТКОСТИ СОСУДИСТОЙ СТЕНКИ И ФУНКЦИИ ЭНДОТЕЛИЯ У БОЛЬНЫХ АРТЕРИАЛЬНОЙ ГИПЕРТЕНЗИЕЙ С ФИБРИЛЛЯЦИЕЙ ПРЕДСЕРДИЙ 14.01.05.- кардиология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель – доктор...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Дышлюк, Антон Владимирович Принципы создания оптоэлектронных информационноизмерительных систем мониторинга безопасности эксплуатации техногенных объектов Москва Российская государственная библиотека diss.rsl.ru 2007 Дышлюк, Антон Владимирович. Принципы создания оптоэлектронных информационноизмерительных систем мониторинга безопасности эксплуатации техногенных объектов [Электронный ресурс] : дис. . канд. физ.мат. наук :...»

«Королев Виктор Васильевич АДСОРБЦИОННЫЕ И МАГНИТОТЕПЛОВЫЕ СВОЙСТВА НЕКОТОРЫХ ВЫСОКОДИСПЕРСНЫХ МАГНЕТИКОВ 02.00.04 – физическая химия 02.00.01 – неорганическая химия Диссертация на соискание ученой степени доктора химических наук Иваново – 2014 СОДЕРЖАНИЕ ВВЕДЕНИЕ.. 6 Глава 1. Высокодисперсные магнетики. 1.1. Строение кристаллической решетки и структура...»

«Шибаева Марина Вячеславовна Совершенствование системы управления развитием негосударственных некоммерческих организаций региона в сфере предоставления социальных услуг 08.00.05. – экономика и управление народным хозяйством: региональная экономика; экономика,...»

«ЕФРЕМОВА ВАЛЕНТИНА ЕВГЕНЬЕВНА НАУЧНОЕ ОБОСНОВАНИЕ ОПТИМИЗАЦИИ СИСТЕМЫ УПРАВЛЕНИЯ КАДРОВЫМИ РЕСУРСАМИ СРЕДНЕГО МЕДИЦИНСКОГО ПЕРСОНАЛА ФЕДЕРАЛЬНЫХ МЕДИЦИНСКИХ ОРГАНИЗАЦИЙ 14. 02. 03 - Общественное здоровье и здравоохранение ДИССЕРТАЦИЯ на соискание ученой степени кандидата медицинских наук Научный руководитель :...»

«ЧЕЛНОКОВ АНДРЕЙ АЛЕКСЕЕВИЧ ЗАКОНОМЕРНОСТИ ФОРМИРОВАНИЯ СПИНАЛЬНОГО ТОРМОЖЕНИЯ У ЧЕЛОВЕКА Специальность 03.03.01 – Физиология Диссертация на соискание учёной степени доктора биологических наук Научный консультант – доктор биологических наук, профессор Р.М. Городничев Великие Луки - ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ГЛАВА...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Зиновьева, Эльвира Валерьевна Школьная тревожность и ее связь с когнитивными и личностными особенностями младших школьников Москва Российская государственная библиотека diss.rsl.ru 2006 Зиновьева, Эльвира Валерьевна Школьная тревожность и ее связь с когнитивными и личностными особенностями младших школьников : [Электронный ресурс] : Дис. . канд. психол. наук : 19.00.01. М.: РГБ, 2006 (Из фондов Российской Государственной Библиотеки)...»

«Соколова Евгения Эрхардовна МЕТОДИЧЕСКИЕ ОСНОВЫ ОСУЩЕСТВЛЕНИЯ ОРГАНИЗАЦИОННЫХ ИННОВАЦИЙ В ИНТЕГРИРОВАННЫХ ХОЛДИНГОВЫХ СТРУКТУРАХ 08.00.05 - Экономика и управление народным хозяйством: управление инновациями Диссертация на соискание ученой степени кандидата...»

«Хламова Оксана Геннадьевна КЛИНИКО-ТЕРАПЕВТИЧЕСКИЕ АСПЕКТЫ ГЕРПЕТИЧЕСКОГО СТОМАТИТА НА ФОНЕ ХРОНИЧЕСКОГО ТОНЗИЛЛИТА 14.01.14 – стоматология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : д.м.н., профессор Лепилин А.В....»

«Разумов Николай Геннадьевич ПОЛУЧЕНИЕ ПОРОШКОВОЙ ВЫСОКОАЗОТИСТОЙ АУСТЕНИТНОЙ СТАЛИ МЕТОДОМ МЕХАНИЧЕСКОГО ЛЕГИРОВАНИЯ ЖЕЛЕЗА АУСТЕНИТООБРАЗУЮЩИМИ ЭЛЕМЕНТАМИ В АЗОТОСОДЕРЖАЩЕЙ АТМОСФЕРЕ Специальность 05.16.06 – Порошковая металлургия и композиционные материалы ДИССЕРТАЦИЯ на соискание ученой степени кандидата...»

«ФИЛАТОВА Евгения Валентиновна УПРАВЛЕНИЕ КАЧЕСТВОМ ТРАНСПОРТНО-ЭКСПЕДИЦИОННОГО ОБСЛУЖИВАНИЯ В СФЕРЕ МОРСКИХ ПЕРЕВОЗОК Специальность 08.00.05 Экономика и управление народным хозяйством: экономика, организация и управление предприятиями, отраслями и комплексами (транспорт) Диссертация на соискание ученой степени...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)

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

ГРАФОВЫЕ МОДЕЛИ

ОТКАЗОУСТОЙЧИВОСТИ

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

ИЗОМОРФИЗМ ПОДГРАФУ

ГАМИЛЬТОНОВ ЦИКЛ

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

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)