Деревья и структура связности графа

Первая проблема, которой посвящён доклад — выделение в связном графе остовного дерева с большим количеством листьев. Будет рассказано о различных оценках на это количество и показаны серии примеров графов, на которых оценки достигаются. Вторая проблема — построение дерева, отображающего структуру разбиения $k$-связного графа его $k$-вершинными разделяющими множества. Для связных графов есть классическое дерево блоков и точек сочленения, которое широко применяется в теории графов (причём не только в теории связности). Уже для двухсвязного графа аналогичная конструкция намного сложнее. Мы расскажем про такую конструкцию для $k=2$ и ее применение, а также про различные обобщения на случай $k>2$. В докладе будет рассказано об истории этих вопросов и некоторых новых результатах автора.