Точные расширения графов

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

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОДЫ ПОСТРОЕНИЯ ТОЧНЫХ РАСШИРЕНИЙ ГРАФОВ

§ 1. Основные определения и вспомогательные утверждения

§ 2. Алгоритмы поиска точных расширений графов и диграфов

2.1. Максимальные коды графов

2.2. Точные расширения неориентированных графов

2.3. Точные расширения диграфов

§ 3. Алгоритмы поиска точных расширений турниров

У 3.1. Генерация турниров

3.2' Распределенная система вычислений

3.3. Алгоритм поиска точных расширений турниров

§ 4. Семейства точных расширений графов
4.1'. Вершинно-симметрические графы
4.2. Транзитивные турниры
4.3. Операция вершинной подстановки
ГЛАВА 2. ТОЧНЫЕ РАСШИРЕНИЯ ГРАФОВ
§ 1. Точные расширения неориентированных графов
§ 2. Несвязные точные расширения орграфов
§ 3. Точные расширения орграфов, имеющих встречные дуги
§ 4. Бесконтурные точные расширения орграфов
§ 5. Сильно связные точные расширения орграфов
§ 6. Единственность точного расширения
ГЛАВА 3. ТОЧНЫЕ Х-РАСШИРЕНИЯ ГРАФОВ ПРИ Х>
§ 1. Семейства точных к-расширений при любом к >
§ 2. Поиск точных 2-расширений турниров
§ 3. Семейство точных 2-расширений турниров
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ 1. ТОЧНЫЕ РАСШИРЕНИЯ ДИГРАФОВ
ПРИЛОЖЕНИЕ 2. ТОЧНЫЕ РАСШИРЕНИЯ ТУРНИРОВ

Введение
В прикладной теории графов особое место занимают задачи нахождения графов, подграфы которых обладают определенными свойствами. Одной из самых известных таких задач является задача описания графов, каждый максимальный подграф которых содержит гамильтонов цикл. Данную задачу можно обобщить и рассматривать графы, каждый максимальный подграф которых содержит в качестве своей части заданный* граф. Графы такого вида оказались очень полезными при описании и конструировании отказоустойчивых систем.
В 1976 году Хейзом была предложена модель отказоустойчивости, основанная, на* графах [6]. Технической системе X сопоставляется граф С7(Х), вершины которого соответствуют элементам системы X, ребра - связям между элементами. В общем случае элементы могут быть.разного типа, однако чаще всего на практике элементы системы оказываются однотипными. Говорят, что система X* является к-отказоустойчивой. реализацией системы X, если отказ любых к элементов системы X* приводит к- графу, в который можно вложить граф системы X.
Предложенная Хейзом модель может быть использована для исследования полной- отказоустойчивости системы, то есть возможности продолжения ее работы без потери функциональных свойств при отказе одного или нескольких элементов [1]. В зависимости от интерпретации отказа в дайной модели рассматривают несколько видов отказоустойчивости. Вершинная отказоустойчивость предполагает в качестве отказа рассматривать отказ элемента [5, 6]. Реберная отказоустойчивость рассматривает отказы, связей между элементами [4].
В «чистой» теории графов для; формализации понятий отказоустойчивости системы используется абстрактная конструкция

расширение графа. Основным объектом исследования в данной работе является частный случай расширения графа-точное расширение.
Ориентированным графом {орграфом или просто графом) G называется пара (V, а), где V — конечное непустое множество {множество вершин), а а — отношение в множестве V {отношение смежности). Неориентированным графом {неографом) называется орграф с антирефлексивным и симметричным отношением смежности. Элементы множества а называются дугами для« орграфа и ребрами для неориентированного графа; Орграф G = (V, а) называется направленным графом или диграфом, если его отношение а антисимметрично, то есть нет встречных дуг за исключением, быть, может, петель. Полный' диграф; без петель называется турниром. У турнира между любымшдвумя различными вершинами существует в-точности одна-дуга.
Неориентированный граф, любые две вершины которого смежны, называется полным и обозначается Кп. Граф с пустым отношением смежности, а называется вполне несвязным или нульграфом и обозначается О
•Подграфом графа G = {V, а) называется пара G' = {V, а% где V'œ V и a’ = {V'x V) п а. Подграф графа- G называется- максимальным, если он получается, из G удалением одной вершины- и всех связанных с нею ребер. Будем обозначать через G - v максимальный подграф, получающийся из графа G удалением вершины v. Список максимальных подграфов графа G называют его колодой.
Два графа G = (Гь сс) и Gz = {V2,М2) называются изоморфными, если можно установить взаимно однозначное соответствиеfV—> V2, сохраняющее отношение смежности: {и, v) є а <=> {/{u),J{v)) є а2, для любых и, v є Vj. В этом случае пишут G = G2.
Изоморфизм графа на себя называется- автоморфизмом. Тождественное отображение является автоморфизмом для любого графа. Множество автоморфизмов графа G относительно операции суперпозиции автоморфизмов
Поскольку у диграфа встречных дуг быть не должно, значит, очевидно, что, поставив единицу на вторую позицию, мы теперь обязаны поставить на
последнюю позицию ноль.
N Всего циркулянтов Неориентированных циркулянтов Направленных циркулянтов Турниров циркулянтов

6 20
7 14
8. 46 12 9 '
9 51*
10* 140
11 108
12 624
13 352 14 63*
14 О О 48 125 о-
15 2172
16 4262
17 4116
Таблица Т.4.1. Циркулянты с малым числом вершин.
Получается, что множество S в данном случае имеет вид:
S= {х е /, /с Z„ {0} | х е / —» п-х й /}.
Турниры - это полные диграфы, значит,.все ограничения на множество S из пункта для диграфа-циркулянта остаются в силе. Однако, случаи когда и х, и п-х одновременно отсутствуют в Sнеобходимо исключить.
S= {x е I,IczZn {0} |х е 1->п-х й IИх й I—> п-х е'Г}.
Очевидно, что если п - четное, то, когда п/2 е S, то и п - nil = и/2 е S и наоборот. Это означает, что турнир циркулянт можно построить только с нечетньм числом вершин.
В данном случае, если.представить множество.S двоичным вектором, то получается,, что при* построении турниров-циркулянтов достаточно перебрать только половину этого вектора. А вторая половина' вектора получается из. первой, если ее перевернуть и инвертировать. Количество перебираемых в этом случае множеств S будет равно 2(п~1)/2 [12].