Разбиения $k$-связного графа на части

В статье изучается разбиение графа набором разделяющих множеств. Найдена точная верхняя оценка числа получающихся частей. Исследована структура набора в случае достижения этой оценки. Кроме того, результат Д. В. Карпова о числе частей в разбиении передоказан при более слабых предположениях о графе. В статье также доказана теорема о пограничных частях, дающая верхнюю оценку числа частей разбиения, граничащих с данной вершиной.
Работа выполнена при поддержке программы фундаментальных исследований Президиума РАН “Исследования в основных областях современной математики” и программы Президента Российской Федерации поддержки ведущих научных школ, грант НШ-2203.2003.1.