Home

Пятница 16 мая, 15-00, ауд. 203

Пятница, 16 мая, ауд. 203. Начало в 15:00.

Докладчик: Д.В. Карпов (ПОМИ РАН).

Тема: Дерево разрезов и минимальный k-связный граф..

Abstract

Будем называть разрезом $ k $-связного графа $ G $ его $ k $-элементное разделяющее множество из вершин и рёбер, содержащее хотя бы одно ребро. Мы определим понятие зависимых и независимых разрезов и докажем, что структуру взаимного расположения любого множества попарно независимых разрезов без общих рёбер в $ k $-связном графе можно отобразить с помощью дерева, которое мы назовём деревом разрезов. С помощью дерева разрезов мы исследуем структуру минимальных $ k $-связных графов (то есть, таких, которые теряют $ k $-связность при удалении любого ребра) для $ k\le 5 $.