Заседание Московского математического общества 17 мая 2016 г.

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

Д.В.Карпов

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

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

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

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

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

======================================================

Доклад Д.В.Карпова, запланированный на 17 мая, отменяется в связи с болезнью докладчика. 
Возможно, он будет перенесен на 24 мая, о чем будет объявлено дополнительно.
Категория: 
Наука