|
|
Заседания Московского математического общества
13 декабря 2016 г., г. Москва, ГЗ МГУ, аудитория 16-10
|
|
|
|
|
|
Структура связности графа
Д. В. Карпов |
Количество просмотров: |
Эта страница: | 293 |
Фотогалерея
|
Аннотация:
В докладе пойдет речь о структуре разбиения графа его
разделяюшими множествами минимальной величины.
Классическое дерево блоков и точек сочленения хорошо известно
и нашло многочисленные применения, причем не только в теории
графов. Однако, его аналоги для графов большей связности
известны гораздо хуже. Так, описанная в 1966 году Таттом
структура разбиения двусвязного графа его двухвершинными
разделяющими множествами практически не нашла применений за
столько лет.
В докладе будет рассказано о деревьях, отображающих разбиение
$k$-связного графа его $k$-элементными разделяюшими
множествами. Отдельно будет разобран случай $k=2$ и ряд применений
структуры в этом случае.
В качестве приложения построенных структур будет рассказаны
о классических и новых результатах по минимальным $k$-связным
графам.
|
|