"Записки научных семинаров ПОМИ"
Том 475, стр. 41-92
О структуре трёхсвязного графа. 2
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский
государственный университет,
Университетский пр. 28,
Старый Петергоф,
198504 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
В статье исследуется структура взаимного расположения 3-вершинных разделяющих множеств трёхсвязного графа.
Все такие множества разбиты на структурные единицы --- {\em комплексы} ромашек, разрезов, одиночных множеств и тривиальные комплексы. Разбиение графа каждым комплексом подробно описано.
Доказано, что для любых двух комплексов ${\mathcal C}_1$ и ${\mathcal C}_2 $ трёхсвязного графа $G$ существует единственная часть разбиения графа комплексом ${\mathcal C}_1$, содержащая ${\mathcal C}_2 $. Взаимное расположение комплексов описано с помощью {\em гипердерева} ${\mathcal T}(G)$ -- гиперграфа, в котором любой цикл -- подмножество одного из гиперрёбер.
Также доказано, что каждая непустая часть разбиения графа $G$ набором из всех 3-вершинных разделяющих множеств либо является частью разбиения графа одним из комплексов, либо соответствует гиперребру ${\mathcal T}(G)$.
Статью можно рассматривать как продолжение исследований, начатых в статье Д. В. Карпова и А. В. Пастора {\em О структуре трёхсвязного графа}, опубликованной в 2011 году.
Библ. -- 10 назв.
- Ключевые слова: связность, трёхсвязный граф, разделяющее множество
[connectivity, 3-connected graph, cutset]
Полный текст(.pdf)