Ежевика (теория графов) (Y'yfntg (mykjnx ijgskf))

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

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

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

[править | править код]

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

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

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

[править | править код]

Как заметили Грох и Маркс (Grohe, Marx), экспандеры с ограниченной степенью имеют древесную ширину, пропорциональную числу вершин, и чтобы включить все подграфы, не имеющие общих вершин с каждым подмножеством такого размера, ежевика для таких графов должна содержать экспоненциально много различных подграфов. Точнее, для этих графов даже те ежевики, порядок которых чуть больше квадратного корня из древесной ширины, должны иметь экспоненциальный размер. Однако Грох и Маркс также показали, что любой граф с древесной шириной k имеет ежевику полиномиального размера и порядок [2].

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

[править | править код]

Поскольку ежевики могут иметь экспоненциальный размер, не всегда возможно построить их в полиномиальное время для графов с неограниченной древесной шириной. Однако если древесная ширина ограничена, полиномиальное время построения возможно — есть возможность найти ежевику порядка k, если такая существует, за время , где n — число вершин в графе. Возможны даже более быстрые алгоритмы для графов с малым числом минимальных сепараторов[3].

Бодлендер, Григорьев и Костер[4] изучали эвристические алгоритмы поиска ежевик высокого порядка. Их методы не всегда давали ежевики с порядком, близким к древесной ширине, но для планарных графов они дают постоянный аппроксимационный коэффициент. Крейцер и Тазари[5] предлагают вероятностные алгоритмы поиска с полиномиальном времени работы на графах с древесной шириной k ежевик полиномиального размера и порядка , что соответствует логарифмическому множителю порядка, выведенного Грохом и Марксом (Grohe, Marx 2009) для существования ежевик полиномиального размера.

  1. 1 2 Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // Journal of Combinatorial Theory. — 1993. — Т. 58, вып. 1. — С. 22–33. — doi:10.1006/jctb.1993.1027.. В этой статье ежевики названы «сетками» (screens), а их порядки названы «толщиной».
  2. Martin Grohe, Dániel Marx. On tree width, bramble size, and expansion // Journal of Combinatorial Theory. — 2009. — Т. 99, вып. 1. — С. 218–228. — doi:10.1016/j.jctb.2008.06.004..
  3. Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings. — Berlin: Springer, 2009. — Т. 5734. — С. 223–234. — doi:10.1007/978-3-642-03816-7_20..
  4. Bodlaender. Treewidth lower bounds with brambles. — Algorithmica. — 2008. — Т. 51. — С. 81–98. — doi:10.1007/s00453-007-9056-z..
  5. Stephan Kreutzer, Siamak Tazari. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). — 2010. — С. 354–364..