Polisnummer

Polisnumret för en oriktad graf är antalet poliser som behövs för att vinna ett jakt-undvikande spel på grafen.

Regler

I det här spelet kontrollerar en spelare positionerna för ett givet antal poliser och den andra spelaren kontrollerar positionen för en rånare. Poliserna försöker fånga rånaren genom att flytta in i den position som rånaren upptar, medan rånaren försöker att inte bli gripen. Spelare gör följande åtgärder i tur och ordning [1] :

Vid det första draget placerar spelaren som kontrollerar poliserna dem på toppen av grafen (det är tillåtet att placera mer än en polis på samma vertex).
Rånarens styrenhet placerar den sedan överst på grafen.
Vid varje nästa tur väljer spelaren som kontrollerar poliserna en (möjligen tom) delmängd av dem och flyttar var och en av dem till intilliggande hörn. De återstående poliserna (om några) är kvar på plats.
Rånaren kan, när hans tur kommer, flytta till en intilliggande vertex eller förbli på plats.

Spelet slutar med att polisen vinner om rånaren är på samma hörn som polisen. Om detta aldrig händer vinner rånaren.

Grevens polisnummer är det minsta antalet så att poliser kan vinna spelet den . [ett] $G$ $k$ $k$ $G$

Exempel

På trädet är polisnumret ett. Polismannen kan börja spela från vilken hörn som helst och varje drag flyttas till den enda hörn som är närmare rånaren. Varje snuts drag minskar storleken på underträdet som är tillgängligt för inbrottstjuven, så spelet kommer säkert att ta slut.

I en cyklisk graf längre än tre är polisnumret två. Om det bara finns en polis kan rånaren flytta till en position två steg från polismannen och alltid hålla detta avstånd. Därmed kan rånaren undvika risken att bli gripen. När det gäller två poliser kan en av dem stå i samma vertex, och rånaren och den andra polisen kommer att spela på den återstående delen. Om den andra polisen följer strategin för trädet kommer rånaren definitivt att förlora.

Övergripande resultat

Varje graf vars omkrets är större än fyra har ett polisnummer som inte är mindre än dess minimigrad [2] . Detta innebär att det finns grafer med ett godtyckligt stort polisnummer.

Olösta problem i matematik : Vilket är största möjliga polisnummer för en graf med hörn?

n

Henry Meinel (känd för Meinel-grafer ) föreslog 1985 att varje graf med hörn har ett polisnummer . Levi-graferna för finita projektiva plan har omkrets 6 och minsta grad , så om gissningen är sann kommer denna gräns att vara den bästa möjliga [3] . Det är känt att alla grafer har ett sublinjärt polisnummer [4] , men problemen med att få en exakt gräns eller motbevisa Meinel-hypotesen förblir olösta [3] . $n$ $O({\sqrt {n)))$ $\Omega ({\sqrt {n)))$

Uppgiften att beräkna polisnumret för en given graf har komplexitetsklassen EXPTIME [5] och är svår i betydelsen parametriserad komplexitet [6] .

Särskilda klasser av grafer

Vinnande polisgrafer är grafer med polis nummer ett [1] .

Varje plan graf har ett polisnummer som inte överstiger tre [1] . Mer generellt har varje graf ett polisnummer som inte överstiger ett tal som är proportionellt mot dess släkte [7] . Den mest kända nedre gränsen för polisnumret när det gäller släktet är dock ungefär lika med kvadratroten av släktet, som är långt ifrån den övre gränsen när släktet är stort [2] .

Trädbredden på grafen kan också erhållas som ett resultat av ett pseudo-jaktspel, men i detta spel kan rånaren röra sig i ett drag längs en godtyckligt lång väg snarare än en kant. Denna extra frihet gör att polisnumret i allmänhet är mindre än trädbredden. Närmare bestämt, på trädbreddsgrafer , överstiger inte polisnumret [8] . $w$ $\lfloor w/2\rfloor +1$

Länkar

↑ 1 2 3 4 Aigner M. , Fromme M. Ett spel med poliser och rövare // Diskret tillämpad matematik . - 1984. - T. 8 , nr. 1 . — S. 1–11 . - doi : 10.1016/0166-218X(84)90073-8 .
↑ 1 2 Bojan Mohar. Anteckningar om Cops and Robber-spel på grafer. - 2017. - . - arXiv : 1710.11281 .
↑ 1 2 William Baird, Anthony Bonato. Meyniels gissning om polisnumret: en undersökning // Journal of Combinatorics. - 2012. - Vol. 3 , nr. 2 . — S. 225–238 . - doi : 10.4310/JOC.2012.v3.n2.a6 . - arXiv : 1308.3385 .
↑ Peter Frankl. Poliser och rånare i grafer med stor omkrets och Cayley-grafer // Discrete Applied Mathematics . - 1987. - T. 17 , nr. 3 . — S. 301–305 . - doi : 10.1016/0166-218X(87)90033-3 .
↑ William B. Kinnersley. Poliser och rånare är EXPTIME-komplett // Journal of Combinatorial Theory. - 2015. - T. 111 . — S. 201–220 . - doi : 10.1016/j.jctb.2014.11.002 . - arXiv : 1309.5405 .
↑ Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl. Om spårbarhet av poliser och rånare // Femte IFIP internationella konferens om teoretisk datavetenskap—TCS 2008. New York: Springer, 2008. Vol. 273. S. 171–185. - (IFIP Int. Fed. Inf. Process.). - doi : 10.1007/978-0-387-09680-3_12 .
↑ Bernd SW Schröder. En grafs kopplingsnummer begränsas av $\lfloor {\tfrac {3}{2}}\operatörsnamn {genus} (G)\rfloor +3$ // Kategoriska perspektiv (Kent, OH, 1998). - Boston: Birkhäuser, 2001. - S. 243-263. - (Trender Math.).
↑ Nancy Elaine Blanche Clarke. Inspärrade poliser och rånare . - Kanada: Dalhousie University, 2002. - (Ph.D.-avhandling).