Русская Википедия:Полицейское число
Полицейское число неориентированного графа — это число полицейских, необходимых для выигрыша в некоторой игре преследования-уклонения на графе.
Правила
В этой игре один игрок контролирует положения заданного числа полицейских, а другой игрок контролирует положение грабителя. Полицейские пытаются схватить грабителя путём передвижения в позицию, занимаемую грабителем, в то время как грабитель стремится не быть схваченным. Игроки делают следующие действия поочерёдноШаблон:R:
- Первым ходом игрок, контролирующий полицейских, помещает их на вершины графа (разрешено помещать в одну вершину более одного полицейского).
- Затем игрок, контролирующий грабителя, помещает его в вершину графа.
- Каждым следующим ходом игрок, контролирующий полицейских, выбирает (возможно пустое) их подмножество и передвигает каждого из них на смежные вершины. Оставшиеся полицейские (если такие есть) остаются на месте.
- Грабитель, когда наступает его ход, может перейти на смежную вершину, или оставаться на месте.
Игра заканчивается выигрышем полицейских, если грабитель оказывается в одной вершине с полицейским. Если такое никогда не случается, выигрывает грабитель.
Полицейское число графа <math>G</math> — это минимальное число <math>k</math>, такое что <math>k</math> полицейских могут выиграть игру на <math>G</math>.Шаблон:R
Пример
На дереве полицейское число равно единице. Полицейский может начать играть с любой вершины и каждым ходом передвигается в единственную вершину, более близкую к грабителю. Каждый ход полицейского уменьшает размер поддерева, которое доступно грабителю, так что игра заведомо завершится.
В циклическом графе длиной более трёх полицейское число равно двум. Если имеется всего один полицейский, грабитель может перейти в позицию на два шага от полицейского и всегда сохранять это расстояние. Таким образом, грабитель может избежать риска быть схваченным. В случае же двух полицейских один из них может стоять в одной и той же вершине, а грабитель и второй полицейский будут играть на оставшейся части. Если второй полицейский следует стратегии для дерева, грабитель, безусловно, проиграет.
Общие результаты
Любой граф, обхват которого более четырёх, имеет полицейское число, не меньшее его минимальной степениШаблон:R. Отсюда следует, что существуют графы с произвольно большим полицейским числом.
Шаблон:Unsolved Генри Мейнель (известный по графам Мейнеля) предположил в 1985 году, что любой граф с <math>n</math> вершинами имеет полицейское число <math>O(\sqrt n)</math>. Графы Леви конечных проективных плоскостей имеют обхват 6 и минимальную степень <math>\Omega(\sqrt n)</math>, так что если гипотеза верна, эта граница будет лучшей из возможныхШаблон:R. Известно, что все графы имеют сублинейное полицейское числоШаблон:R, но задачи получения точной границы или опровержения гипотезы Мейнеля, остаются нерешённымиШаблон:R.
Задача вычисления полицейского числа заданного графа имеет класс сложности EXPTIMEШаблон:R и трудна в смысле Шаблон:Не переведено 5Шаблон:R.
Специальные классы графов
Выигрышные графы полицейского — это графы с полицейским числом единицаШаблон:R.
Любой планарный граф имеет полицейское число, не превосходящее трёхШаблон:R. Более обще, любой граф имеет полицейское число, не превосходящее числа, пропорционального его родуШаблон:R. Однако лучшая известная нижняя граница для полицейского числа в терминах рода примерно равна квадратному корню от рода, что далеко от верхней границы, когда род великШаблон:R.
Древесная ширина графа может быть также получена как результат игры псевдопреследования, но в этой игре грабитель может двигаться за один ход вдоль произвольно длинного пути, а не на одно ребро. Эта лишняя свобода означает, что полицейское число в общем случае меньше древесной ширины. Более конкретно, на графах с древесной шириной <math>w</math> полицейское число не превосходит <math>\lfloor w/2\rfloor+1</math>Шаблон:R.
Ссылки
