График победы полицейского
Тип графика, связанный с преследованием-уклонением

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

Определения

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

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

Демонтаж

В этом графе вершина v доминирует над вершиной w : замкнутая окрестность v , N [ v ] (внутренняя затененная область) является подмножеством замкнутой окрестности w , N [ w ] (внешняя затененная область)

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

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

Эквивалентность cop-win и демонтируемости

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

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

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

абсгефгчас
8
h8 черный король
а1 белый король
8
77
66
55
44
33
22
11
абсгефгчас
Один из двух королей, играющий роль полицейского, может победить другого короля, играющего роль грабителя, на шахматной доске, поэтому граф короля — это граф победы полицейского.

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

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

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

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

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

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

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

В графе с n вершинами, m ребрами и вырожденностью d этот процесс может быть выполнен за время O ( dm ) . [12]

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

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

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

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

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

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

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

В этом графе u является универсальной вершиной : она смежна со всеми другими вершинами.

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

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

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

Граф колеса с пятью вершинами является выигрышным для копов, но не наследственно выигрышным для копов.

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

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

История

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

Ссылки

  1. ^ Бонато, Энтони; Новаковски, Ричард Дж. (2011), Игра в полицейских и грабителей на графах , Студенческая математическая библиотека, т. 61, Провиденс, Род-Айленд: Американское математическое общество, doi : 10.1090/stml/061, ISBN 978-0-8218-5347-4, МР  2830217
  2. ^ abcdefghi Новаковски, Ричард; Винклер, Питер (1983), «Погоня от вершины к вершине в графе», Дискретная математика , 43 ( 2–3 ): 235–239 , doi : 10.1016/0012-365X(83)90160-7 , MR  0685631
  3. ^ ab Chepoi, Victor (1998), «О порядках сохранения расстояний и устранения доминирования», SIAM Journal on Discrete Mathematics , 11 (3): 414– 436, doi :10.1137/S0895480195291230, MR  1628110
  4. ^ Бонато и Новаковски (2011), Теорема 2.3, стр. 32.
  5. ^ Бонато, А.; Головач, П.; Хан, Г.; Кратохвил, Дж. (2009), «Время захвата графа», Дискретная математика , 309 (18): 5588– 5595, doi : 10.1016/j.disc.2008.04.004 , MR  2567962
  6. ^ Гавенчяк, Томаш (2010), «Графы Cop-win с максимальным временем захвата», Дискретная математика , 310 ( 10– 11): 1557– 1563, doi : 10.1016/j.disc.2010.01.015 , MR  2601265
  7. ^ Бонато и Новаковски (2011), с. 36.
  8. ^ Бонато и Новаковски (2011), Лемма 2.1, стр. 31.
  9. ^ Бонато и Новаковски (2011), Теорема 2.2, стр. 32.
  10. ^ Бонато и Новаковски (2011), теорема 2.8, стр. 43.
  11. ^ О том, что сильное произведение путей является cop-win, см. Nowakowski & Winkler (1983). О том, что граф короля является сильным произведением путей, см. Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF) , 2005 International Conference on Analysis of Algorithms , Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, стр.  335–341 , MR  2193130
  12. ^ Лин, Мин Чи; Соулиньяк, Франциско Дж.; Шварцфитер, Джейми Л. (2012), «Древоватость, индекс Хирша и динамические алгоритмы», Теоретическая информатика , 426–427 : 75–90 , arXiv : 1005.2211 , doi :10.1016/j.tcs.2011.12.006, MR  2891574, S2CID  15827218
  13. ^ ab Spinrad, Jeremy P. (2004), «Распознавание квазитриангулированных графов», Discrete Applied Mathematics , 138 ( 1– 2): 203– 213, doi : 10.1016/S0166-218X(03)00295-6 , MR  2057611
  14. ^ Stahl, Rachel D. (сентябрь 2021 г.), «Вычислимость и игра в полицейских и грабителей на графах», Архив для Mathematical Logic , 61 ( 3– 4): 373– 397, doi :10.1007/s00153-021-00794-3, S2CID  244214571
  15. ^ Хан, Гена; Лавиолетт, Франсуа; Зауэр, Норберт; Вудроу, Роберт Э. (2002), «О графах cop-win», Дискретная математика , 258 ( 1–3 ): 27–41 , doi : 10.1016/S0012-365X(02)00260-1 , MR  2002070
  16. ^ Бонато и Новаковски (2011), Раздел 7.4, Бесконечные хордовые графы, стр. 178–182.
  17. ^ Бонато и Новаковски (2011), Раздел 7.5, Вершинно-транзитивные графы cop-win, стр. 182–187.
  18. ^ Бонато, Энтони; Кемкес, Грэм; Пралат, Павел (2012), «Почти все графы cop-win содержат универсальную вершину», Дискретная математика , 312 (10): 1652– 1657, doi : 10.1016/j.disc.2012.02.018 , MR  2901161
  19. ^ Lubiw, Anna ; Snoeyink, Jack; Vosoughpour, Hamideh (2017), «Графы видимости, демонтируемость и игра в полицейских и грабителей», Computational Geometry , 66 : 14–27 , arXiv : 1601.01298 , doi : 10.1016/j.comgeo.2017.07.001, MR  3693353
  20. ^ Anstee, RP; Farber, M. (1988), «О графах с мостами и графах cop-win», Журнал комбинаторной теории , Серия B, 44 (1): 22– 28, doi : 10.1016/0095-8956(88)90093-7 , MR  0923263
  21. ^ Chepoi, Victor (1997), «Мостовые графы — это графы cop-win: алгоритмическое доказательство», Журнал комбинаторной теории , Серия B, 69 (1): 97–100 , doi : 10.1006/jctb.1996.1726 , MR  1426753
  22. ^ ab Aigner, M.; Fromme, M. (1984), «Игра в полицейских и грабителей», Discrete Applied Mathematics , 8 (1): 1– 11, doi : 10.1016/0166-218X(84)90073-8 , MR  0739593
  23. ^ Бонато и Новаковски (2011), стр. 1–3.
  24. ^ Сеймур, Пол Д .; Томас, Робин (1993), «Поиск графа и теорема о минимуме-максимуме для ширины дерева», Журнал комбинаторной теории, Серия B , 58 (1): 22–33 , doi : 10.1006/jctb.1993.1027
  25. ^ Кийо, Ален (1978), Jeux et pointes fixes sur lesgraphes [ Игры и неподвижные точки на графиках ], These de 3ème Cycle (на французском языке), Университет Пьера и Марии Кюри , стр.  131–145по цитате Бонато и Новаковски (2011).
  26. ^ abc Бонато и Новаковски (2011), с. 4.
  • Разборные графы, Информационная система по классам графов и их включениям
Взято с "https://en.wikipedia.org/w/index.php?title=Cop-win_graph&oldid=1156485229"