Минимальные расширения графов

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. НЕИЗОМОРФНЫЕ МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ГРАФОВ
§ 1. Основные понятия и вспомогательные утверждения
§ 2. Наименьшие графы с неизоморфными минимальными расширениями
§ 3. Минимальные расширения циклов
ЗЛ. Неизоморфные минимальные расширения циклов
3.2. Негамильтоновы минимальные расширения циклов
ГЛАВА 2. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ДОПОЛНЕНИЙ ГРАФОВ
§ 1. Определения и постановка задачи
§ 2. Свойство дополнительности к-расширения графа
2.1. Дополнительность расширения
2.2. Дополнительность к-расширения
§ З.Точные к-расшнрения графов
ГЛАВА 3. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ СОЕДИНЕНИЙ ГРАФОВ
§ 1. Основные определения и постановка задачи
§ 2. Соединения с одновершинным графом
2.1. Предполные графы
2.2. Минимальные расширения
2.3. Минимальные к-расширения
§ 3. Соединения графа и его минимального расширения
ГЛАВА 4. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ОБЪЕДИНЕНИЙ ГРАФОВ
§ 1. Основные определения и постановка задачи
§ 2. Объединения графов с цепями
2.1. Цепь и вполне несвязный граф
2.2. Объединения цепей
2.3. Сверхстройные деревья
§ 3. Минимальные расширения объединений циклов
§ 4. Объединения с вполне несвязными графами
§ 5. Объединения графа и его минимального расширения
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ А. Минимальные расширения малых графов
ПРИЛОЖЕНИЕ Б. Минимальные расширения циклов
ПРИЛОЖЕНИЕ В. Точные расширения графов
ВВЕДЕНИЕ
В данной работе вводится в рассмотрение и исследуется конструкция минимального расширения графа, основанная на идеях формализации понятия отказоустойчивости технических систем, предложенных в 1976 году Хейзом [20].
Согласно Авиженису [3] можно выделить два подхода для повышения надежности реальных вычислительных систем: предотвращение ошибок и отказоустойчивость. Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоко-надежных компонент системы. Во втором - используется введение в систему избыточных структур для придания ей дополнительных свойств отказоустойчивости.
Впервые понятие отказоустойчивости было введено Авиженисом (см. [2], [48]) как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют следующие уровни отказоустойчивости:
1) полная отказоустойчивость - система продолжает работать в присутствии ошибок, без существенной потери функциональных свойств;
2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.
В рамках первого направления в 1976 году Хейз предложил модель для исследования отказоустойчивости, основанную на графах.
Графом (далее: ориентированным графом) называется пара С ^ ( V, а), где V - непустое множество, называемое множеством вершин, а а - отношение на множестве вершин V, называемое отношением смежности. Граф с симметричным и антирефлексивным отношением смежности называется неориентированным графом (везде далее просто графом). Если (п,у) е а, то говорят, что вершины и И V смежны и эти вершины соединены ребром {и, V). При этом (и, у) и (у, и) это одно и то же ребро, которое обозначают {и, у}. Граф,

любые две вершины которого смежны, называется полным и обозначается Кщ.
Граф с пустым отношением смежности а называется вполне несвязным и обозначается Ощ.
Степенью вершины у в неориентированном графе Є будем называть количество вершин в Сг, смежных с данной, и обозначать через й?(у). Вектор, составленный из степеней вершин графа Є в порядке их убывания, называется вектором степеней. Говорят, что граф является реализацией своего вектора степеней. Однородным или регулярным н-вершинным графом IIпорядка р называют граф, в котором все степени вершин равны р.
Путем в графе Є = (V, а) называется последовательность вершин и ребер вида v0,{v0,v1},v1,...,{vn_1,vи},vn. При этом говорят, что г0 - начальная вершина пути, а у„ — конечная. Говорят также, что путь соединяет вершины Уо и у„ и вершина у„ достижима из v0. Путь, каждая вершина которого принадлежит не более чем двум его ребрам, считается простым. Если начальная вершина простого пути совпадает с конечной, путь называют циклом, в противном случае - цепью. Цикл или цепь, содержащие все вершины графа, называются гамильтоновыми. Граф, содержащий гамильтонов цикл, также называется гамильтоновым.
Будем считать, что каждая вершина достижима из самой себя. Тогда отношение достижимости является отношением эквивалентности на множестве вершин графа. Классы этого отношения называются компонентами связности графа. Граф с универсальным отношением достижимости называется связным. Связный граф без циклов называется деревом.
Цепью Рп называется граф С = (Г, а), где У= (уь у2, ..., у„}, и «= {(у,-, у,): |/ —] = 1}, а циклом Сп - граф Є = (V, а), где V- {уь Уг,..., т„}, и «= {(Г, у,): |/-/'| = 1} II {(уь у„), (у„,уі)}.
Подграфом графа С = (V, а) называется пара Є' = (П, ос'), где ГсК и а'= (Г'хГ') п а. Подграф графа С называется максимальным, если он получается из С удалением одной вершины и всех связанных с нею ребер.

ГЛАВА 2.
МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ДОПОЛНЕНИЙ ГРАФОВ
Настоящая глава посвящена исследованию связи операции дополнения графа и введенной конструкции минимального ^-расширения графа. Особый интерес представляет случай, когда минимальное ^-расширение дополнительного графа является дополнением минимального ^-расширения графа.
В первом параграфе даются определения понятий, используемых на протяжении главы. Дается определение свойства дополнительности ^-расширения для графа. Формулируется постановка задачи описания графов, обладающих этим свойством, и приводятся иллюстрирующие примеры.
Во втором параграфе доказываются результаты, являющиеся полным ответом на поставленную в первом параграфе задачу. Первый результат (теорема 2.2.4) - критерий дополнительности 1-расширения графа.
Выполненные на основании этого критерия компьютерные расчеты позволили найти все графы с небольшим числом вершин, обладающие свойством дополнительности 1-расширения. В приложении В приводятся все графы с числом вершин до 11, обладающие свойством дополнительности расширения. Второй важный результат параграфа (теорема 2.2.5) - утверждение о том, что только полные и вполне несвязные графы обладают свойством дополнительности ^-расширения при к> 1.
В третьем параграфе дается определение точного ^-расширения графа, впервые введенное Харари и Хейзом в работе [17]. Точные ^-расширения среди минимальных ^-расширений в некотором смысле являются самыми оптимальными, так как не содержат «лишних» ребер - после удаления произвольных Аг-вершин оставшаяся часть изоморфна исходному графу.