В теорії графів ожиною для неорієнтованого графу G називається сімейство зв'язних підграфів графу G, які дотикаються один з одним: для будь-якої пари підграфів, які не мають спільних вершин, має існувати ребро, кінцеві вершини якого лежать в цих двох підграфах. Порядок ожини - це найменший розмір множини вершин G, яка має непорожній перетин з кожним підграфом ожини. Ожини використовують для опису деревної ширини графу G.
Деревна ширина й укриття ред.
Укриттям порядку k в графі G називається функція β, яка переводить кожну множину X з числом вершин менше k в зв'язний компонент G − X таким чином, що будь-які дві підмножини β(X) і β(Y) дотикаються між собою. Тобто, образи β утворюють ожину з порядком k в G. І навпаки, будь-яку ожину можна використати для створення укриття — для кожної множини X з розміром, меншим від порядку ожини, є єдиний зв'язний компонент β(X), що містить всі підграфи в ожині, не зв'язані з X.
Як показали Сеймур і Томас, порядок ожини (або, що еквівалентно, укриття) описує деревну ширину — граф має ожину порядку k в тому і тільки в тому випадку, коли деревна ширина не менша від k − 1.
Розмір ожин ред.
Як помітили Грох[en] і Маркс (Marx), експандери з обмеженим степенем мають деревну ширину, пропорційну числу вершин, і щоб включити всі підграфи, які не мають спільних вершин з кожною підмножиною такого розміру, ожина для таких графів повинна містити експоненціально багато різних підграфів. Точніше, для цих графів навіть ті ожини, порядок яких трохи більший від квадратного кореня з деревної ширини, повинні мати експоненціальний розмір. Однак Грох і Маркс також показали, що будь-який граф з деревною шириною k має ожину поліноміального розміру і порядок .
Обчислювальна складність ред.
Оскільки ожини можуть мати експоненціальний розмір, не завжди можливо побудувати їх за поліноміальний час для графів з необмеженою деревною шириною. Однак якщо деревна ширина обмежена, поліноміальний час побудови можливий — є можливість знайти ожину порядку k, якщо така існує, за час , де n — число вершин у графі. Можливі навіть швидші алгоритми для графів з малим числом мінімальних сепараторів.
Бодлендер[en], Григор'єв і Костер вивчали евристичні алгоритми пошуку ожин високого порядку. Їхні методи не завжди давали ожини з порядком, близьким до деревної ширини, але для планарних графів вони дають постійний апроксимаційний коефіцієнт. Крейцер і Тазарі пропонують імовірнісні алгоритми пошуку з поліноміальним часом роботи на графах з деревною шириною k ожин поліноміального розміру і порядку , що відповідає логарифмічному множнику порядку, виведеного Грохом і Марксом (Grohe, Marx, 2009) для існування ожин поліноміального розміру.
Примітки ред.
- ↑ Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // Journal of Combinatorial Theory. — 1993. — Т. 58, вип. 1 (25 жовтня). — С. 22–33. — (Series B). — DOI:. В цій статті ожини названо «сітками» (screens), а їх порядки - «товщиною».
- Martin Grohe, Dániel Marx. On tree width, bramble size, and expansion // Journal of Combinatorial Theory. — 2009. — Т. 99, вип. 1 (25 жовтня). — С. 218–228. — (Series B). — DOI:..
- 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:.
- Bodlaender. Treewidth lower bounds with brambles. — Algorithmica. — 2008. — Т. 51. — С. 81–98. — DOI:.
- Stephan Kreutzer, Siamak Tazari. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). — 2010. — С. 354–364..