График выигрыша полицейских

В теории графов граф « коп -выигрыш» — это неориентированный граф , на котором преследователь (полицейский) всегда может выиграть игру преследования-уклонения против грабителя, при этом игроки делают поочередные ходы, в которых они могут выбирать движение вдоль края графа. граф или оставайтесь на месте, пока полицейский не приземлится на вершину грабителя. ^[1] Конечные графы с выигрышем от копов также называются разборными графами или конструируемыми графами , поскольку их можно разобрать путем многократного удаления доминируемой вершины (той, замкнутая окрестность которой является подмножеством окрестности другой вершины) или построить путем многократного добавления такой вершины. Графы «коп-выигрыш» могут быть распознаны за полиномиальное время с помощью жадного алгоритма , который строит порядок демонтажа. К ним относятся хордальные графы и графы, содержащие универсальную вершину .

Определения

Преследование-уклонение

Графы «коп-выигрыш» могут быть определены с помощью игры преследования-уклонения , в которой два игрока, полицейский и грабитель, расположены в разных начальных вершинах данного неориентированного графа . Сначала полицейский выбирает начальную вершину, а затем грабитель. Далее играют по очереди, опять же сначала с полицейским. В свой ход каждый игрок может либо переместиться в соседнюю вершину, либо остаться на месте. Игра заканчивается, и полицейский побеждает, если полицейский сможет завершить ход в той же вершине, что и грабитель. Грабитель побеждает, уклоняясь от полицейского на неопределенный срок. Граф победы полицейского — это граф, свойство которого состоит в том, что, когда игроки выбирают стартовые позиции и затем двигаются таким образом, полицейский всегда может добиться победы. Если неориентированный граф не является графом, в котором выигрывают полицейские, он называется графом, в котором выигрывают грабители. ^[2]

Демонтаж

Замкнутая окрестность $N [v]$ вершины $v$ в данном графе — это множество вершин, состоящее из $самой вершины v$ и всех других вершин, смежных с $v$ . вершина $v$ Говорят, что доминирует другой вершиной $w,$ когда $N [v] \subset N [w]$ . То есть $v$ и $w$ смежны, и каждый другой сосед $v$ также является соседом $w$ . ^[3] Новаковски и Винклер (1983) называют вершину, в которой доминирует другая вершина, неприводимой вершиной . ^[2]

Порядок демонтажа или порядок исключения доминирования данного графа - это такой порядок вершин, что, если вершины удаляются одна за другой в этом порядке, каждая вершина (кроме последней) доминирует в момент ее удаления. Граф является разборчивым тогда и только тогда, когда он имеет порядок разборки. ^[2]^[3]

Эквивалентность коп-вина и демонтажа

Любой конечный разборный граф является выигрышным для полицейских. Это можно доказать с помощью математической индукции , используя в качестве базового случая граф с одной вершиной (тривиально выигранный полицейским). Для большего графа пусть $v$ будет любой доминируемой вершиной. По гипотезе индукции полицейский имеет выигрышную стратегию на графе, образованном удалением $v$ , и может следовать той же стратегии на исходном графе, делая вид, что грабитель находится в вершине, которая доминирует над $v$ , когда грабитель на самом деле находится на $v$ . Следование этой стратегии приведет либо к фактической победе в игре, либо к ситуации, когда грабитель находится на $v$ , а полицейский - в доминирующей вершине, из которой полицейский может выиграть еще за один ход. ^[2]^[4] Полицейский, следующий этой индуктивной стратегии на графе с $n$ вершинами, сделает для победы не более $n$ ходов, независимо от начальной позиции. Тщательно выбирая стартовую позицию полицейского, можно использовать ту же идею, чтобы доказать, что в $графе с n$ вершинами полицейский может добиться победы не более чем за $n - 4$ хода. ^[5]^[6]^[7]

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

Свойства замыкания

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

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

