Т-неприводимые расширения графов

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

Общая характеристика работы

Содержание работы

Глава I. Свойства Т-неприводимых расширений

1. Основные определения

2. Основные свойства Т-неприводимых расширений

Глава II. Т-неприводимые расширения деревьев

1. Т-неприводимые расширения цепей колес

2. Т-неприводимые расширения пальм

3. Т-неприводимые расширения полных бинарных деревьев

3.1. Полные бинарные деревья: первый подкласс

3.2. Полные бинарные деревья: второй подкласс

3.3. Полные бинарные деревья: третий подкласс
Глава III. Т-неприводимые расширения объединений графов
1. Т-неприводимые расширения для объединений в классах цепей и колес
2. Т-неприводимые расширения объединений некоторых графов с вполне несвязным графом
3. Т-неприводимые расширения объединений полных графов
Заключение
Литература
Приложение 1. Каталог Т-неприводимых расширений для 3-, 4-, 5- и 6ВЕРШИННЫХ ГРАФОВ
Приложение 2. Каталог Т-неприводимых расширений для деревьев с числом вершин не более

Общая характеристика работы
Актуальность проблемы. В последние десятилетия значительно расширилась область применения автоматизированных систем в различных областях деятельности человека. В связи с этим возникает необходимость в повышенных требованиях надежности. Одним из показателей надежности системы является ее отказоустойчивость. Согласно Авиженису [27,5], отказоустойчивость - это свойство системы сохранять полностью свою работоспособность при наличии в ней отказов. Для обеспечения отказоустойчивости необходимо вводить в систему избыточные элементы, которые активируются при возникновении отказа.
В 1976 году Хейз [30] формализовал понятие отказоустойчивости в терминах теории графов. Он рассматривал дискретную систему в виде графа, вершинами которого являются элементы этой системы, а ребра представляют связи между элементами. Вообще говоря, элементы системы взаимно не заменяемы и, следовательно, вершины графа будут иметь метки. В этом случае для обеспечения отказоустойчивости придется вводить в систему добавочные компоненты каждого типа. Тогда общую задачу нахождения отказоустойчивой реализации можно свести к анализу подсистем, состоящих из одинаковых типов элементов. А это, в свою очередь, сводится к построению некоторого расширения графа, задающего систему с однотипными элементами.
Расширением «-вершинного графа Я называется граф Я с «+1 вершинами такой, что (7 вкладывается в каждый максимальный подграф графа Я. Для любого графа существует по крайней мере одно расширение, называемое тривиальным. Это расширение получается соединением исходного графа (7 с одновершинным графом. Хейз выделил из всего множества расширений графа С подмножество оптимальных. В качестве критерия оптимальности он предложил минимальность количества ребер в

расширении. Такие расширения называются минимальными. Задача описания минимальных расширений для произвольного графа остается нерешенной и представляется чрезвычайно трудной. К настоящему времени получен ряд нетривиальных результатов. Сделаем обзор наиболее интересных направлений поисков.
Хейз предложил процедуру нахождения одного из минимальных расширений для цикла. М.Б. Абросимов обнаружил еще одну серию минимальных расширений для циклов. Им же исследовались вопросы поведения конструкции минимальных расширений относительно операций над графами и были получены некоторые частные результаты, связанные с вопросами минимальных расширений для объединений и для соединений графов [2,3]. Ряд работ посвящен нахождению минимальных расширений для класса деревьев - связных графов без циклов. Так Фаррад и Доусон охарактеризовали минимальные расширения для звездных графов [29]. Харари и Хуррум описали минимальные расширения для особого вида деревьев - гусениц [34]. М.А. Кабанов указал одно из минимальных расширений для специального класса деревьев - цепей колес [11]. М.Б. Абросимов нашел [2] минимальные расширения для сверхстройных деревьев особого вида.
В 1993 году Харари и Хейз [32] (см. также [31]) отмечают, что отказать может не только элемент системы. Связь между элементами тоже может оказаться поврежденной. Поэтому они предлагают конструкцию реберных расширений (граф Я с п вершинами называется реберным расширением п-вершинного графа б, если С вкладывается в любой граф, полученный из Я удалением одного ребра). Интересные результаты в этом направлении представлены Чоу и Сю [28], которые рассматривали минимальные реберные расширения графов, представляющих собой решетку.
Хотя дискретные системы, которые должны обладать свойством отказоустойчивости, сами по себе считаются достаточно надежными, но все же теоретически возможен отказ более чем одного элемента. В связи с этим в

определенный в условии теоремы граф Я будет единственным ТНР для пальмы IV^, если И>4 или Л=4 и п>2. ■
3. Т-неприводимые расширения полных бинарных деревьев
Один из известных классов деревьев образуют и-арные деревья.
Дерево является п-арньш, если любая его вершина имеет степень не больше п+1.
В 1976 году Хейз решал задачу нахождения минимальных расширений для и-арного дерева с метками [30]. Самым простым, но чрезвычайно важным классом я-арных деревьев являются 2-арные (или бинарные) деревья. В этом разделе рассматриваются полные бинарные деревья и их ТНР.
Полным бинарным деревом называется дерево с п>3 вершинами, у которого все вершины имеют степень 1 (листья) или 3 (узловые вершины), кроме одной вершины степени 2, называемой корнем.
Обозначим корень дерева как и0, а две смежные с ним вершины через м, и и2 (см. рис. 5). Поддерево дерева Г, образованное всеми потомками вершины и и содержащее Рис 5 Подное бшарное дерево т саму вершину и, назовем поддеревом,
порожденным вершиной и, и обозначим Т(и). Для краткости поддерево Т(и) будем обозначать через Ти а поддерево Т(и2) через Г2.
Будем считать, что в дереве Т всего к узловых вершин и / листьев. Так как п = т +1, где т - количество ребер в дереве, то п = т + = (Зк+2+1)/2 + , а так как п = к + 1 + , то можно записать, что к = (п-3)/2. Отсюда видно, что п - нечетное. Для ТНР полного бинарного дерева справедлива следующая теорема.