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

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