WikiDer > Номер полицейского - Википедия

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

Правила

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

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

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

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

Пример

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

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

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

Общие результаты

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

Нерешенная проблема в математике: Какое наибольшее возможное количество полицейских ${ displaystyle n}$-вершинный граф? (больше нерешенных задач по математике)

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

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

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

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

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

Вычисление числа полицейских данного графа: EXPTIME-жесткий,^[5] и тяжело для параметризованная сложность.^[6]

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

В графики выигрыша - графы с числом копов, равным единице.^[1]

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

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

Рекомендации