Введение
1 Деревья разбиения 44
1.1 Дерево разбиения для набора попарно независимых множеств 44
1.2 Дерево разбиения двусвязного графа 48
1.3 Применение дерева разбиения двусвязного графа 53
1.4 Дерево разрезов 61
2 Минимальные /с-связные графы
2.1 Минимальные /с-связные графы с минимальным количеством вершин степени к 72
2.2 Минимальные двусвязные графы 97
2.3 Структура минимальных /с-связных графов при к 5 113
3 Гипердерево и теорема разбиения 122
3.1 Гиперграф и гипердерево 122
3.2 Гипердерево Struct(V) 125
4 Компоненты зависимости 128
4.1 Некоторые технические леммы 129
4.2 Взаимное расположение компонент зависимости 134
5 Удаление вершин из /с-связного графа 141
5.1 Удаление вершин из двусвязного графа с сохранением дву-связности 141
5.2 Удаление вершин из /с-связного графа при к 2 144
6 Остовные деревья 158
6.1 Нижняя оценка на u{G) через количество вершин степеней 3 и не менее 4 158
6.2 Нижняя оценка на u{G) через количество вершин степеней 1, 3 и не менее 4 201
6.3 Нижняя оценка нам(С), учитывающая вершины степени 2 232
Заключение 242
Литература
