В статье исследуется структура взаимного расположения 3-вершинных разделяющих множеств трёхсвязного графа. Все такие множества разбиты на структурные единицы — комплексы ромашек, разрезов, одиночных множеств и тривиальные комплексы. Разбиение графа каждым комплексом подробно описано.
Доказано, что для любых двух комплексов C1 и C2 трёхсвязного графа G существует единственная часть разбиения графа комплексом C1, содержащая C2. Взаимное расположение комплексов описано с помощью гипердерева T(G) — гиперграфа, в котором любой цикл — подмножество одного из гиперрёбер. Также доказано, что каждая непустая часть разбиения графа G набором из всех 3-вершинных разделяющих множеств либо является частью разбиения графа одним из комплексов, либо соответствует гиперребру T(G).
Статью можно рассматривать как продолжение исследований, начатых в статье Д. В. Карпова и А. В. Пастора О структуре трёхсвязного графа, опубликованной в 2011 году. Библ. — 10 назв.
Язык оригиналарусский
Страницы (с-по)41-92
ЖурналЗаписки научных семинаров ПОМИ
Том475
СостояниеОпубликовано - 2018

    Области исследований

  • связность, трёхсвязный граф, разделяющее множество

ID: 51928126