Bramble (теория графов) - Bramble (graph theory)

Ежевика четвертого порядка в сеточном графе 3 × 3, состоящая из шести соприкасающихся друг с другом связанных подграфов

В теории графов ежевика для неориентированный граф грамм это семья связаны подграфы из грамм все соприкасаются друг с другом: для каждой пары непересекающихся подграфов должно существовать ребро в грамм который имеет по одной конечной точке в каждом подграфе. В порядок ежевики - наименьший размер ударная установка, набор вершин грамм который имеет непустое пересечение с каждым из подграфов. Брамблс может использоваться для характеристики ширина дерева из грамм.^[1]

Ширина деревьев и убежища

А убежище порядка k в графике грамм это функция β который отображает каждый набор Икс менее чем k вершины связной компоненты грамм − Икс, таким образом, что каждые два подмножества β(Икс) и β(Y) касаются друг друга. Таким образом, набор изображений β образует кусты в грамм, с заказом k. И наоборот, каждый кустик можно использовать для определения убежища: для каждого набора Икс размером меньше порядка ежевики, имеется уникальный компонент связности β(Икс), который содержит все подграфы ежевики, не пересекающиеся с Икс.

Как показали Сеймур и Томас, порядок терновника (или, что то же самое, убежища) характеризует ширина дерева: на графике есть кусты порядка k если и только если он имеет ширину не менее k − 1.^[1]

Размер ежевики

Графики расширителей ограниченного степень имеют ширину дерева, пропорциональную количеству вершин, и, следовательно, также имеют кусты линейного порядка. Однако, как Мартин Гроэ и Даниэль Маркс показал, что для этих графиков кусты такого высокого порядка должны включать экспоненциально много множеств. Более того, для этих графиков даже ежевики, порядок которых немного больше квадратного корня из ширины дерева, должны иметь экспоненциальный размер. Однако Гроэ и Маркс также показали, что каждый график ширины дерева k имеет куст полиномиального размера и порядка ${ Displaystyle Omega (к ^ {1/2} / log ^ {2} к)}$.^[2]

Вычислительная сложность

Поскольку ежевики могут иметь экспоненциальный размер, не всегда возможно построить их в полиномиальное время для графов неограниченной ширины дерева. Однако, когда ширина дерева ограничена, возможна конструкция с полиномиальным временем: можно найти куст порядка k, если он существует, за время O (п^k + 2) куда п - количество вершин в данном графе. Для графов с небольшим количеством минимальных разделителей возможны еще более быстрые алгоритмы.^[3]

Бодлендер, Григорьев и Костер^[4] изучал эвристику для поиска ежевики высокого порядка. Их методы не всегда генерируют кусты порядка, близкого к ширине дерева входного графа, но для плоских графов они дают постоянную коэффициент аппроксимации. Крейцер и Тазари^[5] предоставлять рандомизированные алгоритмы что на графиках ширины деревьев k, найти ежевики полиномиального размера и порядка ${ Displaystyle Omega (к ^ {1/2} / log ^ {3} к)}$ за полиномиальное время, входя в логарифмический коэффициент порядка, показанного Гроэ и Маркс (2009) существовать для ежевики полиномиального размера.

Направленные ежевики

Понятие ежевики также было определено для ориентированных графов.^[6][7] В ориентированный граф D, а ежевика это собрание сильно связанный подграфы D все касаются друг друга: для каждой пары непересекающихся элементов Икс, Y ежевики, должна существовать дуга в D из Икс к Y и один из Y к Икс. В порядок ежевики - наименьший размер ударная установка, набор вершин D которое имеет непустое пересечение с каждым из элементов ежевики. В число ежевики из D это максимальный порядок куста в DЧисло колючек ориентированного графа находится в пределах постоянного множителя ширины его направленного дерева.^[8]

Рекомендации