Семейство математических объектов называется замкнутым относительно набора операций, если объединение членов семейства всегда дает еще одного члена этого семейства. В этом смысле семейство графов «cop-win» замкнуто относительно сильных произведений графов . Каждая вершина сильного произведения соответствует паре вершин в каждом из двух факторных графов. Полицейский может выиграть в сильном продукте двух графов выигрыша полицейского, сначала играя на победу в одном из этих двух графов факторов, достигнув пары, первый компонент которой такой же, как у грабителя. Тогда, оставаясь в парах, первый компонент которых совпадает с грабителем, полицейский может играть на победу по второму из двух факторов. ^[2]^[10] Например, граф короля , сильное произведение двух графов путей , является выигрышным. На этом графе вершины соответствуют клеткам шахматной доски, и и полицейский, и грабитель ходят, как король в игре в шахматы , на клетку, примыкающую по горизонтали, вертикали или диагонали. Стратегия, основанная на продукте, для полицейского будет заключаться в том, чтобы сначала перейти к той же строке, что и грабитель, а затем двигаться к столбцу грабителя, оставаясь на каждом этапе в той же строке, что и грабитель. ^[11]

Неправда, что каждый индуцированный подграф графа «коп-выигрыш» является «коп-выигрыш». Однако некоторые специальные индуцированные подграфы остаются выигрышными. Новаковски и Винклер (1983) определяют ретракцию графа $G$ на один из его индуцированных подграфов $H$ как отображение вершин $G$ в вершины $H$ , которое отображает каждую вершину графа $H$ в себя и отображает каждую пару соседних графов H. вершины $G$ либо в одну и ту же вершину, либо в пару смежных вершин в $H$ . Тогда семейство графов «коп-выиграл» замкнуто относительно ретракции. Это потому, что полицейский может выиграть в $H,$ игру в $G.$ смоделировав Всякий раз, когда выигрышная стратегия в $G$ требует, чтобы полицейский оставался на месте или следовал по ребру, конечные точки которого сопоставлены с одной и той же вершиной $H$ , полицейский остается на месте $H$ . А во всех остальных случаях коп следует за ребром в $H$ , который является изображением при отводе выигрышного ребра в $G$ . ^[2]

Алгоритмы распознавания

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

Жадный алгоритм

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

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

В графе с $n$ вершинами, $m$ ребрами и вырождением $d$ этот процесс можно осуществить за время $О (дм)$ . ^[12]

Подсчет соседей

Альтернативный и более сложный алгоритм Spinrad (2004) включает поддержание числа, называемого дефицитом, для каждой соседней пары вершин $(x, y)$ , которое подсчитывает количество соседей $x,$ которые не являются соседями $y$ . Если это число становится нулевым после удаления других вершин, то $x$ доминирует над $y$ и также может быть удален. Он создает и поддерживает фактический набор дефицита (соседей $x$ , которые не являются соседями $y$ ) только для пар $(x, y),$ для которых дефицит невелик. ^[13]

Чтобы ускорить вычисления, алгоритм Спинрада использует подпрограмму для подсчета соседей среди небольших блоков из $log 2 n$ вершин. Если $B$ — это набор вершин, которые алгоритм выбрал в качестве блока, то для любой другой вершины набор соседей этой вершины в $B$ можно представить как двоичное число с $log 2 n$ бит. Эти числа позволяют алгоритму подсчитать для любых двух вершин $x$ и $y$ , какой $вклад B$ вносит в дефицит $x$ и $y$ за постоянное время, с помощью комбинации побитовых операций и поиска в таблице. Используя эту подпрограмму, алгоритм выполняет следующие шаги:

Создайте блоки из произвольного раздела вершин и найдите числа, представляющие соседей каждой вершины в каждом блоке.
Используйте подпрограмму подсчета блоков, чтобы вычислить дефицит для всех соседних пар вершин.
Повторяйте следующие шаги, пока все вершины не будут удалены:
- Создайте набор дефицита для всех соседних пар, у которых дефицит не превышает $log n$ и для которых этот набор еще не был построен. Для ускорения данного строительства можно использовать исходную систему блоков.
- Повторите следующие шаги log n раз:
  - Найдите пару $(x, y)$ с построенным, но пустым дефицитным набором. Если такой пары не существует, граф не является выигрышным для полицейских; в этом случае прервите алгоритм.
  - Удалить вершину $x$
  - Удалите $x$ из всех построенных дефицитных множеств, которым он принадлежит.
- Постройте блок из $журнала n$ удаленных вершин и чисел, представляющих смежности всех остальных вершин в этом блоке.
- Используйте подпрограмму подсчета блоков в этом блоке, чтобы обновить дефициты для всех ребер.

Спинрад заявляет, что общее время для этого алгоритма равно $O (n 3 / журнал н)$ . ^[13]

В бесконечных графах

