|
Записки научных семинаров ПОМИ, 2013, том 417, страницы 86–105
(Mi znsl5706)
|
|
|
|
Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)
Дерево разбиения двусвязного графа
Д. В. Карповab a С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023 Санкт-Петербург, Россия
b Математико-механический факультет СПбГУ, Университетский пр., 28, 198504, Санкт-Петербург, Старый Петергоф
Аннотация:
Дерево разбиения $k$-связного графа набором $\mathfrak S$ из попарно независимых $k$-вершинных разделяющих множеств определяется следующим образом: вершины этого дерева – множества набора $\mathfrak S$ и части разбиения графа этим набором, каждое множество соединено с теми и только теми частями, которые его содержат. В работе доказывается, что построенный таким образом граф является деревом.
Частным случаем этой конструкции является дерево разбиения двусвязного графа. Это дерево разбиения двусвязного графа набором из его одиночных двухвершинных разделяющих множеств (то есть, независимых со всеми остальными двухвершинными разделяющими множествами).
Показано, что дерево разбиения двусвязного графа имеет много общего с классическим деревом блоков и точек сочленения связного графа. С помощью дерева разбиения двусвязного графа доказаны критерии планарности и оценки на хроматическое число этого графа.
Также с помощью дерева разбиения изучена структура критических двусвязных графов и показано, что любой такой граф имеет хотя бы четыре вершины степени 2. Библ. – 11 назв.
Ключевые слова:
связность, двусвязный граф, разбиение, блоки.
Поступило: 31.10.2013
Образец цитирования:
Д. В. Карпов, “Дерево разбиения двусвязного графа”, Комбинаторика и теория графов. VI, Зап. научн. сем. ПОМИ, 417, ПОМИ, СПб., 2013, 86–105; J. Math. Sci. (N. Y.), 204:2 (2015), 232–243
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5706 https://www.mathnet.ru/rus/znsl/v417/p86
|
Статистика просмотров: |
Страница аннотации: | 331 | PDF полного текста: | 90 | Список литературы: | 56 |
|