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

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

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

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

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

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

Розмір ожин

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

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

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

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