Номер полицейского

Количество полицейских, необходимых для поимки грабителя, на графике

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

Правила

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

• На первом ходу игры игрок, управляющий копами, размещает каждого копа на вершине графа (что позволяет размещать на одной вершине более одного копа).
• Далее игрок, управляющий грабителем, помещает грабителя в вершину графа.
• На каждом последующем ходу игрок, управляющий копами, выбирает (возможно, пустое) подмножество копов и перемещает каждого из этих копов в соседние вершины. Оставшиеся копы (если таковые имеются) остаются на месте.
• В свой ход грабитель может либо переместиться на соседнюю вершину, либо остаться на месте.

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

Число копов в графе — это минимальное число , при котором копы могут выиграть игру . ^[1] ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$

Пример

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

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

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

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

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

Нерешенная задача по математике :

Каково наибольшее возможное число копий -вершинного графа? ${\displaystyle n}$

(еще нерешенные проблемы по математике)

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

Все графы имеют сублинейное число полицейских. Один из способов доказать это — использовать подграфы, которые охраняются одним полицейским: полицейский может двигаться, чтобы отслеживать грабителя таким образом, что если грабитель когда-либо войдет в подграф, полицейский сможет немедленно схватить грабителя. Два типа охраняемых подграфов — это замкнутая окрестность одной вершины и кратчайший путь между любыми двумя вершинами. Граница Мура в задаче о диаметре степени подразумевает, что по крайней мере один из этих двух видов охраняемых множеств имеет размер . Использование одного полицейского для охраны этого множества и рекурсия внутри связных компонентов оставшихся вершин графа показывает, что число полицейских не превышает . ^{[3] [4]} ${\displaystyle \Omega (\log n/\log \log n)}$ ${\displaystyle O(n\log \log n/\log n)}$

Более сильная сублинейная верхняя граница числа полицейских,

${\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}$

известно. Однако проблемы получения жесткой границы и доказательства или опровержения гипотезы Мейниэля остаются нерешенными. Неизвестно даже, верна ли мягкая гипотеза Мейниэля о том, что существует константа , для которой число cop всегда равно . ^[3] ${\displaystyle c<1}$ ${\displaystyle O(n^{c})}$

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

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

Графы «коп-победитель» — это графы с числом копов, равным единице. ^[1]

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

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

Ссылки

1. Aigner, M. ; Fromme, M. (1984), «Игра в полицейских и грабителей», Discrete Applied Mathematics , 8 (1): 1–11, doi : 10.1016/0166-218X(84)90073-8 , MR  0739593
2. Mohar, Bojan (2017), Заметки об игре Cops and Robber на графах , arXiv : 1710.11281 , Bibcode : 2017arXiv171011281M
3. Бэрд, Уильям; Бонато, Энтони (2012), «Гипотеза Мейниэля о числе полицейских: обзор», Журнал комбинаторики , 3 (2): 225–238, arXiv : 1308.3385 , doi : 10.4310/JOC.2012.v3.n2.a6, MR  2980752, S2CID  18942362
4. Франкл, Петер (1987), «Полицейские и грабители в графах с большим обхватом и графах Кэли», Дискретная прикладная математика , 17 (3): 301–305, doi :10.1016/0166-218X(87)90033-3, MR  0890640
5. Киннерсли, Уильям Б. (2015), «Полицейские и грабители — это EXPTIME-полная модель», Журнал комбинаторной теории , Серия B, 111 : 201–220, arXiv : 1309.5405 , doi : 10.1016/j.jctb.2014.11.002, MR  3315605, S2CID  15432889
6. Фомин, Федор В .; Головач, Петр А.; Кратохвил, Ян (2008), «О сговорчивости игры «полицейские и грабители»», Пятая международная конференция IFIP по теоретической информатике — TCS 2008 , IFIP Int. Fed. Inf. Process., т. 273, Нью-Йорк: Springer, стр. 171–185, doi : 10.1007/978-0-387-09680-3_12 , MR  2757374
7. Шредер, Бернд SW (2001), «Число копий графа ограничено », Категориальные перспективы (Кент, Огайо, 1998) , Trends Math., Бостон: Birkhäuser, стр. 243–263, MR  1827672 ${\displaystyle \lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3}$
8. Кларк, Нэнси Элейн Бланш (2002), Сдержанные полицейские и грабитель , докторская диссертация, Канада: Университет Далхаузи, MR  2704200, ProQuest  305503876