Вычислимость алгоритмических задач, включающих графы «cop-win» , также изучалась для бесконечных графов . В случае бесконечных графов можно построить вычислимые счетные бесконечные графы, на которых всеведущий грабитель всегда мог бы уклониться от любого полицейского, но для которых ни один алгоритм не может следовать этой стратегии. Эти графы могут быть даже бесконечными деревьями с конечным числом ребер на вершину. По лемме Кенига такое дерево должно иметь бесконечный путь, и всеведущий грабитель может победить, уйдя от полицейского по этому пути, но этот путь не может быть найден алгоритмом. Вместо этого любой алгоритм выбора действий грабителя может быть обыгран полицейским, который просто идет по дереву по уникальному пути к грабителю. Аналогично можно построить вычислимые счетно бесконечные графы выигрыша полицейских, на которых всеведущий полицейский имеет выигрышную стратегию, которая всегда завершается за конечное число ходов, но для которых ни один алгоритм не может следовать этой стратегии. На таких графах грабитель может бесконечно обходить любой алгоритм выбора ходов полицейского. ^[14]

Родственные семейства графов

Каждый конечный хордальный граф является разборным графом, и каждый порядок исключения хордального графа (упорядочение вершин, в котором более поздние соседи каждой вершины образуют клику ) является допустимым порядком разборки. Однако существуют бесконечные хордальные графы и даже бесконечные хордальные графы диаметра два, которые не являются выигрышными. ^[15]^[16] Для других типов графов могут существовать бесконечные выигрышные графы этого типа, даже если конечных графов нет; например, это верно для вершинно-транзитивных графов , которые не являются полными графами . ^[17]

Универсальная вершина графа — это вершина $u$ , смежная со всеми остальными вершинами.Всякий раз, когда в графе есть универсальная вершина , он подлежит демонтажу, поскольку в каждой другой вершине доминирует универсальная вершина, и любой порядок вершин, при котором универсальная вершина ставится последней, является допустимым порядком демонтажа. И наоборот, почти все разборные графы имеют универсальную вершину в том смысле, что среди всех $разборных графов с n$ -вершинами доля этих графов, имеющих универсальную вершину, стремится к единице в пределе, когда $n$ стремится к бесконечности. ^[18]

простых Графы видимости всегда многоугольников выигрышны. Это графы, определенные из вершин многоугольника, с ребром, когда две вершины могут быть соединены отрезком, не выходящим за пределы многоугольника. (В частности, вершины, смежные в многоугольнике, также являются смежными и в графе.) Даже если полицейскому и грабителю разрешено перемещаться по отрезкам прямой внутри многоугольника, а не от вершины к вершине, полицейский может выиграть, всегда двигаясь по первому шагу кратчайшего пути к грабителю.Такой ход отсекает часть многоугольника, до которой грабитель никогда не сможет добраться. Когда полицейский начинает с вершины, а грабитель ограничен в перемещении между вершинами, эта стратегия также ограничивает полицейского вершинами, поэтому это действительная выигрышная стратегия для графа видимости. ^[19]

Наследственно выигрышные графы — это графы, в которых каждый изометрический подграф (подграф $H\subseteq G$ такая, что для любых двух вершин из $H$ расстояние между ними измеряется в $G$ равно расстоянию между ними, измеренному в $H$ ) выигрывает коп. Это справедливо не для всех графов «полицейский-выигрыш»; например, граф колеса с пятью вершинами является выигрышным по принципу «коп-выигрыш», но содержит изометрический 4-цикл, который не является «выигрыш по борьбе», поэтому этот граф-колесо не является наследственно выигрышным по принципу «коп-выигрыш». Наследственно выигрышные графы аналогичны мостовым графам, графам, в которых каждый цикл длиной четыре или более имеет ярлык, пару вершин в графе ближе, чем в цикле. ^[20] Граф «коп-выигрыш» является наследственно «коп-выигрыш» тогда и только тогда, когда в нем нет ни 4-цикла, ни 5-цикла в качестве индуцированных циклов . Для наследственно выигрышного графа обращение любого обхода в ширину является допустимым порядком разборки, из которого следует, что любая вершина может быть выбрана в качестве последней вершины порядка разборки. ^[21]

