Структурные свойства k-связных графов

• Автор: Пастор, Алексей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Санкт-Петербург
• Количество страниц: 93 с.

О г лаъЛ0ние

в ПЛДОХТТТЛ

Вершинная связность и ^-связные графы

Критические ^-связные графы и удаление вершин без потери

/г-связности

Разбиение £;-связного графа на блоки. Дерево блоков

Минимальные ^-связные графы и удаление ребер без потери

^-связности

Структура диссертации

1. Основные понятия

1.1. Вершинная связность графа
1.2. Разделяющие множества и фрагменты
1.3. Простейшие свойства минимальных фрагментов
1.4. Зависимые и независимые разделяющие множества
2. Избыточные множества и минимальные фрагменты не-расщепимого /г-связного графа
2.1. Удаление вершин из минимальных фрагментов
3. Блоки и деревья блоков ^-связного графа
3.1. Понятие блока для &-связного графа
3.2. Удаление внутренней вершины блока
3.3. Деревья блоков ^-связного графа

4. Избыточные ребра А:-связного графа 8(
4.1. Избыточные ребра и минимальные фрагменты
Литература
Введение
Вершинная связность и к-связные графы
Рассматриваемое в данной диссертации понятие вершинной связности графа является естественным обобщением понятия связности и, по этой причине, имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования понятия вершинной связности можно найти в книге [1, глава 20].
Начало активных исследований свойств ^-связных графов, то есть графов, содержащих как минимум к + 1 вершину, и сохраняющих связность при удалении произвольных к — 1 вершин, было положено в 1927 году работой [25]. Примерно с середины 60-х годов XX века начались исследования такого специфического свойства ^-связных графов, как сохранение ^-связности графа при удалении его вершин и ребер.
Общеизвестно, что в любом связном графе существует вершина, в результате удаления которой получается связный граф. Однако прямое обобщение этого утверждения на случай Аэсвязных графов не верно. Например, простой цикл является двусвязным графом, однако при удалении любой его вершины образуется граф, не являющийся двусвязным. По этой причине, естественным образом возникает вопрос

G = G — {а} не является /г-связным. Тогда k(G) — к — 1. Заметим, что Vq > к, поскольку граф G содержит все вершины множества R, которых ровно к, и все вершины множества У#3, которое не пусто. Следовательно, в графе G есть (к — 1)-разделяющее множество Т. Тогда множество Ti = TU {а} является «-разделяющим множеством графа G.
Заметим, что подграф Н не может состоять ровно из одной вреши-ны, так как иначе Уя С Ti, что противоречит слабой нерасщепимости графа G. Обозначим через Н граф Н — {а}. Пусть G2, G3,..., Gn — компоненты связности графа G — R, отличные от Н.
Как следует из леммы 1.3, граф Н* является (к + 1)-связным, а графы С?2,...,(т* являются fc-связными. Заметим, что тогда граф (H)*gR = Н* — {а} является fc-связным.
Поскольку граф G является слабо нерасщепимым, множество Т не может содержать все вершины одного из подграфов Н, G2,..., Gn. Следовательно, по пункту 1 леммы 1.5, одна из компонент связности графа G — Т (совпадающего с графом G — Т) должна состоять из не более чем вершин множества R. Но существование такой компоненты связности противоречит слабой нерасщепимости графа G. □
Следствие 2.1. Никакие два минимальных фрагмента слабо нерас-щепимого Ансвязного графа G не пересекаются.
Доказательство. Пусть множества вершин минимальных фрагментов Н и Н2, отделяемых fc-разделяющими множествами i?i и R2 соответственно, имеют непустое пересечение.
Заметим, что, поскольку фрагмент Н2 не содержится в фрагменте Ні и оба фрагмента связны, существует ребро (а, Ь) є E[G), такое, что а Є Vff2 V#i и Ь Є Vff1 П Уя2. Но, поскольку вершина Ъ принадлежит фрагменту Hi, она может быть смежна только с вершинами множе-