Номер полицейского - Википедия - Cop number

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

Правила

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

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

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

Копирование числа графа это минимальное количество такой, что копы могут выиграть игру на .[1]

Пример

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

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

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

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

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Какое наибольшее возможное количество полицейских -вершинный граф?
(больше нерешенных задач по математике)

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

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

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

известен. Однако проблемы получения жесткой привязки, а также доказательства или опровержения Гипотеза Мейниэля, остаются нерешенными. Даже неизвестно, были ли мягкая гипотеза Мейниеля, что существует постоянная для которых номер полицейского всегда , правда.[3]

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

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

В графики выигрыша - графы с числом копов, равным единице.[1]

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

В ширина дерева графа также может быть получен в результате игры преследования-уклонения, но такой, в которой грабитель может перемещаться по путям произвольной длины вместо одного ребра за каждый ход. Эта дополнительная свобода означает, что число копов обычно меньше ширины дерева. В частности, на графиках ширина дерева , количество полицейских не более .[8]

Рекомендации

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