Аналогичную игру с большим количеством полицейских можно использовать для определения количества полицейских в графе — наименьшего количества полицейских, необходимого для победы в игре. Графы «коп-выигрыш» — это в точности графики с числом полицейских, равным единице. ^[22] Бонато и Новаковски интуитивно описывают эту игру как количество призраков, которое понадобится, чтобы заставить игрока Pac-Man проиграть, используя данный график в качестве игрового поля. ^[23] Игру, используемую для определения количества полицейских, следует отличать от другой игры «полицейские и грабители», используемой в одном определении ширины дерева , которая позволяет полицейским перемещаться в произвольные вершины, а не требует от них перемещения по ребрам графа. ^[24]

История

Игра с одним полицейским и определенные на ее основе графики выигрышей полицейских были представлены Квиллиотом (1978) . ^[25]^[26] Еще одним ранним упоминанием является работа Новаковски и Винклера (1983) , которых с игрой познакомил Г. Габор. ^[2]^[26] Игра с несколькими полицейскими и определяемое на ее основе количество полицейских были впервые изучены Айгнером и Фроммом (1984) . ^[22]^[26]

Ссылки

^ Бонато, Энтони; Новаковски, Ричард Дж. (2011), Игра полицейских и грабителей на графиках , Студенческая математическая библиотека, том. 61, Провиденс, Род-Айленд: Американское математическое общество, номер документа : 10.1090/stml/061 , ISBN. 978-0-8218-5347-4 , МР 2830217
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Новаковски, Ричард; Винклер, Питер (1983), «Преследование от вершины к вершине в графе», Discrete Mathematics , 43 (2–3): 235–239, doi : 10.1016/0012-365X(83)90160-7 , MR 0685631
^ Перейти обратно: ^а ^б Чепой, Виктор (1998), «О порядках сохранения расстояния и устранения доминирования», SIAM Journal on Discrete Mathematics , 11 (3): 414–436, doi : 10.1137/S0895480195291230 , MR 1628110
^ Бонато и Новаковски (2011) , Теорема 2.3, стр. 32.
^ Бонато, А.; Головач П.; Хан, Г.; Краточвил, Дж. (2009), «Время захвата графика», Discrete Mathematics , 309 (18): 5588–5595, doi : 10.1016/j.disc.2008.04.004 , MR 2567962
^ Гавенчак, Томаш (2010), «Графы победы полицейских с максимальным временем захвата», Discrete Mathematics , 310 (10–11): 1557–1563, doi : 10.1016/j.disc.2010.01.015 , MR 2601265
^ Бонато и Новаковски (2011) , стр. 36.
^ Бонато и Новаковски (2011) , Лемма 2.1, стр. 31.
^ Бонато и Новаковски (2011) , Теорема 2.2, стр. 32.
^ Бонато и Новаковски (2011) , Теорема 2.8, стр. 43.
^ О том, что сильный продукт путей является выигрышным для полицейских, см. Nowakowski & Winkler (1983) . О том, что королевский граф является сильным произведением путей, см. Беренд, Дэниел; Корах, Ефрем; Цукер, Шира (2005), «Две антираскраски плоских и связанных с ними графов» (PDF) , Международная конференция 2005 г. по анализу алгоритмов , дискретной математике и теоретической информатике, Нэнси: Ассоциация дискретной математики и теоретической информатики, стр. 335–341, МР 2193130
^ Лин, Мин Чи; Сулиньяк, Франсиско Дж.; Шварцфитер, Джейм Л. (2012), «Древовидность, $индекс Хирша$ и динамические алгоритмы», Theoretical Computer Science , 426–427: 75–90, arXiv : 1005.2211 , doi : 10.1016/j.tcs.2011.12.006 , MR 2891574 , S2CID 15827218
^ Перейти обратно: ^а ^б Спинрад, Джереми П. (2004), «Распознавание квазитриангулированных графов», Discrete Applied Mathematics , 138 (1–2): 203–213, doi : 10.1016/S0166-218X(03)00295-6 , MR 2057611
^ Шталь, Рэйчел Д. (сентябрь 2021 г.), «Вычислимость и игра полицейских и грабителей на графах», Архив математической логики , 61 (3–4): 373–397, doi : 10.1007/s00153-021-00794-3 , S2CID 244214571
^ Хан, Геня; Лавиолетт, Франсуа; Зауэр, Норберт; Вудро, Роберт Э. (2002), «О графах победы полицейских», Discrete Mathematics , 258 (1–3): 27–41, doi : 10.1016/S0012-365X(02)00260-1 , MR 2002070
^ Бонато и Новаковски (2011) , Раздел 7.4, Бесконечные хордальные графы, стр. 178–182.
^ Бонато и Новаковски (2011) , Раздел 7.5, Вершинно-транзитивные графы выигрыша полицейских, стр. 182–187.
^ Бонато, Энтони; Кемкес, Грэм; Пралат, Павел (2012), «Почти все графы, обеспечивающие выигрыш полицейских, содержат универсальную вершину», Discrete Mathematics , 312 (10): 1652–1657, doi : 10.1016/j.disc.2012.02.018 , MR 2901161
^ Любив, Анна ; Снойинк, Джек; Восугпур, Хамиде (2017), «Графики видимости, разборка и игра в полицейских и грабителей», Computational Geometry , 66 : 14–27, arXiv : 1601.01298 , doi : 10.1016/j.comgeo.2017.07.001 , MR 3693353
^ Ансти, РП; Фарбер, М. (1988), «О мостовых графах и графах выигрыша полицейских», Журнал комбинаторной теории , серия B, 44 (1): 22–28, doi : 10.1016/0095-8956(88)90093-7 , МР 0923263
^ Чепой, Виктор (1997), «Мостовые графы - это графы, в которых выигрывают полицейские: алгоритмическое доказательство», Журнал комбинаторной теории , серия B, 69 (1): 97–100, doi : 10.1006/jctb.1996.1726 , MR 1426753
^ Перейти обратно: ^а ^б Айгнер, М.; Фромм, М. (1984), «Игра в полицейских и грабителей», Дискретная прикладная математика , 8 (1): 1–11, doi : 10.1016/0166-218X(84)90073-8 , MR 0739593
^ Бонато и Новаковски (2011) , стр. 1–3.
^ Сеймур, Пол Д .; Томас, Робин (1993), «Поиск по графу и теорема о мин-максе для ширины дерева», Журнал комбинаторной теории, серия B , 58 (1): 22–33, doi : 10.1006/jctb.1993.1027
^ Кийо, Ален (1978), Игры и неподвижные точки на графиках диссертация 3-го , цикла (на французском языке), Университет Пьера и Марии Кюри , стр. 131–145 , по цитате Бонато и Новаковски (2011).
^ Перейти обратно: ^а ^б ^с Бонато и Новаковски (2011) , стр. 4.

