Laboratory of Mathematical Logic at PDMI

Пятница, 31 марта, комната 106. Начало в 17:30.

Докладчик: Д. Карпов.

Тема: Структура разбиения трехсвязного графа.

Abstract

Структура разбиения связного графа его точками сочленения (то есть, вершинами, удаление которых делает граф несвязным) широко известна. В 1966 году W.T.Tutte описал структуру взаимного расположения двухвершинных разделяющих множеств в двусвязном графе и показал, что она имеет много общего со структурой точек сочленения. Аналогичных результатов для произвольных графов большей связности до последнего времени не было..

В докладе будет описана структура взаимного расположения трехвершинных разделяющих множеств (вершинно) трехсвязного графа G. Мы представим набор, состоящий из всех 3-разделяющих множеств графа G, как объединение нескольких поднаборов --- структурных единиц разбиения --- которые мы назовем комплексами.

Мы перечислим все виды комплексов, опишем все 3-разделяющие множества каждого комплекса и разбиение графа множествами одного комплекса. Далее с помощью теоремы о разбиении мы построим гипердерево взаимного расположения множеств различных комплексов. В результате получится полная картина взаимного расположения трехвершинных разделяющих множеств в произвольном трехсвязном графе.