Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Петербургский топологический семинар им. В. А. Рохлина
2 марта 2015 г. 17:30–19:00, г. Санкт-Петербург, ПОМИ, комн. 311 (наб. р. Фонтанки, 27)
 


Обобщенные ромашки в $k$-связном графе

А. Л. Глазманab

a Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН
b University of Geneva

Количество просмотров:
Эта страница:127

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