Брамбл (теория графов)

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

В теории графов ежевика — это для неориентированного графа G семейство связных подграфов G , которые все соприкасаются друг с другом: для каждой пары непересекающихся должно существовать ребро, подграфов в G имеющее одну конечную точку в каждом подграфе. Порядок попаданий ежевики — это наименьший размер множества , набора вершин графа G , имеющего непустое пересечение с каждым из подграфов. Ежевику можно использовать для характеристики дерева ширины G .

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

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

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

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

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

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

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

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

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

Понятие ежевики также было определено для ориентированных графов. В ориентированном графе D ежевика представляет собой набор сильно связных подграфов D , которые все соприкасаются друг с другом: для каждой пары непересекающихся элементов X , Y ежевики в D должна существовать дуга из X в Y и одна из Y до X. От Порядок попаданий ежевики — это наименьший размер множества , набора вершин D , имеющего непустое пересечение с каждым из элементов ежевики. Число ежевики D — это максимальный порядок ежевики в D .Число ежевики ориентированного графа находится в пределах постоянного фактора его направленной ширины дерева.