Номер полицейского - Википедия - Cop number
В теория графов, раздел математики, номер полицейского или же число из неориентированный граф минимальное количество полицейских, достаточное для обеспечения победы (т. е. поимки грабителя) в определенном преследование-уклонение игра на графике.
Правила
В этой игре один игрок управляет положением определенного количества полицейских, а другой игрок контролирует положение грабителя. Менты пытаются поймать грабителя, переместившись на ту же позицию, в то время как грабитель пытается остаться незамеченным. Таким образом, игроки по очереди выполняют следующие действия:[1]
- В первый ход игры игрок, управляющий полицейскими, помещает каждого полицейского в вершину графа (позволяя разместить более одного полицейского в одной и той же вершине).
- Затем игрок, управляющий грабителем, помещает грабителя в вершину графа.
- На каждом последующем ходу игрок, управляющий полицейскими, выбирает (возможно, пустое) подмножество полицейских и перемещает каждого из этих полицейских в соседние вершины. Остальные копы (если есть) остаются на месте.
- В свой ход грабитель может либо переместиться в соседнюю вершину, либо остаться на месте.
Игра заканчивается выигрышем для полицейских, когда грабитель занимает ту же вершину, что и полицейский. Если этого никогда не произойдет, победит грабитель.
Копирование числа графа это минимальное количество такой, что копы могут выиграть игру на .[1]
Пример
На дерево, номер полицейского - один. Коп может начинать где угодно и на каждом шагу двигаться к уникальному соседу, который ближе к грабителю. Каждый шаг копа уменьшает размер поддерева, которым ограничен грабитель, так что игра в конечном итоге заканчивается.
На график цикла длиной больше трех, число полицейских - два. Если полицейский только один, грабитель может переместиться на позицию в двух шагах от полицейского и всегда сохранять такое же расстояние после каждого движения грабителя. Таким образом, грабитель может навсегда избежать захвата. Однако, если есть два полицейских, один может остаться в одной вершине и заставить грабителя и другого полицейского играть на оставшемся пути. Если другой полицейский следует стратегии дерева, грабитель в конечном итоге проиграет.
Общие результаты
Каждый граф, чей обхват больше четырех имеет номер полицейского, по крайней мере, равный его минимальная степень.[2] Отсюда следует, что существуют графы сколь угодно большого числа копов.
Нерешенная проблема в математике: Какое наибольшее возможное количество полицейских -вершинный граф? (больше нерешенных задач по математике) |
Анри Мейниэль (также известный Графики Мейниеля ) предположил в 1985 г., что все связанные -вершинный граф имеет номер копа . В Графы Леви (или графики заболеваемости) конечные проективные плоскости иметь обхват шесть и минимальную степень , поэтому, если это правда, эта оценка была бы наилучшей из возможных.[3]
Все графики имеют сублинейное число копов. Один из способов доказать это - использовать подграфы, которые охраняет один полицейский: полицейский может двигаться, чтобы выследить грабителя, таким образом, что, если грабитель когда-либо войдет в подграф, полицейский может немедленно схватить грабителя. Два типа охраняемых подграфов: закрытый район одной вершины, а кратчайший путь между любыми двумя вершинами. В Мур связан в проблема диаметра градусов означает, что хотя бы один из этих двух типов охраняемых наборов имеет размер . Использование одного полицейского для охраны этого множества и рекурсивное обращение к компонентам связности оставшихся вершин графа показывает, что число полицейских не превышает .[3][4]
Более сильно сублинейная верхняя граница числа полицейского,
известен. Однако проблемы получения жесткой привязки, а также доказательства или опровержения Гипотеза Мейниэля, остаются нерешенными. Даже неизвестно, были ли мягкая гипотеза Мейниеля, что существует постоянная для которых номер полицейского всегда , правда.[3]
Вычисление числа полицейских данного графа: EXPTIME-жесткий,[5] и тяжело для параметризованная сложность.[6]
Специальные классы графов
В графики выигрыша - графы с числом копов, равным единице.[1]
Каждый планарный граф имеет не более трех полицейских.[1]В более общем смысле, на каждом графике число полицейских не более чем пропорционально его род.[7] Однако наиболее известная нижняя оценка числа копов с точки зрения рода - это приблизительно квадратный корень из рода, что далеко от верхней границы, когда род большой.[2]
В ширина дерева графа также может быть получен в результате игры преследования-уклонения, но такой, в которой грабитель может перемещаться по путям произвольной длины вместо одного ребра за каждый ход. Эта дополнительная свобода означает, что число копов обычно меньше ширины дерева. В частности, на графиках ширина дерева , количество полицейских не более .[8]
Рекомендации
- ^ а б c d Айгнер, М.; Фромме, М. (1984), «Игра полицейских и грабителей», Дискретная прикладная математика, 8 (1): 1–11, Дои:10.1016 / 0166-218X (84) 90073-8, МИСТЕР 0739593
- ^ а б Мохар, Боян (2017), Примечания по игре Cops and Robber на графиках, arXiv:1710.11281, Bibcode:2017arXiv171011281M
- ^ а б c Бэрд, Уильям; Бонато, Энтони (2012), "Гипотеза Мейниэля о числе полицейских: обзор", Журнал комбинаторики, 3 (2): 225–238, arXiv:1308.3385, Дои:10.4310 / JOC.2012.v3.n2.a6, МИСТЕР 2980752
- ^ Франкл, Петер (1987), «Копы и грабители в графах с большим обхватом и графах Кэли», Дискретная прикладная математика, 17 (3): 301–305, Дои:10.1016 / 0166-218X (87) 90033-3, МИСТЕР 0890640
- ^ Киннерсли, Уильям Б. (2015), «Полицейские и грабители - это EXPTIME-полная», Журнал комбинаторной теории, Серия B, 111: 201–220, arXiv:1309.5405, Дои:10.1016 / j.jctb.2014.11.002, МИСТЕР 3315605
- ^ Фомин, Федор В.; Головач, Петр А .; Кратохвил, Ян (2008), «О сговорчивости игры ментов и грабителей», Пятая Международная конференция ИФИП по теоретической информатике — TCS 2008, IFIP Int. Кормили. Инф. Процесс., 273, Нью-Йорк: Springer, стр. 171–185, Дои:10.1007/978-0-387-09680-3_12, МИСТЕР 2757374
- ^ Шредер, Бернд С. В. (2001), "Сложное число графа ограничено ", Категориальные перспективы (Кент, Огайо, 1998), Trends Math., Бостон: Birkhäuser, стр. 243–263, МИСТЕР 1827672
- ^ Кларк, Нэнси Элейн Бланш (2002), Сдержанные полицейские и грабители, Кандидат наук. дипломная работа, Канада: Университет Далхаузи, МИСТЕР 2704200, ProQuest 305503876