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

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

Визначення

Якщо 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-борт.

Легко безпосередньо перевірити за допомогою ^[en], що ця функція β задовольняє властивостям монотонності укриття. Якщо 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-борт, який складається з необмеженого числа вершин променя. Таким чином, у випадку нескінченних графів зв'язок між деревною шириною і укриттями ламається — окремий промінь, попри те, що він сам по собі є деревом, що має укриття всіх скінченних порядків і навіть сильніше, укриття порядку ℵ₀. Два промені нескінченного графу вважаються еквівалентними, якщо немає скінченної множини вершин, які відокремлюють нескінченно багато вершин одного променя від нескінченно великого числа вершин іншого променя. Це відношення еквівалентності і його відношення еквівалентності називаються кінцями графу.

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

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

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

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

Примітки

1. Seymour, Thomas, 1993.
2. Seymour, Thomas, 1993, с. 22–33.
3. Alon, Seymour, Thomas, 1990, с. 801–808.
4. Robertson, Seymour, Thomas, 1991, с. 303–319.
5. Diestel, Kühn, 2003, с. 197–206.
6. Johnson, Robertson, Seymour, Thomas, 2001, с. 138–155.

Література

• Neil Robertson, Paul Seymour, Robin Thomas. Excluding infinite minors // . — 1991. — Т. 95, вип. 1-3 (16 червня). — С. 303–319. — DOI:10.1016/0012-365X(91)90343-Z.
• Reinhard Diestel, Daniela Kühn. Graph-theoretical versus topological ends of graphs // . — 2003. — Т. 87, вип. 1 (16 червня). — С. 197–206. — DOI:10.1016/S0095-8956(02)00034-5.
• Thor Johnson, Neil Robertson, Paul Seymour, Robin Thomas. Directed Tree Width // . — 2001. — Т. 82, вип. 1 (16 червня). — С. 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 (16 червня). — С. 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 (16 червня). — С. 801–808. — DOI:10.1090/S0894-0347-1990-1065053-0.