Укриття (теорія графів)

В теорії графів укриття — це певний тип функції на множині вершин неорієнтованого графу. Якщо укриття існує, ним може скористатись утікач, щоб виграти гру переслідування-ухилення на графі, використовуючи цю функцію на кожному кроці гри для визначення безпечних множин вершин, куди можна перейти. Укриття вперше ввели Сеймур і Томас як засіб характеризації деревної ширини графів. Інші застосування цього поняття — доведення існування малих сепараторів у замкнутих за мінорами сімействах графів і опис країв і мінорів клік нескінченних графів.

Визначення

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

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

Ожина порядку чотири. Укриття, отримане з цієї ожини, відображає кожну множину X із трьох і менше вершин в унікальну зв'язну компоненту графу G \ X, яка включає принаймні один підграф ожини.

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

Приклад

Як приклад: нехай G — ґратка з дев'ятьма вершинами. Визначимо укриття порядку 4 в G, відобразивши кожну множину X з трьома і менше вершинами в X-борт β(X) таким чином:

• Якщо існує унікальний X-борт, більший від будь-якого іншого X-борта, нехай β(X) буде цим унікальним великим X-бортом.
• В іншому випадку, виберемо як β(X) довільний X-борт.

Легко безпосередньо перевірити за допомогою розбору випадків, що ця функція β задовольняє властивостям монотонності укриття. Якщо X ⊆ Y і X має менше двох вершин, або X складається з двох вершин, які не є двома сусідами кутової вершини ґратки, то існує тільки один X-борт і він містить будь-який Y-борт. В останньому випадку X складається з двох сусідів кутової вершини і має два X-борти — один складається з кутової вершини, а інший (вибирається як β(X)) складається з решти шести вершин. Незалежно від того, яку вершину додано в X для утворення Y, буде існувати Y-борт, принаймні, з чотирма вершинами, який повинен бути унікальним найбільшим бортом, оскільки він містить більше половини вершин не з Y. Цей великий Y-борт буде обрано як β(Y) і буде підмножиною β(X). Таким чином, у будь-якому випадку властивість монотонності виконується.

Переслідування-ухилення

Укриття моделюють певні класи стратегій для втікача в грі переслідування-ухилення, в якій менше ніж k переслідувачів намагаються схопити одного втікача. Положення як переслідувачів, так і втікача обмежені вершинами заданого неорієнтованого графу, а позиції і переслідувачів, і втікача відомі обом гравцям. На кожному ході гри можна додати нового переслідувача в довільну вершину графу (поки не досягнемо величини k переслідувачів) або одного зі вже наявних переслідувачів можна видалити з графу. Однак до додавання нового переслідувача утікач отримує інформацію, куди буде додано переслідувача, і може пересуватися по ребрах графу в будь-яку вільну вершину. Під час руху втікач не може проходити через вершину, зайняту одним з переслідувачів.

Якщо k-укриття (зі властивістю монотонності) існує, то втікач може уникати впіймання нескінченно довго і тим самим виграти, якщо завжди буде рухатися до вершини β(X), де X — множина вершин, зайнятих переслідувачами до кінця ходу. Властивість монотонності укриття гарантує, що при додаванні нового переслідувача у вершину графу вершини в β(X) завжди будуть доступні з поточного положення втікача.

Наприклад, утікач виграє цю гру проти трьох переслідувачів на решітці 3 × 3 за допомогою описаної стратегії, спираючись на укриття порядку 4, описане в прикладі. Проте в цій самій грі чотири переслідувачі завжди можуть спіймати втікача, розмістивши переслідувачів на три вершини, які розрізають ґрати на два шляхи з трьома вершинами в кожному. Потім розміщуємо переслідувача в центр шляху, що містить втікача, і, нарешті, видаляємо одного переслідувача, який не суміжний з кутом, і поміщаємо його на втікача. Таким чином, решітка 3 × 3 не має укриття порядку 5.

Укриття з властивістю дотикання дозволяють втікачеві виграти проти сильніших переслідувачів, які можуть одночасно стрибати з однієї позиції в іншу.

Зв'язок з деревною шириною, сепараторами і мінорами

Укриття можна використати для опису деревної ширини графу — граф має укриття порядку k тоді й лише тоді, коли він має деревну ширину принаймні k − 1. Деревну декомпозицію можна використати для опису виграшної стратегії для переслідувачів у тій самій грі переслідування-ухилення, так що істинне твердження, що граф має укриття порядку k тоді й лише тоді, коли втікач виграє за правильної гри проти менше ніж k переслідувачів. В іграх, які виграє втікач, завжди існує оптимальна стратегія у вигляді укриття, а в іграх, виграваних переслідувачами, завжди існує оптимальна стратегія у вигляді деревної декомпозиції. Наприклад, оскільки решітка 3 × 3 має укриття порядку 4, але не має укриття порядку 5, вона повинна мати деревну ширину точно рівну 3. Ту ж мінімаксну теорему можна узагальнити на нескінченні графи зі скінченною деревною шириною, якщо у визначенні деревної ширини від дерева, що лежить в основі, вимагається відсутність кінців.