Внешние ссылки

Разбираемые графы , Информационная система по классам графов и их включениям

[bn-1] Бонато, Энтони; Новаковски, Ричард Дж. (2011), Игра полицейских и грабителей на графиках , Студенческая математическая библиотека, том. 61, Провиденс, Род-Айленд: Американское математическое общество, номер документа : 10.1090/stml/061 , ISBN. 978-0-8218-5347-4 , МР 2830217

[nw-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Новаковски, Ричард; Винклер, Питер (1983), «Преследование от вершины к вершине в графе», Discrete Mathematics , 43 (2–3): 235–239, doi : 10.1016/0012-365X(83)90160-7 , MR 0685631

[c-3] Перейти обратно: ^а ^б Чепой, Виктор (1998), «О порядках сохранения расстояния и устранения доминирования», SIAM Journal on Discrete Mathematics , 11 (3): 414–436, doi : 10.1137/S0895480195291230 , MR 1628110

[FOOTNOTEBonatoNowakowski2011Theorem_2.3,_page_32-4] Бонато и Новаковски (2011) , Теорема 2.3, стр. 32.

[bgh-5] Бонато, А.; Головач П.; Хан, Г.; Краточвил, Дж. (2009), «Время захвата графика», Discrete Mathematics , 309 (18): 5588–5595, doi : 10.1016/j.disc.2008.04.004 , MR 2567962

[g-6] Гавенчак, Томаш (2010), «Графы победы полицейских с максимальным временем захвата», Discrete Mathematics , 310 (10–11): 1557–1563, doi : 10.1016/j.disc.2010.01.015 , MR 2601265

[FOOTNOTEBonatoNowakowski201136-7] Бонато и Новаковски (2011) , стр. 36.

[FOOTNOTEBonatoNowakowski2011Lemma_2.1,_page_31-8] Бонато и Новаковски (2011) , Лемма 2.1, стр. 31.

[FOOTNOTEBonatoNowakowski2011Theorem_2.2,_page_32-9] Бонато и Новаковски (2011) , Теорема 2.2, стр. 32.

[FOOTNOTEBonatoNowakowski2011Theorem_2.8,_page_43-10] Бонато и Новаковски (2011) , Теорема 2.8, стр. 43.

[bkz-11] О том, что сильный продукт путей является выигрышным для полицейских, см. Nowakowski & Winkler (1983) . О том, что королевский граф является сильным произведением путей, см. Беренд, Дэниел; Корах, Ефрем; Цукер, Шира (2005), «Две антираскраски плоских и связанных с ними графов» (PDF) , Международная конференция 2005 г. по анализу алгоритмов , дискретной математике и теоретической информатике, Нэнси: Ассоциация дискретной математики и теоретической информатики, стр. 335–341, МР 2193130

[lss-12] Лин, Мин Чи; Сулиньяк, Франсиско Дж.; Шварцфитер, Джейм Л. (2012), «Древовидность, $индекс Хирша$ и динамические алгоритмы», Theoretical Computer Science , 426–427: 75–90, arXiv : 1005.2211 , doi : 10.1016/j.tcs.2011.12.006 , MR 2891574 , S2CID 15827218

[s-13] Перейти обратно: ^а ^б Спинрад, Джереми П. (2004), «Распознавание квазитриангулированных графов», Discrete Applied Mathematics , 138 (1–2): 203–213, doi : 10.1016/S0166-218X(03)00295-6 , MR 2057611

[stahl-14] Шталь, Рэйчел Д. (сентябрь 2021 г.), «Вычислимость и игра полицейских и грабителей на графах», Архив математической логики , 61 (3–4): 373–397, doi : 10.1007/s00153-021-00794-3 , S2CID 244214571

[hlsw-15] Хан, Геня; Лавиолетт, Франсуа; Зауэр, Норберт; Вудро, Роберт Э. (2002), «О графах победы полицейских», Discrete Mathematics , 258 (1–3): 27–41, doi : 10.1016/S0012-365X(02)00260-1 , MR 2002070

[FOOTNOTEBonatoNowakowski2011Section_7.4,_Infinite_chordal_graphs,_pp._178–182-16] Бонато и Новаковски (2011) , Раздел 7.4, Бесконечные хордальные графы, стр. 178–182.

[FOOTNOTEBonatoNowakowski2011Section_7.5,_Vertex-transitive_cop-win_graphs,_pp._182–187-17] Бонато и Новаковски (2011) , Раздел 7.5, Вершинно-транзитивные графы выигрыша полицейских, стр. 182–187.

[bkp-18] Бонато, Энтони; Кемкес, Грэм; Пралат, Павел (2012), «Почти все графы, обеспечивающие выигрыш полицейских, содержат универсальную вершину», Discrete Mathematics , 312 (10): 1652–1657, doi : 10.1016/j.disc.2012.02.018 , MR 2901161

[lsv-19] Любив, Анна ; Снойинк, Джек; Восугпур, Хамиде (2017), «Графики видимости, разборка и игра в полицейских и грабителей», Computational Geometry , 66 : 14–27, arXiv : 1601.01298 , doi : 10.1016/j.comgeo.2017.07.001 , MR 3693353

[af2-20] Ансти, РП; Фарбер, М. (1988), «О мостовых графах и графах выигрыша полицейских», Журнал комбинаторной теории , серия B, 44 (1): 22–28, doi : 10.1016/0095-8956(88)90093-7 , МР 0923263

[c2-21] Чепой, Виктор (1997), «Мостовые графы - это графы, в которых выигрывают полицейские: алгоритмическое доказательство», Журнал комбинаторной теории , серия B, 69 (1): 97–100, doi : 10.1006/jctb.1996.1726 , MR 1426753

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

[FOOTNOTEBonatoNowakowski20111–3-23] Бонато и Новаковски (2011) , стр. 1–3.

[st-24] Сеймур, Пол Д .; Томас, Робин (1993), «Поиск по графу и теорема о мин-максе для ширины дерева», Журнал комбинаторной теории, серия B , 58 (1): 22–33, doi : 10.1006/jctb.1993.1027

[q-25] Кийо, Ален (1978), Игры и неподвижные точки на графиках диссертация 3-го , цикла (на французском языке), Университет Пьера и Марии Кюри , стр. 131–145 , по цитате Бонато и Новаковски (2011).

[FOOTNOTEBonatoNowakowski20114-26] Перейти обратно: ^а ^б ^с Бонато и Новаковски (2011) , стр. 4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]