"Записки научных семинаров ПОМИ"

Том 417, стр. 86-105

Дерево разбиения двусвязного графа

Д. В. Карпов

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН Фонтанка 27, 191023 Санкт-Петербург, Россия; СПбГУ Университетский пр., 28, 198504, Санкт-Петербург, Старый Петергоф

dvk0@yandex.ru

Аннотация: Дерево разбиения $k$-связного графа набором $\mathfrak S$ из попарно независимых $k$-вершинных разделяющих множеств определяется следующим образом: вершины этого дерева -- множества набора $\mathfrak S$ и части разбиения графа этим набором, каждое множество соединено с теми и только теми частями, которые его содержат. В работе доказывается, что построенный таким образом граф является деревом. Частным случаем этой конструкции является дерево разбиения двусвязного графа. Это дерево разбиения двусвязного графа набором из его одиночных двухвершинных разделяющих множеств (то есть, независимых со всеми остальными двухвершинными разделяющими множествами). Показано, что дерево разбиения двусвязного графа имеет много общего с классическим деревом блоков и точек сочленения связного графа. С помощью дерева разбиения двусвязного графа доказаны критерии планарности и оценки на хроматическое число этого графа. Также с помощью дерева разбиения изучена структура критических двусвязных графов и показано, что любой такой граф имеет хотя бы четыре вершины степени 2. Библ. -- 10 назв.
Ключевые слова:связность, двусвязный граф, разбиение, блоки [connectivity, biconnected graph, decomposition, blocks]

Полный текст(.pdf)