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

ID: 51928126