Поліційне число

Поліційне число неорієнтованого графа — це кількість поліціянтів, необхідних для виграшу в деякій грі переслідування-ухилення на графі.

Правила

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

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

Гра закінчується виграшем поліціянтів, якщо грабіжник опиняється на одній вершині з поліціянтом. Якщо таке ніколи не відбувається, виграє грабіжник.

Поліцейське число графа $G$ — мінімальне число $k$, таке що $k$ поліціянтів можуть виграти гру на $G$Шаблон:R.

Приклад

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

Послідовними ходами назустріч один одному два поліціянти гарантовано можуть схопити грабіжника в циклі (тут, на бейсбольному майданчику)

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

Загальні результати

Будь-який граф, обхват якого більше 4, має поліційне число, не менше від його найменшого степеняШаблон:R. Звідси випливає, що існують графи з доволі великим поліційним числом.Шаблон:Нерозв'язано1985 року Генрі Мейнель (відомий за графами Мейнеля) припустив, що будь-який граф із $n$ вершинами має поліційне число $O(\sqrt{n})$. Графи Леві скінченних проєктивних площин мають обхват 6 та мінімальний степінь $\mathrm{\Omega }(\sqrt{n})$, так що, якщо гіпотеза істинна, ця межа буде найкращою з можливихШаблон:R. Відомо, що всі графи мають сублінійне поліційне числоШаблон:R, але задачі отримання точної межі або спростування гіпотези Мейнеля залишаються нерозв'язанимиШаблон:R.

Задача обчислення поліційного числа заданого графа має клас складності EXPTIMEШаблон:R і складна в сенсі Шаблон:Не перекладеноШаблон:R.

Спеціальні класи графів

Виграшні графи поліціянта — це графи з поліційним числом 1Шаблон:R.

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

Деревну ширину графа можна отримати як результат гри псевдопереслідування, але в цій грі грабіжник може рухатися за один хід уздовж довільно довгого шляху, а не на одне ребро. Ця зайва свобода означає, що поліційне число в загальному випадку менше від деревної ширини. Конкретніше, на графах із деревною шириною $w$ поліційне число не перевищує $\lfloor w/2\rfloor +1$Шаблон:R.