Ожина (теорія графів)

В теорії графів ожиною для неорієнтованого графу G називається сімейство зв'язних підграфів графу G, які дотикаються один з одним: для будь-якої пари підграфів, які не мають спільних вершин, має існувати ребро, кінцеві вершини якого лежать в цих двох підграфах. Порядок ожини - це найменший розмір множини вершин G, яка має непорожній перетин з кожним підграфом ожини. Ожини використовують для опису деревної ширини графу G.

Ожина порядку чотири в 3×3 ґратці, що складається з шести попарно дотичних зв'язних підграфів

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

Докладніше: Деревна ширина (теорія графів) та Укриття (теорія графів)

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

Як показали і , порядок ожини (або, що еквівалентно, укриття) описує деревну ширину — граф має ожину порядку k в тому і тільки в тому випадку, коли деревна ширина не менша від k − 1.

Розмір ожин

Як помітили ^[en] і Маркс (Marx), експандери з обмеженим степенем мають деревну ширину, пропорційну числу вершин, і щоб включити всі підграфи, які не мають спільних вершин з кожною підмножиною такого розміру, ожина для таких графів повинна містити експоненціально багато різних підграфів. Точніше, для цих графів навіть ті ожини, порядок яких трохи більший від квадратного кореня з деревної ширини, повинні мати експоненціальний розмір. Однак Грох і Маркс також показали, що будь-який граф з деревною шириною k має ожину поліноміального розміру і порядок ${\displaystyle \Omega (k^{1/2}/\log ^{2}k)}$.

Обчислювальна складність

Оскільки ожини можуть мати експоненціальний розмір, не завжди можливо побудувати їх за поліноміальний час для графів з необмеженою деревною шириною. Однак якщо деревна ширина обмежена, поліноміальний час побудови можливий — є можливість знайти ожину порядку k, якщо така існує, за час ${\displaystyle O(n^{k+2})}$, де n — число вершин у графі. Можливі навіть швидші алгоритми для графів з малим числом мінімальних сепараторів.

^[en], Григор'єв і Костер вивчали евристичні алгоритми пошуку ожин високого порядку. Їхні методи не завжди давали ожини з порядком, близьким до деревної ширини, але для планарних графів вони дають постійний апроксимаційний коефіцієнт. Крейцер і Тазарі пропонують імовірнісні алгоритми пошуку з поліноміальним часом роботи на графах з деревною шириною k ожин поліноміального розміру і порядку ${\displaystyle \Omega (k^{1/2}/\log ^{3}k)}$, що відповідає логарифмічному множнику порядку, виведеного Грохом і Марксом (Grohe, Marx, 2009) для існування ожин поліноміального розміру.

Примітки

1. Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // . — 1993. — Т. 58, вип. 1 (19 червня). — С. 22–33. — (Series B). — DOI:10.1006/jctb.1993.1027. В цій статті ожини названо «сітками» (screens), а їх порядки - «товщиною».
2. Martin Grohe, Dániel Marx. On tree width, bramble size, and expansion // . — 2009. — Т. 99, вип. 1 (19 червня). — С. 218–228. — (Series B). — 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. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-03816-7_20..
4. Bodlaender. Treewidth lower bounds with brambles. — . — 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..