Аннотация:
Граф называется $k$-связным, если в нем более $k$ вершин и удаление любых $k-1$ вершины оставляет граф связным. Работа посвящена исследованию взаимного расположения $k$-вершинных разделяющих множеств. В случае $k=1$ структура графа описывается так называемым деревом блоков и точек сочленения, где блоками называются максимальные двусвязные подграфы, а точками сочленения — вершины, удаление которых делает граф несвязным. Случай $k=2$ был описан Таттом, а случай $k=3$ — Карповым и Пастором. В обоих случаях разделяющие множества можно разбить на просто описываемые комплексы разделяющих множеств таким образом, что один комплекс не разбивает другой. При этом единственным комплексом, содержащим потенциально сколь угодно много разделяющих множеств, является комплекс ромашки. Этот комплекс порожден набором разделяющих множеств, разбивающих граф на части, на которых можно задать циклический порядок. В работе обобщатся определение ромашки, доказываются базовые утверждения для нее — про внутренние множества ромашки и про то, что набор лепестков и центр задают ромашку. Далее для 4-связного графа доказываются утверждения про разделяющие множества, содержащиеся в множестве вершин ромашки. Еще одно утверждение посвящено описанию взаимного расположения двух ромашек с пустым центром, имеющих общее внутреннее множество.
|
