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

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

Правила

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

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

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

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

Пример

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

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

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

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

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

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

Каково максимально возможное количество полицейских

n

-вершинный граф?

(еще нерешенные задачи по математике)

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

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

Более строго сублинейная верхняя граница числа cops:

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

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

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

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

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

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

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

Ссылки

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

[af-1] Jump up to: ^а ^б ^с ^д Айгнер, М .; Фромм, М. (1984), «Игра в полицейских и грабителей», Дискретная прикладная математика , 8 (1): 1–11, doi : 10.1016/0166-218X(84)90073-8 , MR 0739593

[m-2] Jump up to: ^а ^б Мохар, Боян (2017), Заметки об игре «Полицейские и грабители» на графиках , arXiv : 1710.11281 , Bibcode : 2017arXiv171011281M

[bb-3] Jump up to: ^а ^б ^с Бэрд, Уильям; Бонато, Энтони (2012), «Гипотеза Мейниэля о количестве полицейских: обзор», Journal of Combinatorics , 3 (2): 225–238, arXiv : 1308.3385 , doi : 10.4310/JOC.2012.v3.n2.a6 , МР 2980752 , S2CID 18942362

[f-4] Франкл, Петер (1987), «Полицейские и грабители в графах большого обхвата и графах Кэли», Discrete Applied Mathematics , 17 (3): 301–305, doi : 10.1016/0166-218X(87)90033-3 , MR 0890640

[k-5] Кинерсли, Уильям Б. (2015), «Полицейские и грабители полны по EXPTIME», Журнал комбинаторной теории , серия B, 111 : 201–220, arXiv : 1309.5405 , doi : 10.1016/j.jctb.2014.11.002 , MR 3315605 , S2CID 15432889

[fgk-6] Фомин Федор Владимирович ; Головач Петр А.; Кратохвил, Ян (2008 г.), «О сговорчивости игры полицейских и грабителей», Пятая Международная конференция ИФИП по теоретической информатике — TCS 2008 , IFIP Int. Фед. Инф. Процесс., вып. 273, Нью-Йорк: Springer, стр. 171–185, номер документа : 10.1007/978-0-387-09680-3_12 , MR 2757374.

[s-7] Шредер, Бернд С.В. (2001), «Количество копий графа ограничено $\lfloor {\tfrac {3}{2}}\operatorname {genus} (G)\rfloor +3$ ", Категориальные перспективы (Кент, Огайо, 1998) , Trends Math., Бостон: Birkhäuser, стр. 243–263, MR 1827672.

[c-8] Кларк, Нэнси Элейн Бланш (2002), Принужденные полицейские и грабители , доктор философии. диссертация, Канада: Университет Далхаузи, MR 2704200 , ПроКвест 305503876

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]