Номер полицейского

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

Правила [ править ]

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

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

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

Число полицейских на графике - это минимальное число , при котором полицейские могут выиграть игру . ^[1]${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle G}$

Пример [ править ]

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

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

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

Общие результаты [ править ]

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

Анри Мейниэль (также известный по графам Мейниеля ) в 1985 г. предположил, что у каждого связного графа вершин есть число копов . На графиках Леви (или падение графика) из конечных проективных плоскостей имеют обхвата шесть и минимальную степень , так что если это верно неизбежно будет наилучшими. ^[3]${\ displaystyle n}$${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle \ Omega ({\ sqrt {n}})}$

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

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

${\ displaystyle {\ frac {n} {2 ^ {(1-o (1)) {\ sqrt {\ log n}}}}},}$

известен. Однако проблемы получения точной границы и доказательства или опровержения гипотезы Мейниэля остаются нерешенными. Неизвестно даже, верна ли мягкая гипотеза Мейниеля о том , что существует константа, для которой всегда есть число полицейских . ^[3]${\ displaystyle c <1}$${\ Displaystyle О (п ^ {с})}$

Вычисление КС количества данного графа EXPTIME-трудно , ^[5] и трудно для параметризованного сложности . ^[6]

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

На графиках початков победы являются графы с числом полицейского равной единицы. ^[1]

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

Древесная ширина графы может быть также получена в результате погона-уклонение игры, но тот , в котором грабитель может перемещаться вдоль произвольной длиной путей вместо одного ребра в каждом повороте. Эта дополнительная свобода означает, что число копов обычно меньше ширины дерева. В частности, на графиках ширины деревьев число копов не превышает . ^[8]${\ displaystyle w}$${\ displaystyle \ lfloor w / 2 \ rfloor +1}$

Ссылки [ править ]