Укриття також тісно пов'язані з існуванням сепараторів, малих за розміром множин вершин X у графі з n вершинами, таких, що будь-який X-борт має максимум 2n/3 вершин. Якщо граф G не має сепаратора з k вершинами, то будь-яка множина X максимум з k вершинами має (унікальний) X-борт з більш ніж 2n/3 вершинами. У цьому випадку G має укриття порядку k + 1, у якому β(X) визначається як унікальний великий X-борт. Тобто будь-який граф має або малий сепаратор, або укриття високого порядку.

Якщо граф G має укриття порядку k, при k ≥ h^3/2n^1/2 для деякого цілого h, тоді G повинен також мати мінором повний граф K_h. Іншими словами, число Хадвігера графу з n вершинами з укриттям порядку k має значення, не менше k^2/3n^−1/3. Як наслідок, вільні від K_h мінорів графи мають деревну ширину, меншу ніж h^3/2n^1/2 та сепаратори розміру, меншого ніж h^3/2n^1/2. Загальніше, межа O(√n) деревної ширини і розмір сепаратора виконується для будь-якого нетривіального сімейства графів, які можна схарактеризувати забороненими графами, оскільки для будь-якого такого сімейства існує константа h, така, що сімейство не включає K_h.

У нескінченних графах

Якщо граф G містить промінь, напівнескінченний простий шлях, що має початкову вершину, але не має кінцевої вершини, то він має укриття порядку ℵ₀, тобто функцію β, яка відображає кожну скінченну множину X вершин у X-борт, що задовольняє умовам укриттів. А саме, визначимо β(X) як унікальний X-борт, який складається з необмеженого числа вершин променя. Таким чином, у випадку нескінченних графів зв'язок між деревною шириною і укриттями ламається — окремий промінь, попри те, що він сам по собі є деревом, що має укриття всіх скінченних порядків і навіть сильніше, укриття порядку ℵ₀. Два промені нескінченного графу вважаються еквівалентними, якщо немає скінченної множини вершин, які відокремлюють нескінченно багато вершин одного променя від нескінченно великого числа вершин іншого променя. Це відношення еквівалентності і його відношення еквівалентності називаються кінцями графу.

Кінці будь-якого графу мають один-до-одного відповідність з укриттями порядку ℵ₀. Будь-який промінь визначає укриття і будь-які два еквівалентних промені визначають те ж саме укриття. З іншого боку — будь-яке укриття визначається променями таким способом, що можна показати таким аналізом варіантів:

• Якщо укриття має властивість, що перетин $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (де перетин пробігає по всій скінченній множині X) є сам по собі нескінченною множиною S, то будь-який скінченний простий шлях, який має скінченну вершину в S, можна розширити додатковою вершиною з S, і повторення процесу розширення дає промінь, що проходить через нескінченне число вершин з S. Цей промінь визначає задане укриття.
• З іншого боку, якщо S скінченний, то (працюючи з подграфом G \ S) його можна вважати порожнім. У цьому випадку для будь-якої скінченної множини X_i вершин існує множина X_i + 1 з властивістю, що X_i не має спільних елементів з $X_{i+1}\cup \beta (X_{i+1})$. Якщо грабіжник дотримується стратегії ухилення, яка визначається укриттям, а поліція дотримується стратегії, що задається цією послідовністю множин, то шлях, якого дотримується грабіжник, утворює промінь, який визначає укриття.

Таким чином, будь-який клас еквівалентності променів визначає унікальне укриття, а будь-яке укриття визначається класом еквівалентності променів.

Для будь-якого кардинального числа $\kappa \geq \aleph _{1}$, нескінченний граф G має укриття порядку $\kappa$ тоді й лише тоді, коли він має мінор кліки порядку $\kappa$. Тобто, для незліченних кардинальних чисел найбільший порядок укриття в G є числом Хадвігера графу G.

Література

• Neil Robertson, Paul Seymour, Robin Thomas. Excluding infinite minors // Discrete Mathematics. — 1991. — Т. 95, вип. 1-3 (21 квітня). — С. 303–319. — DOI:10.1016/0012-365X(91)90343-Z.
• Reinhard Diestel, Daniela Kühn. Graph-theoretical versus topological ends of graphs // Journal of Combinatorial Theory. — 2003. — Т. 87, вип. 1 (21 квітня). — С. 197–206. — DOI:10.1016/S0095-8956(02)00034-5.
• Thor Johnson, Neil Robertson, Paul Seymour, Robin Thomas. Directed Tree Width // Journal of Combinatorial Theory, Series B. — 2001. — Т. 82, вип. 1 (21 квітня). — С. 138–155. — DOI:10.1006/jctb.2000.2031.
• Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // Journal of Combinatorial Theory, Series B. — 1993. — Т. 58, вип. 1 (21 квітня). — С. 22–33. — DOI:10.1006/jctb.1993.1027.
• Noga Alon, Paul Seymour, Robin Thomas. A separator theorem for nonplanar graphs // J. Amer. Math. Soc.. — 1990. — Т. 3, вип. 4 (21 квітня). — С. 801–808. — DOI:10.1090/S0894-0347-1990-1065053-0.