Poliisin numero

Ohjaamattoman kaavion poliisinumero on poliisien lukumäärä , joka tarvitaan voittaakseen jonkin kaavion takaa-ajo-kiertopelin .

Säännöt

Tässä pelissä yksi pelaaja hallitsee tietyn määrän poliiseja ja toinen pelaaja ryöstäjän asemaa. Poliisit yrittävät saada ryöstäjän kiinni siirtymällä ryöstäjän miehittämälle paikalle, kun taas ryöstäjä yrittää olla jäämättä kiinni. Pelaajat tekevät seuraavat toiminnot vuorotellen [1] :

Ensimmäisellä siirrolla poliiseja ohjaava pelaaja asettaa ne graafin huipulle (samaan kärkeen saa sijoittaa useampi kuin yksi poliisi).
Ryöstön ohjain asettaa sen sitten kaavion yläosaan.
Jokaisella seuraavalla kierroksella poliiseja ohjaava pelaaja valitsee niistä (mahdollisesti tyhjän) osajoukon ja siirtää jokaisen niistä vierekkäisiin pisteisiin. Loput poliisit (jos sellaisia on) pysyvät paikoillaan.
Ryöstäjä voi, kun hänen vuoronsa tulee, siirtyä viereiseen kärkipisteeseen tai pysyä paikallaan.

Peli päättyy poliisien voittoon, jos rosvo on samalla kärjellä poliisin kanssa. Jos näin ei koskaan tapahdu, rosvo voittaa.

Kreivin poliisinumero on vähimmäisnumero , jolla poliisit voivat voittaa pelin . [yksi] $G$ $k$ $k$ $G$

Esimerkki

Puussa poliisinumero on yksi. Poliisi voi aloittaa pelaamisen mistä tahansa kärjestä ja jokainen liike siirtyy ainoaan pisteeseen, joka on lähempänä rosvoa. Jokainen poliisin liike pienentää murtovarkaan käytettävissä olevan alipuun kokoa, joten peli päättyy varmasti.

Kolmea pidemmässä syklisessä kaaviossa poliisiluku on kaksi. Jos poliisia on vain yksi, rosvo voi siirtyä kahden askeleen etäisyydelle poliisista ja säilyttää tämän etäisyyden aina. Siten rosvo voi välttää kiinnijäämisriskin. Kahden poliisin tapauksessa toinen heistä voi seisoa samassa kärjessä, ja rosvo ja toinen poliisi pelaavat jäljellä olevaa osaa. Jos toinen poliisi noudattaa puun strategiaa, rosvo häviää varmasti.

Kokonaistulokset

Jokaisella kuvaajalla, jonka ympärysmitta on suurempi kuin neljä, on poliisinumero, joka on vähintään sen vähimmäisaste [2] . Tämä tarkoittaa, että on kaavioita, joissa on mielivaltaisen suuri poliisiluku.

Ratkaisemattomat matematiikan ongelmat : Mikä on suurin mahdollinen poliisiluku graafille, jossa on pisteitä?

n

Henry Meinel (tunnetaan Meinel-grafeista ) ehdotti vuonna 1985, että kaikilla graafisilla pisteillä on poliisinumero . Äärillisten projektiivisten tasojen Levi-graafien ympärysmitta on 6 ja minimiaste , joten jos olettamus pitää paikkansa, tämä raja on paras mahdollinen [3] . Tiedetään, että kaikilla kaavioilla on alilineaarinen poliisinumero [4] , mutta tarkan rajan saamiseen tai Meinelin hypoteesin kumoamiseen liittyvät ongelmat jäävät ratkaisematta [3] . $n$ $O({\sqrt {n)))$ $\Omega ({\sqrt {n)))$

Tehtävä laskea tietyn graafin poliisiluku on kompleksisuusluokkaa EXPTIME [5] ja se on vaikea parametrisoidun monimutkaisuuden [6] mielessä .

Graafeiden erikoisluokat

Voittajapoliisikaaviot ovat kaavioita, joissa on poliisi numero yksi [1] .

Minkä tahansa tasograafin poliisinumero on enintään kolme [1] . Yleisesti ottaen kaikilla kaavioilla on poliisinumero, joka ei ylitä sen sukuun verrannollista lukua [7] . Kuitenkin tunnetuin poliisiluvun alaraja suvun suhteen on suunnilleen yhtä suuri kuin suvun neliöjuuri, joka on kaukana ylärajasta, kun suku on suuri [2] .

Graafin puunleveys voidaan saada myös pseudo-takaa-pelin tuloksena, mutta tässä pelissä rosvo voi liikkua yhdellä liikkeellä mielivaltaisen pitkää polkua yhden reunan sijaan. Tämä ylimääräinen vapaus tarkoittaa, että poliisinumero on yleensä pienempi kuin puun leveys. Tarkemmin sanottuna puunleveyskaavioissa poliisiluku ei ylitä [8] . $w$ $\lfloor w/2\rfloor +1$

Linkit

↑ 1 2 3 4 Aigner M. , Fromme M. Poliisi- ja rosvopeli // Discrete Applied Mathematics . - 1984. - T. 8 , no. 1 . - S. 1-11 . - doi : 10.1016/0166-218X(84)90073-8 .
↑ 1 2 Bojan Mohar. Huomautuksia poliisi- ja rosvopelistä kaavioissa. - 2017. - . - arXiv : 1710.11281 .
↑ 1 2 William Baird, Anthony Bonato. Meynielin arvelu poliisin numerosta: kysely // Journal of Combinatorics. - 2012. - Osa 3 , no. 2 . — S. 225–238 . - doi : 10.4310/JOC.2012.v3.n2.a6 . - arXiv : 1308.3385 .
↑ Peter Frankl. Poliisit ja rosvot suurilla ympärysmittauksilla ja Cayley-kaavioilla // Discrete Applied Mathematics . - 1987. - T. 17 , no. 3 . — S. 301–305 . - doi : 10.1016/0166-218X(87)90033-3 .
↑ William B. Kinnersley. Poliisit ja rosvot on EXPTIME-täydellinen // 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. Poliisi- ja rosvopelien ohjattavuus // Fifth IFIP International Conference on Theoretical Computer Science – 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 Schroeder. Graafin kopilukua rajoittavat $\lfloor {\tfrac {3}{2}}\operaattorinimi {suku} (G)\rfloor +3$ // Kategoriset perspektiivit (Kent, OH, 1998). - Boston: Birkhäuser, 2001. - S. 243-263. - (Trendit Math.).
↑ Nancy Elaine Blanche Clarke. Pakotetut poliisit ja rosvot . - Kanada: Dalhousie University, 2002. - (Ph.D. thesis).