Структура связности графа

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

Оглавление
Введение

Актуальность темы диссертации

Цели диссертации

Основные положения и результаты, выносимые на защиту

Методы исследований

Новизна, степень достоверности и апробация результатов

Теоретическая значимость диссертации

Обозначения

Вершинная связность

Дерево блоков и точек сочленения

Части разбиения, граница и внутренность
Содержание диссертации
Структура диссертации
1 Деревья разбиения
1.1 Дерево разбиения для набора попарно независимых множеств
1.2 Дерево разбиения двусвязного графа
1.3 Применение дерева разбиения двусвязного графа
1.4 Дерево разрезов
2 Минимальные /с-связные графы

ОГЛАВЛЕНИЕ З
2.1 Минимальные /с-связные графы с минимальным количеством вершин степени к
2.2 Минимальные двусвязные графы
2.3 Структура минимальных Ансвязных графов при к <
3 Гипердерево и теорема разбиения
3.1 Гиперграф и гипердерево
3.2 Гипердерево Struct(V)
4 Компоненты зависимости
4.1 Некоторые технические леммы
4.2 Взаимное расположение компонент зависимости
5 Удаление вершин из /с-связного графа
5.1 Удаление вершин из двусвязного графа с сохранением дву-связности
5.2 Удаление вершин из Апсвязного графа при к >
6 Остовные деревья
6.1 Нижняя оценка на u{G) через количество вершин степеней
3 и не менее 4
6.2 Нижняя оценка на u(G) через количество вершин степеней
1, 3 и не менее
6.3 Нижняя оценка на u(G), учитывающая вершины степени 2 .
Заключение
Литература

Введение
Актуальность темы диссертации
Теория графов является важным, интересным и динамично развивающимся разделом дискретной математики. Одним из классических направлений исследований в теории графов являются исследования по вершинной связности графов. Понятие к-связного графа является естественным обобщением понятия связного графа. Это подчеркивает и классическая теорема Менгера, с которой в 1927 году фактически начались исследования по связности. Их продолжили Уитни, Татт, Форд и Фалкерсон, Дирак, Халин, Мадер и другие. В 60-80 годы XX века был всплеск интереса к связности графов. Сейчас продолжают появляться новые работы по этой тематике, пусть и не в таком количестве, как 30 лет назад.
Диссертация посвящена исследованию структуры взаимного расположения разделяющих множеств наименьшего размера в графе. Остановимся на классических аналогах решаемых в диссертации задач. Понятия блоков и точек сочленения связного графа хорошо известны и весьма полезны, с их помощью доказано немало утверждений, причем не только о связности графов. Помогает работать с блоками структура дерева блоков и точек сочленения, описанная, например, в классической книге Ф.Харари “Теория графов” [57]. Именно структура дерева позволяет успешно применять блоки в доказательствах.
Поэтому неоднократно возникали вопросы об аналогичной структуре

ВВЕДЕНИЕ

с помощью гипердерева ЭПисД©).
Определение 28. Пусть Д = {@1,... ©„} — гиперребро БПисД©). Для всех г 6 {1,... ,п} пусть Аг 6 РаП(©г) — часть, содержащая множества всех остальных компонент зависимости из Д. Тогда множество вершин
назовем частью, соответствующей гиперребру R (даже в случае, когда
Именно из-за того, что не каждому гиперребру Struct(6) соответствует часть Part(©), не получается ввести на компонентах зависимости и частях Part(©) структуру дерева, как в случае с набором из попарно независимых множеств. Будет доказано, что часть А, соответствующая гиперребру R гипердерева Struct(©) не принадлежит Part(©) только в одном случае: Л Є © и гиперребро R состоит ровно из двух компонент зависимости, одна из которых — это {А}, а другая компонента зависимости имеет часть разбиения с границей А.
Следующая теорема описывает части Part(©) с помощью гипердерева Struct (©).
Теорема 4.2. Пусть G — к-связный граф, © С 93fc(G). Тогда выполняются следующие утверждения.
1) Пусть & Є Comp(©) и часть А Є Part(©') таковы, что А не содержит множеств из © ©'. Тогда А є Pa.rt(©).
2) Пусть Н Є Part(©). Тогда либо часть Н соответствует некоторому гиперребру R, гипердерева Struct(©), либо существует такая компонента зависимости & Є Comp(©); что Н Є Part(©').

А ^ Part(©)).