Číslo policisty - Cop number

V teorii grafů , odvětví matematiky se počet policista nebo copnumber z undirected grafu je minimální počet policistů, že stačí, aby zajistily výhru (tj dopadení zloděje) v určitém snaha daňovým únikům hry na grafu.

Pravidla

V této hře jeden hráč ovládá pozici daného počtu policajtů a druhý hráč pozici lupiče. Policisté se pokoušejí lupiče chytit přesunem do stejné polohy, zatímco lupič se snaží zůstat nezachycen. Hráči tedy provádějí následující akce a střídají se navzájem:

• Na prvním tahu hry hráč ovládající policajty umístí každého policajta na vrchol grafu (což umožňuje umístit více než jednoho policistu na stejný vrchol).
• Poté hráč ovládající lupiče umístí lupiče na vrchol grafu.
• V každém dalším tahu si hráč ovládající policajty vybere (případně prázdnou) podmnožinu policajtů a přesune každého z těchto policajtů na sousední vrcholy. Zbývající policajti (pokud existují) zůstávají na místě.
• Na tahu lupiče se může buď přesunout na sousední vrchol, nebo zůstat na místě.

Hra končí vítězstvím policajtů, kdykoli lupič zabírá stejný vrchol jako policajt. Pokud se to nikdy nestane, lupič vyhraje.

Počet policistů v grafu je minimální počet , ve kterém mohou policajti vyhrát hru . ${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle G}$

Příklad

Na stromě je číslo policisty jedna. Policista může začít kdekoli a na každém kroku se přesunout k jedinečnému sousedovi, který je blíže lupiči. Každý z kroků policisty zmenšuje velikost podstromu, na který je lupič omezen, takže hra nakonec končí.

Postupným přiblížením k sobě mohou dva policajti nakonec chytit lupiče v jakémkoli cyklu (zde baseballový diamant)

Na cyklickém grafu o délce větší než tři je počet policistů dva. Pokud je pouze jeden policista, může se lupič přesunout do polohy vzdálené dva kroky od policisty a vždy si po každém pohybu lupiče udržovat stejnou vzdálenost. Tímto způsobem se lupič může navždy vyhnout zajetí. Pokud však existují dva policajti, jeden může zůstat na jednom vrcholu a způsobit, že lupič a druhý policista hrají na zbývající cestě. Pokud druhý policista dodržuje strategii stromu, lupič nakonec prohraje.

Obecné výsledky

Každý graf, jehož obvod je větší než čtyři, má počet policistů alespoň stejný jako jeho minimální stupeň . Z toho vyplývá, že existují grafy libovolně vysokého počtu policistů.

Henri Meyniel (také známý pro Meynielovy grafy ) předpokládal v roce 1985, že každý propojený -vrcholový graf má číslo policisty . Tyto grafy Levi (nebo výskyt grafy) z konečných projektivní rovina má obvod šest a minimální stupeň , takže pokud je to pravda to vázán by být co nejlepší. ${\ displaystyle n}$${\ displaystyle O ({\ sqrt {n}})}$${\ displaystyle \ Omega ({\ sqrt {n}})}$

Všechny grafy mají sublearní číslo policisty. Jedním ze způsobů, jak to dokázat, je použití podgrafů, které lze hlídat jediným policistou: policista se může pohybovat a sledovat lupiče takovým způsobem, že pokud se lupič někdy dostane do podgrafu, může policistu lupiče okamžitě zajmout. Dva typy podgrafu, které lze hlídat, jsou uzavřené okolí jednoho vrcholu a nejkratší cesta mezi dvěma vrcholy. Problém Moore vázaný v průměru průměru znamená, že alespoň jeden z těchto dvou druhů strážných sad má velikost . Použití jednoho policajta k ochraně této sady a opakování uvnitř připojených komponent zbývajících vrcholů grafu ukazuje, že počet policistů je nejvýše . ${\ displaystyle \ Omega (\ log n / \ log \ log n)}$${\ displaystyle O (n \ log \ log n / \ log n)}$

Silnější sublineární horní mez na počtu policistů,

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

je známo. Problémy se získáním pevné vazby a prokázáním nebo vyvrácením Meynielovy domněnky však zůstávají nevyřešeny. Dokonce není známo, zda je měkký Meynielův dohad , že existuje konstanta, pro kterou je vždy číslo policisty , pravdivý. ${\ displaystyle c <1}$${\ displaystyle O (n ^ {c})}$

Výpočet počtu polic daného grafu je EXPTIME-těžký a těžký pro parametrizovanou složitost .

Speciální třídy grafů

Tyto grafy policajt-win jsou grafy s číslem policisty roven jedné.

Každý rovinný graf má číslo policajta maximálně tři. Obecněji řečeno, každý graf má počet policajtů nanejvýš úměrný svému rodu . Nejznámější dolní mez počtu policistů z hlediska rodu je však přibližně druhá odmocnina rodu, která je daleko od horní hranice, když je rod velký.

Treewidth grafu lze také získat jako výsledek výkon-únik hry, ale ve kterém je zloděj může pohybovat podél libovolné délky drah místo jednoho okraje v každém tahu. Tato zvláštní svoboda znamená, že počet policistů je obecně menší než šířka stromu. Přesněji řečeno, na grafech šířky stromů je počet policistů nejvýše . ${\ displaystyle w}$${\ displaystyle \ lfloor w / 2 \ rfloor +1}$

Reference