RUS  ENG
Полная версия
СЕМИНАРЫ

Заседания Московского математического общества
13 декабря 2016 г., г. Москва, ГЗ МГУ, аудитория 16-10


Структура связности графа

Д. В. Карпов

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


© МИАН, 2024