Laboratory of Mathematical Logic at PDMI

Пятница, 15 марта, ауд. 203. Начало в 18:00.

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

Тема: Дерево разбиения двусвязного графа.

Abstract

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

Поэтому неоднократно возникали и возникают попытки построения для графов большей связности структуры, аналогичной по своим свойствам дереву блоков и точек сочленения. В 1966 году Татт построил дерево, отображающее структуру расположения двухвершинных разделяющих рёбер в двусвязном графе.

Мы предложим наш взгляд на эту проблему и построим {\it дерево разбиения} для двусвязного графа, а также в более общем случае --- для набора из попарно независимых разделяющих множеств в -связном графе. В целом наша конструкция похожа на дерево, построенное Таттом, но мы используем другие средства для описания структуры --- понятие {\it части разбиения}.

В результате мы получим дерево, которое несколько более похоже на классическое дерево блоков и точек сочленения. Важно не только построить структуру, но и показать, как она применяется. С помощью дерева разбиения мы повторим доказательства критерия планарности двусвязного графа (S.MacLane, 1937), выведем несложную оценку на хроматическое число графа через хроматические числа его частей разбиения, а также поймем, как выглядят минимальные и критические двусвязные графы.