Выигрышный граф полицейского

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

Определение

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

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

Разборка

Замкнутая окрестность N[v] вершины v данного графа — это множество вершин, состоящих из самой вершины v и всех других вершин, смежных v. Говорят, что вершина v доминируется другой вершиной w, если N [ v ] ⊂ N [ w ] {displaystyle N[v]subset N[w]} . То есть v и w смежны и любой сосед вершины v является соседом вершины w. Новаковский и Уинклер называют вершину, которая доминируется другой вершиной неприводимой вершиной.

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

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

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

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

Эквивалентность выигрыша полицейского и разбираемость

Любой разбираемый граф является выигрышным для полицейского. Выигрышной стратегией для полицейского является нахождение доминируемой вершины v и следовать (по индукции) оптимальной стратегии на графе, образованной путём удаления v, предполагая, что грабитель находится на вершине, которая доминирует над вершиной v. Это приводит к тому, что либо полицейский хватает грабителя, или находится в положении, когда грабитель находится в вершине v, а полицейский на доминирующей вершине, из которой полицейский может выиграть, сделав один лишний ход. Эта стратегия может быть использована для доказательства по индукции факта, что в графе с n вершинами полицейский может вынужденно выиграть за макмимум n − 4 ходов.

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

Алгоритмы распознавания и семейство всех порядков разборки

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

Один из путей поиска следующей вершины для удаления — осуществить следующие шаги:

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

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

Альтернативный, но более сложный алгоритм Спинрада использует число, которое называет дефицитом, для каждой смежной пары вершин (x, y) и это число содержит количество соседей x, которые не являются соседями y. Алгоритм строит и поддерживает множество дефицита (соседей x, которые не являются соседями y), только когда дефицит мал. Для ускорения вычислений алгоритм использует деревья решений, которые классифицируют вершины согласно их смежности с малыми блоками с log 2 ⁡ n {displaystyle log _{2}n} вершинами. Алгоритм осуществляет следующие шаги:

Группируем вершины в блоки, строим дерево решений для каждого блока и классифицируем все вершины по их множествам соседей в каждом блоке.
Используем эту классификацию для вычисления дефицита для каждой пары смежных вершин за время O ( n / log ⁡ n ) {displaystyle O(n/log n)} на пару.
Повторяем следующие шаги n / log ⁡ n {displaystyle n/log n} раз, пока все вершины не будут удалены:
- Строим множество дефицита для каждой смежной пары, имеющей дефицит, не превосходящий log ⁡ n {displaystyle log n} и не построенный, уже используя начальное множество деревьев решений, за время O ( n / log ⁡ n ) {displaystyle O(n/log n)} на каждую пару.
- Повторяем следующие шаги log ⁡ n {displaystyle log n} раз:
  - Находим пару ( x , y ) {displaystyle (x,y)} с построенным пустым множеством дефекта.
  - Удаляем вершину x
  - Удаляем x из всех построенных множеств дефекта, которым она принадлежит.
- Строим дерево решений для log ⁡ n {displaystyle log n} удалённых вершин и классифицируем все вершины по их соседям в этом множестве.
- Используем дерево решений для обновления дефицита для всех рёбер за постоянное время на ребро.

Время работы этой процедуры равно O ( n 2 + m n / log ⁡ n ) {displaystyle O(n^{2}+mn/log n)} .

Связанные семейства графов

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

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

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

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