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

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

Правила

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

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

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

Поліцейське число графа ${\displaystyle G}$ — мінімальне число ${\displaystyle k}$, таке що ${\displaystyle k}$ поліціянтів можуть виграти гру на ${\displaystyle G}$[1].

Приклад

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

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

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

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

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

Нерозв'язана проблема математики: Яким є найбільше можливе поліційне число графа з n вершинами? (більше нерозв'язаних проблем математики)

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

Задача обчислення поліційного числа заданого графа має клас складності EXPTIME[5] і складна в сенсі параметризованої складності^[en][6].

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

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

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

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

Посилання

1. Aigner M.^[ru], Fromme M. A game of cops and robbers // Discrete Applied Mathematics. — 1984. — Т. 8, вип. 1. — С. 1–11. — doi:10.1016/0166-218X(84)90073-8.
2. Bojan Mohar. Notes on Cops and Robber game on graphs. — 2017. — arXiv:1710.11281. — Bibcode: 2017arXiv171011281M.
3. William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey // Journal of Combinatorics. — 2012. — Т. 3, вип. 2. — С. 225–238. — arXiv:1308.3385. — doi:10.4310/JOC.2012.v3.n2.a6.
4. Péter Frankl. Cops and robbers in graphs with large girth and Cayley graphs // Discrete Applied Mathematics. — 1987. — Т. 17, вип. 3. — С. 301–305. — doi:10.1016/0166-218X(87)90033-3.
5. William B. Kinnersley. Cops and robbers is EXPTIME-complete // Journal of Combinatorial Theory. — 2015. — Т. 111. — С. 201–220. — arXiv:1309.5405. — doi:10.1016/j.jctb.2014.11.002.
6. Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl. On tractability of cops and robbers game // Fifth IFIP International Conference on Theoretical Computer Science—TCS 2008. — New York : Springer, 2008. — Т. 273. — С. 171–185. — (IFIP Int. Fed. Inf. Process.). — doi:10.1007/978-0-387-09680-3_12.
7. Bernd S. W. Schroeder. The copnumber of a graph is bounded by ${\displaystyle \lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3}$ // Categorical perspectives (Kent, OH, 1998). — Boston : Birkhäuser, 2001. — С. 243–263. — (Trends Math.).
8. Nancy Elaine Blanche Clarke. Constrained cops and robber. — Canada : Dalhousie University, 2002. — (Ph.D. thesis).