Полицейское число

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

Правила

В этой игре один игрок контролирует положения заданного числа полицейских, а другой игрок контролирует положение грабителя. Полицейские пытаются схватить грабителя путём передвижения в позицию, занимаемую грабителем, в то время как грабитель стремится не быть схваченным. Игроки делают следующие действия поочерёдно^[1]:

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

Игра заканчивается выигрышем полицейских, если грабитель оказывается в одной вершине с полицейским. Если такое никогда не случается, выигрывает грабитель.

Полицейское число графа $G$ — это минимальное число $k$ , такое что $k$ полицейских могут выиграть игру на $G$ .^[1]

Пример

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

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

В циклическом графе длиной более трёх полицейское число равно двум. Если имеется всего один полицейский, грабитель может перейти в позицию на два шага от полицейского и всегда сохранять это расстояние. Таким образом, грабитель может избежать риска быть схваченным. В случае же двух полицейских один из них может стоять в одной и той же вершине, а грабитель и второй полицейский будут играть на оставшейся части. Если второй полицейский следует стратегии для дерева, грабитель, безусловно, проиграет.

Общие результаты

Любой граф, обхват которого более четырёх, имеет полицейское число, не меньшее его минимальной степени^[2]. Отсюда следует, что существуют графы с произвольно большим полицейским числом.

Нерешённые проблемы математики: Каково наиболее возможное полицейское число графа с $n$ вершинами?

Генри Мейнель (известный по графам Мейнеля) предположил в 1985 году, что любой граф с $n$ вершинами имеет полицейское число $O({\sqrt {n}})$ . Графы Леви конечных проективных плоскостей имеют обхват 6 и минимальную степень $\Omega ({\sqrt {n}})$ , так что если гипотеза верна, эта граница будет лучшей из возможных^[3]. Известно, что все графы имеют сублинейное полицейское число^[4], но задачи получения точной границы или опровержения гипотезы Мейнеля, остаются нерешёнными^[3].

Задача вычисления полицейского числа заданного графа имеет класс сложности EXPTIME^[5] и трудна в смысле параметризованной сложности^[англ.]^[6].

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

Выигрышные графы полицейского — это графы с полицейским числом единица^[1].

Любой планарный граф имеет полицейское число, не превосходящее трёх^[1]. Более обще, любой граф имеет полицейское число, не превосходящее числа, пропорционального его роду^[7]. Однако лучшая известная нижняя граница для полицейского числа в терминах рода примерно равна квадратному корню от рода, что далеко от верхней границы, когда род велик^[2].

Древесная ширина графа может быть также получена как результат игры псевдопреследования, но в этой игре грабитель может двигаться за один ход вдоль произвольно длинного пути, а не на одно ребро. Эта лишняя свобода означает, что полицейское число в общем случае меньше древесной ширины. Более конкретно, на графах с древесной шириной $w$ полицейское число не превосходит $\lfloor w/2\rfloor +1$ ^[8].

Ссылки

↑ ¹ ² ³ ⁴ Aigner M., Fromme M. A game of cops and robbers // Discrete Applied Mathematics. — 1984. — Т. 8, вып. 1. — С. 1–11. — doi:10.1016/0166-218X(84)90073-8.
↑ ¹ ² Bojan Mohar. Notes on Cops and Robber game on graphs. — 2017. — Bibcode: 2017arXiv171011281M. — arXiv:1710.11281.
↑ ¹ ² William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey // Journal of Combinatorics. — 2012. — Т. 3, вып. 2. — С. 225–238. — doi:10.4310/JOC.2012.v3.n2.a6. — arXiv:1308.3385.
↑ 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.
↑ William B. Kinnersley. Cops and robbers is EXPTIME-complete // Journal of Combinatorial Theory. — 2015. — Т. 111. — С. 201–220. — doi:10.1016/j.jctb.2014.11.002. — arXiv:1309.5405.
↑ 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.
↑ Bernd S. W. Schroeder. The copnumber of a graph is bounded by $\lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3$ // Categorical perspectives (Kent, OH, 1998). — Boston: Birkhäuser, 2001. — С. 243–263. — (Trends Math.).
↑ Nancy Elaine Blanche Clarke. Constrained cops and robber. — Canada: Dalhousie University, 2002. — (Ph.D. thesis). Архивировано 28 июля 2019 года.

[af-1] ¹ ² ³ ⁴ Aigner M., Fromme M. A game of cops and robbers // Discrete Applied Mathematics. — 1984. — Т. 8, вып. 1. — С. 1–11. — doi:10.1016/0166-218X(84)90073-8.

[m-2] ¹ ² Bojan Mohar. Notes on Cops and Robber game on graphs. — 2017. — Bibcode: 2017arXiv171011281M. — arXiv:1710.11281.

[bb-3] ¹ ² William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey // Journal of Combinatorics. — 2012. — Т. 3, вып. 2. — С. 225–238. — doi:10.4310/JOC.2012.v3.n2.a6. — arXiv:1308.3385.

[f-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.

[k-5] William B. Kinnersley. Cops and robbers is EXPTIME-complete // Journal of Combinatorial Theory. — 2015. — Т. 111. — С. 201–220. — doi:10.1016/j.jctb.2014.11.002. — arXiv:1309.5405.

[fgk-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.

[s-7] Bernd S. W. Schroeder. The copnumber of a graph is bounded by $\lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3$ // Categorical perspectives (Kent, OH, 1998). — Boston: Birkhäuser, 2001. — С. 243–263. — (Trends Math.).

[c-8] Nancy Elaine Blanche Clarke. Constrained cops and robber. — Canada: Dalhousie University, 2002. — (Ph.D. thesis). Архивировано 28 июля 2019 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]