Розбі́рний граф, або cop-win граф (, ; також конструйований граф, ) — у теорії графів неорієнтований граф, у якому переслідувач, званий поліцейським, завжди може виграти у грі переслідування та втечі проти втікача, званого грабіжником. Гравці по черзі переміщуються вздовж ребер графа або залишаються на місці, доки поліцейський не опиниться у тій самій вершині, що й грабіжник. Скінченні розбірні графи отримали свою назву тому, що їх можна послідовно розібрати, ітеративно вилучаючи таку доміновану вершину, чий замкнений окіл повністю міститься в околі іншої вершини; еквівалентно, такі графи можна побудувати, послідовно додаючи такі вершини. Розбірні графи розпізнаються за поліноміальний час жадібним алгоритмом, який будує порядок розбирання. До них належать хордальні графи та графи, що містять універсальну вершину.

Означення

Гра переслідування та втечі Розбірні графи визначаються через гру переслідування та втечі, у якій двоє гравців — поліцейський і грабіжник — стартують у різних початкових вершинах заданого неорієнтованого графа. Спочатку свою початкову вершину обирає поліцейський, а потім — грабіжник. Далі гравці ходять по черзі, знову ж таки починаючи з поліцейського. На своєму ході гравець може або перейти у суміжну вершину, або залишитися на місці. Гра завершується перемогою поліцейського, якщо в кінці ходу він опиняється у тій самій вершині, що й грабіжник. Грабіжник перемагає, якщо може ухилятися необмежено довго. Розбірним (або cop-win-графом) називають граф із тією властивістю, що за описаних правил вибору початкових позицій і ходів поліцейський завжди може форсувати перемогу. Якщо неорієнтований граф не є розбірним, його називають виграшним для грабіжника ().

Доміновані вершини та порядок розбирання

Замкненим околом вершини заданого графа називають множину, що складається із самої та всіх інших вершин, суміжних із . Кажуть, що вершина домінується іншою вершиною , якщо Це означає, що і суміжні й кожен інший сусід вершини є також сусідом . Новаковський і Вінклер (1983) називають вершину, що домінується іншою вершиною, незвідною.

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

Еквівалентність розбірності та виграшу поліцейського Кожен скінченний розбірний граф є cop-win. Це доводиться математичною індукцією; базою індукції є граф із однією вершиною, на якому поліцейський перемагає тривіально. Для більшого графа нехай  — будь-яка домінована вершина. За припущенням індукції поліцейський має виграшну стратегію на графі, отриманому вилученням , і може дотримуватися тієї самої стратегії на вихідному графі, удаючи, що грабіжник перебуває у вершині, яка домінує , щоразу коли той насправді стоїть у . Така стратегія призводить або до реальної перемоги в грі, або до позиції, коли грабіжник стоїть у , а поліцейський — у вершині, яка її домінує, звідки поліцейський виграє за один хід.Bonato & Nowakowski (2011), Theorem 2.3, p. 32. Поліцейський, що дотримується цієї індуктивної стратегії на графі з вершинами, виграє щонайбільше за ходів незалежно від початкової позиції. Більш ретельним вибором початкової позиції поліцейського можна показати, що у -вершинному графі поліцейський може форсувати перемогу не більш ніж за ходи.Bonato & Nowakowski (2011), p. 36.

Обернене також справедливе: кожен cop-win граф має доміновану вершину. Дійсно, у графі без домінованих вершин, якщо грабіжник ще не програв, у нього завжди знайдеться безпечний хід у позицію, не суміжну з поліцейським; повторюючи такі ходи на кожному кроці, грабіжник може продовжувати гру нескінченно довго.Bonato & Nowakowski (2011), Lemma 2.1, p. 31. Крім того, якщо  — домінована вершина в cop-win графі, то результат її вилучення також має бути cop-win графом: у протилежному випадку грабіжник міг би гратися в межах цього підграфа, удаючи, що поліцейський перебуває у вершині, яка домінує , щоразу коли той насправді стоїть у , і таким чином уникати спіймання. З цих двох принципів за індукцією випливає, що кожен скінченний cop-win граф є розбірним.Bonato & Nowakowski (2011), Theorem 2.2, p. 32. Це твердження разом із попереднім становить теорему Новаковського–Вінклера, яка повністю характеризує скінченні розбірні графи.

