Ежевика (теория графов)

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

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

Древесная ширина и укрытияПравить

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

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

Размер ежевикПравить

Как заметили Грох и Маркс (Grohe, Marx), экспандеры с ограниченной степенью имеют древесную ширину, пропорциональную числу вершин, и чтобы включить все подграфы, не имеющие общих вершин с каждым подмножеством такого размера, ежевика для таких графов должна содержать экспоненциально много различных подграфов. Точнее, для этих графов даже те ежевики, порядок которых чуть больше квадратного корня из древесной ширины, должны иметь экспоненциальный размер. Однако Грох и Маркс также показали, что любой граф с древесной шириной k имеет ежевику полиномиального размера и порядок $\mathrm{\Omega <!--\; \Omega \; -->}(k^{1/2}/{\log }^2<!--\; \; -->k)$$\Omega (k^{1/2}/\log ^{2}k)$ .

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

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

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