skip to Main Content

(начало в 18 час. 30 мин., ауд. 16-10 Главного здания МГУ)

Д.В.Карпов
Структура связности графа

В докладе пойдет речь о структуре разбиения графа его разделяюшими
множествами минимальной величины.

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

В докладе будет рассказано о деревьях, отображающих разбиение
$k$-связного  графа его $k$-элементными разделяюшими множествами.
Отдельно будет разобран случай $k=2$ и ряд применений  структуры
в этом случае.

В качестве приложения построенных структур будет рассказаны о
классических и новых результатах по минимальным $k$-связным графам.