Поліційне число неорієнтованого графа — це кількість поліціянтів, необхідних для виграшу в деякій грі переслідування-ухилення на графі.
Правила У цій грі один гравець керує положенням заданої кількості поліціянтів, а інший гравець керує положенням грабіжника. Поліціянти намагаються схопити грабіжника, пересуваючись у позицію, яку займає грабіжник, тоді як грабіжник прагне не бути схопленим. Гравці почергово роблять такі дії:
Першим ходом гравець, який керує поліціянтами, поміщає їх на вершини графа (дозволено поміщати в одну вершину більше одного поліціянта). Потім гравець, який керує грабіжником, поміщає його у вершину графа. Кожним наступним ходом гравець, який керує поліціянтами, вибирає (можливо порожню) їх підмножину і пересуває кожного з них на суміжні вершини. Решта поліціянтів (якщо такі є) залишаються на місці. Грабіжник, коли настає його хід, може перейти на суміжну вершину або залишитися на місці.
Гра закінчується виграшем поліціянтів, якщо грабіжник опиняється на одній вершині з поліціянтом. Якщо таке ніколи не відбувається, виграє грабіжник.
Поліцейське число графа — мінімальне число , таке що поліціянтів можуть виграти гру на .
Приклад На дереві поліційне число дорівнює одиниці. Поліціянт може почати грати з будь-якої вершини і кожним ходом пересувтися в єдину вершину, ближчу до грабіжника. Кожен хід поліціянта зменшує розмір піддерева, доступного грабіжнику, тому гра обов'язково завершиться.
У циклічному графі довжиною більше трьох поліційне число дорівнює двом. Якщо є один поліціянт, грабіжник може перейти в позицію за два кроки від поліціянта і завжди зберігати цю відстань. Таким чином, грабіжник уникне ризику бути схопленим. У випадку двох поліціянтів один з них може стояти в одній і тій самій вершині, а грабіжник і другий поліціянт гратимуть на частині, що залишилася. Якщо другий поліціянт дотримується стратегії для дерева, грабіжник, безумовно, програє.
Загальні результати Будь-який граф, обхват якого більше 4, має поліційне число, не менше від його найменшого степеня. Звідси випливає, що існують графи з доволі великим поліційним числом.1985 року Генрі Мейнель (відомий за графами Мейнеля) припустив, що будь-який граф із вершинами має поліційне число . Графи Леві скінченних проєктивних площин мають обхват 6 та мінімальний степінь , так що, якщо гіпотеза істинна, ця межа буде найкращою з можливих. Відомо, що всі графи мають сублінійне поліційне число, але задачі отримання точної межі або спростування гіпотези Мейнеля залишаються нерозв'язаними.
Задача обчислення поліційного числа заданого графа має клас складності EXPTIME і складна в сенсі .
Спеціальні класи графів Виграшні графи поліціянта — це графи з поліційним числом 1.
Поліційне число будь-якого планарного графа не перевищує 3. Загальніше, будь-який граф має поліційне число, що не перевищує числа, пропорційного його роду. Однак найкраща відома нижня межа для поліційного числа в термінах роду приблизно дорівнює квадратному кореню з роду, що далеко від верхньої межі, коли рід великий.
Деревну ширину графа можна отримати як результат гри псевдопереслідування, але в цій грі грабіжник може рухатися за один хід уздовж довільно довгого шляху, а не на одне ребро. Ця зайва свобода означає, що поліційне число в загальному випадку менше від деревної ширини. Конкретніше, на графах із деревною шириною поліційне число не перевищує .
Посилання