Властивості замикання Сім'ю математичних об'єктів називають замкненою щодо деякої множини операцій, якщо комбінування елементів сім'ї цими операціями завжди дає елемент тієї самої сім'ї.

Сильні добутки Сім'я розбірних графів замкнена щодо сильного добутку графів. Кожна вершина сильного добутку відповідає парі вершин двох множників. Поліцейський може виграти у сильному добутку двох розбірних графів так: спершу він грає на перемогу в одному з двох графів-множників, доходячи до пари, перша компонента якої збігається з першою компонентою грабіжника; потім, утримуючи рівність перших компонент, поліцейський грає на перемогу в другому множнику.Bonato & Nowakowski (2011), Theorem 2.8, p. 43. Наприклад, граф шахового короля, який є сильним добутком двох графів-шляхів, є розбірним: у цьому графі вершини відповідають клітинам шахівниці, а поліцейський і грабіжник рухаються як король у грі в шахи — на сусідню по горизонталі, вертикалі або діагоналі клітину. Виграшна стратегія поліцейського на основі добутку полягає в тому, щоб спершу опинитися в одному рядку з грабіжником, а потім рухатися у напрямку до стовпця грабіжника, на кожному кроці залишаючись із ним в одному рядку.

Ретракти Неправильно, що довільний породжений підграф розбірного графа є розбірним; проте деякі особливі породжені підграфи зберігають цю властивість. Новаковський і Вінклер означують ретракцію графа на породжений підграф як відображення множини вершин у множину вершин , що залишає кожну вершину нерухомою й переводить кожну пару суміжних у вершин або в одну й ту саму вершину , або у пару суміжних вершин . За цим означенням сім'я розбірних графів замкнена щодо ретракцій: поліцейський може виграти в , моделюючи гру в . Щоразу, коли виграшна стратегія в потребує, щоб поліцейський залишився на місці або пройшов ребром, обидва кінці якого ретракція переводить у ту саму вершину , він залишається на місці в ; в усіх інших випадках поліцейський робить хід тим ребром , яке є образом потрібного ребра під ретракцією.

Алгоритми розпізнавання Відомо кілька стратегій для перевірки того, чи є заданий граф розбірним, і знаходження послідовності розбирання, яка дозволяє поліцейському виграти. До них належать жадібні алгоритми, а також складніший алгоритм, що ґрунтується на підрахунку спільних сусідів вершин.

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

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

У графі з вершинами, ребрами та виродженістю цей процес можна здійснити за час .

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

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

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

Спінрад показує, що сумарна тривалість роботи цього алгоритму складає .

Нескінченні графи Обчислюваність алгоритмічних задач щодо розбірних графів вивчалася також для нескінченних графів. Можна побудувати обчислювані зліченні графи, на яких грабіжник, який володіє повною інформацією, може завжди уникати спіймання, але жоден алгоритм не може реалізувати цю стратегію. Такі графи можуть навіть бути нескінченними деревами зі скінченним степенем кожної вершини. За лемою Кеніга таке дерево має містити нескінченний шлях, і грабіжник із повною інформацією може виграти, рухаючись від поліцейського цим шляхом; проте жоден алгоритм не може знайти цей шлях. Натомість будь-який алгоритм для вибору ходів грабіжника може бути переможений поліцейським, який просто йде у дереві єдиним шляхом у напрямку грабіжника. Аналогічно існують обчислювані зліченні розбірні графи, на яких поліцейський із повною інформацією має виграшну стратегію, що завжди завершується за скінченну кількість ходів, проте жоден алгоритм не реалізує таку стратегію: на цих графах від будь-якого алгоритму вибору ходів поліцейського грабіжник може ухилятися як завгодно довго.

Хордальні графи Кожен скінченний хордальний граф є розбірним; більше того, будь-який порядок ідеального вилучення хордального графа (тобто такий порядок вершин, у якому пізніші сусіди кожної вершини утворюють кліку) є коректним порядком розбирання. Однак існують нескінченні хордальні графи, і навіть нескінченні хордальні графи діаметра два, які не є розбірними.Bonato & Nowakowski (2011), розд. 7.4, с. 178—182. Для інших типів графів нескінченні розбірні графи цього типу можуть існувати навіть тоді, коли скінченних немає; наприклад, це справджується для вершинно-транзитивних графів, що не є повними графами.Bonato & Nowakowski (2011), розд. 7.5, с. 182—187.

Універсальна вершина

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

Графи видимості