Пятница, 16 мая, ауд. 203. Начало в 15:00.
Докладчик: Д.В. Карпов (ПОМИ РАН).
Тема: Дерево разрезов и минимальный k-связный граф..
Abstract
Будем называть разрезом $k$-связного графа $G$ его $k$-элементное разделяющее множество из вершин и рёбер, содержащее хотя бы одно ребро.
Мы определим понятие зависимых и независимых разрезов и докажем, что структуру взаимного расположения любого множества попарно независимых разрезов без общих рёбер в $k$-связном графе можно отобразить с помощью дерева, которое мы назовём деревом разрезов.
С помощью дерева разрезов мы исследуем структуру минимальных $k$-связных графов (то есть, таких, которые теряют $k$-связность при удалении любого ребра) для $k\le 5$.
