Структура разбиения κ-связного графа

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

Связность

Блоки в /с-связном графе. Структура разбиения /;;-связиого графа

Результаты диссертации

Разделяющие множества и части разбиения

Блоки ^-связного графа

Зависимые и независимые множества. Компоненты зависимости

Ромашки

Слабо нерасщепимые графы

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

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

1.1. Части разбиения

1.1.1. Представление части разбиения в виде пересечения
1.1.2. Граница и внутренность
1.1.3. Блоки
1.2. Зависимые и независимые разделяющие множества
1.2.1. Независимые разделяющие множества
1.2.2. Разбиение ^-связного графа парой зависимых ^-разделяющих множеств
1.3. Свойства правильных частей разбиения

2 Компоненты зависимости набора разделяющих множеств
2.1. Пополнение и замыкание набора разделяющих множеств
2.2. Компоненты зависимости набора разделяющих множеств
2.3. Новые свойства пополнения и замыкания набора разделяющих множеств
2.4. Разбиение графа набором из попарно независимых множеств
2.5. Процесс разбиения /г-связного графа
3 Ромашки и квазиромашки
3.1. Циклический порядок лепестков квазиромашки
3.2. Разбиения без малых частей
3.3. Сруктура разбиения двусвязного графа
4 Слабо нерасщепимые графы. Основные свойства
5 Структура разбиения слабо нерасщепимого й-связного
графа
5.1. Классы /г-разделяющих множеств
5.2. Доминирующие множества. Границы и внутренняя область класса
5.3. Множества независимого класса
5.4. Множества большого комплекса
5.5. Разбиения графа комплексами
Литература

Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики — алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
В диссертации мы будем рассматривать неориентированные графы без петель и кратных ребер, множество вершин графа О мы всегда будем обозначать через К(С?), а множество его ребер — через Е(0).
Связность
Одним из основных понятия в теории графов является понятие связности. Граф называется связным, если между любыми двумя его вершинами существует путь. Множество вершин несвязного графа разбивается на компоненты связности. (Под компонентой связности мы понимаем максимальное по включению множество вершин графа, любые две из которых связаны путем.)
Граф называется (вершинно) к-связным, если в нем не менее к + 1 вершин и при удалении любых к — 1 вершин получается связный граф. Связностью двух вершин х и у графа О называется наименьшее количество вершин, которое необходимо удалить из О для того, чтобы в оставшемся графе вершины х и у оказались в разных компонентах связности. Вершинная связность двух смежных вершин считается равной +оо. Обозначается вершинная связность х и у через ка{х,у). Вершинная связность графа С? — это наименьшая вершинная связность

ется граф И, не являющийся (к + 1)-связным и ^-разделяющее множество 5і+і в этом графе. Пусть {1}-разбиение графа ¥ состоит из частей Ну Пр. Тогда граф И заменяется на графы Щ Н*, которые в силу леммы 2.7 также являются ^-связными.
Опишем результат работы этого алгоритма на языке разбиения графа наборами ^-разделяющих множеств.
Теорема 2.3. Пусть на п шагах работы описанного выше алгоритма разбиения /с-связного графа С? последовательно проводились разрезы по множествам 5і 5„, а в результате получены ^-связные графы О і От. Пусть © = {£і 5„}. Тогда выполняются следующие утверждения.
1) © С ІЯк(0), причем множества набора © попарно независимы.
2) Р{&) = {П(<3!) У(СГО)}, причем Су = У{СіУ для
всех і Є {1 т}.
3) Если после п шага алгоритм разбиения закончил работу, то © — максимальный по включению набор попарно независимых ^-разделяющих множеств графа (7.
Доказательство. 1) Утверждение пункта 1 теоремы следует из пункта 1 леммы 2.7.
2) Докажем утверждение пункта 2 индукцией, по количеству множеств в наборе 6. База для одного множества очевидна. Пусть &І = {©'х Д}.
Предположим, что для набора ©, мы доказали утверждение пункта 2, Пусть Р{&і) = {Ди..., Д}, тогда после первых і шагов работы алгоритма мы получили /г-связные графы И* Д*. На следующем шаге один из этих графов был “разрезан” по множеству Д+ь Не умаляя общности предположим, что это был граф Иу. Тогда Д+і С Д.