Voittaja Cop Count

Poliisin voittokaavio on suuntaamaton graafi , jolla takaa-ajo-väistöpelin , jossa hän jahtaa rosvoa ja pelaajat liikkuvat vuorotellen kaavion reunoja pitkin tai seisovat paikallaan, kunnes poliisi saavuttaa kärjen. missä rosvo on [ 1] . Äärillisiä voittavia poliisigrafioita kutsutaan myös jäsennettäviksi tai konstruoiduiksi graafeiksi , koska ne voidaan jäsentää poistamalla hallitseva kärki kerta toisensa jälkeen (kärki, jonka suljettu naapuri on toisen kärjen naapuruston osajoukko) tai rakentaa lisäämällä toistuvasti tällainen kärki. Voittaneet poliisikuvaajat voidaan tunnistaa polynomiajassa ahneella algoritmilla , joka luo lajittelujärjestyksen. Tähän luokkaan kuuluvat sointukuvaajat ja graafit, jotka sisältävät universaalin huippupisteen .

Määritelmä

Välttelevä takaa-ajo

Nowakowski ja Winkler [2] esittelivät poliisin voittokaaviot (ja täydentävän graafisen luokan, ryöstön voittokaaviot) seuraavan takaa-ajo-kiertopelin yhteydessä, jonka he katsovat G. Gaborin ja A:n ansioksi. Kiyo. Kaksi pelaajaa, poliisi ja rosvo, sijaitsevat tietyn graafin eri alkupisteissä. He leikkivät vuorotellen. Vuorollaan pelaaja voi joko siirtyä viereiseen kärkipisteeseen tai pysyä paikallaan. Peli päättyy ja poliisi voittaa, jos poliisi voi päättää vuoronsa samaan kärkeen kuin rosvo. Ryöstäjä voittaa, jos hän voi väistää poliisia loputtomiin. Voittavan poliisin kaavio on kaavio, jonka ominaisuus on, että poliisi voi aina voittaa pelin mistä tahansa pelaajasta riippumatta [3] .

Purkaminen

Tietyn graafin kärjen v suljettu naapurusto N [ v ] on pistejoukko , joka koostuu pisteestä v itsestään ja kaikista muista v :n viereisistä pisteistä . Huippupisteen v sanotaan hallitsevan toinen kärki w , jos . Eli v ja w ovat vierekkäisiä, ja mikä tahansa v :n naapuri on w :n naapuri [4] . Nowakowski ja Winkler [2] kutsuvat kärkeä, jota hallitsee toinen huippupiste , redusoitumattomaksi pisteeksi [3] .

Tietyn graafin dominoitujen kärkien purkamisjärjestys tai eliminointijärjestys vastaa pisteiden järjestystä siten, että jos kärjet poistetaan yksitellen tässä järjestyksessä, jokainen kärki (paitsi viimeinen) on dominoiva. Graafi jäsennetään silloin ja vain, jos sillä on jäsennysjärjestys [3] [4] .

Sulkemisominaisuudet

Voittaneiden poliisikaavioiden perhe on suljettu graafien vahvan tuotteen alle . Poliisi voi voittaa poliisin voittokaavioiden tiukassa tulossa pelaamalla uhkapeliä yhdellä tuotteen kertoimilla ja tekemällä sitten saman toisilla kertoimilla, pysyen samalla kärjellä kuin rosvo jo voitetuissa kertoimissa [3] . Esimerkiksi kuninkaan liikegraafi , kahden polun vahva tulo , on voittavan poliisin graafi [5] .

Ei ole totta, että mielivaltaisesti generoitu voittavien poliisien graafien aligraafi on voittava. Jotkut erikoisluovutetut alakaaviot ovat kuitenkin edelleen voittajia. Nowakowski ja Winkler [2] määrittelevät graafin G supistumisen yhdeksi sen generoiduista aligraafista H kuvauksena G :n pisteistä H :n kärkipisteisiin, joka kuvaa H :n jokaisen kärjen itseensä ja kuvaa G :n jokaisen kaksi vierekkäistä kärkeä jompaankumpaan samaan kärkeen tai vierekkäisten kärkien pariin H . Sitten, kuten sanotaan, voittaneiden poliisien kaavioiden perhe on supistunut. Voittaaksesi H : ssä , voidaan simuloida peliä G . Jos poliisin G : n voittostrategia on seisoa paikallaan tai liikkua kaarta pitkin, jonka molemmat kärjet osoittavat samaan kärkeen H :ssä, poliisi seisoo paikallaan H :ssä . Kaikissa muissa tapauksissa poliisi liikkuu H :n reunaa pitkin, joka on G : n voittavan reunan kuva supistuksen alaisena [3] .

Poliisipalkkion vastaavuus ja jäsentävyys

Mikä tahansa jäsennetty kaavio on poliisille voittoisa. Poliisin voittava strategia on löytää dominoitu kärki v ja seurata (induktion avulla) optimaalista strategiaa graafissa, joka muodostetaan poistamalla v , olettaen, että rosvo on kärjessä, joka hallitsee kärkeä v . Tämä johtaa joko siihen, että poliisi tarttuu ryöstäjään tai on asennossa, jossa ryöstäjä on kärjessä v ja poliisi hallitsevassa kärjessä, josta poliisi voi voittaa tekemällä yhden ylimääräisen liikkeen [3] . Tätä strategiaa voidaan käyttää osoittamaan induktiolla, että graafissa, jossa on n kärkeä, poliisi voidaan pakottaa voittamaan enintään n − 4 siirrossa [6] [7] .

Päinvastoin, jokaisella voittavalla poliisin graafilla on hallitseva kärki. Jos rosvo pelaa optimaalisesti tarkoituksenaan vetää peli ja pelin viimeinen sijainti ennen kuin poliisi tarttuu rosvoon solmussa c ja rosvoon solmussa r , c :n on dominoitava r :tä, muuten rosvo voi pidentää peliä ainakin yksi liike. Funktio, joka kuvaa r :n c : ksi ja jättää loput kärjet paikoilleen, on supistuminen, joten hallitsevan kärjen poistamisella muodostetun graafin täytyy silti olla poliisin voittava. Induktiolla saadaan, että mikä tahansa voittava poliisikaavio voidaan jäsentää [3] . Samat argumentit osoittavat, että graafissa, jossa ei ole dominoituja kärkipisteitä, rosvo ei koskaan häviä – aina siirtyy kärkipisteeseen, joka ei ole poliisin vieressä. Mielivaltaisessa graafissa, joka ei ole voittoisa poliisille, rosvo voi voittaa poistamalla kaikki hallitsevat kärjet ja pelaamalla jäljellä olevalla aligraafilla, jonka ei saa olla tyhjä, muuten graafista tulee jäsennettävä.

Tunnistusalgoritmit ja joukko kaikkia purkutilauksia

Jos voittavan cop-graafin kärkeä dominoidaan, (kun muut hallitsevat kärjet poistetaan) se pysyy dominoivana, kunnes se itse poistetaan, tai se pysyy jäsennysjärjestyksen lopullisena kärjenä. Siksi oikeiden jäsennysjärjestysten joukolla on antimatroidin rakenne , ja jäsennysjärjestys voidaan löytää yksinkertaisella ahneella algoritmilla , joka poistaa hallitsevat kärjet askel askeleelta. Prosessi onnistuu, jos ja vain jos graafi voittaa poliisin, joten antamalla algoritmin jäsennysjärjestyksen löytämiseksi, tämä menetelmä tarjoaa algoritmin sen tarkistamiseksi, voittaako tietty graafi poliisin kannalta.

Yksi tapa löytää seuraava poistettava huippupiste on suorittaa seuraavat vaiheet:

Graafissa, jossa on n kärkeä, m reunaa ja degeneraatio d , tämä prosessi voidaan suorittaa loppuun O ( dm ) ajassa [8] .


Vaihtoehtoinen mutta monimutkaisempi Spinradin algoritmi [9] käyttää lukua, jota hän kutsuu alijäämäksi , jokaiselle vierekkäiselle pisteparille ( x , y ) ja tämä luku sisältää x :n naapurien lukumäärän, jotka eivät ole y :n naapureita . Algoritmi rakentaa ja ylläpitää alijäämäjoukkoa ( x :n naapureita, jotka eivät ole y :n naapureita ) vain, kun alijäämä on pieni. Laskelmien nopeuttamiseksi algoritmi käyttää päätöspuita , jotka luokittelevat kärjet niiden läheisyyden mukaan pienten lohkojen kanssa . Algoritmi suorittaa seuraavat vaiheet:

Tämän menettelyn suoritusaika on [10] .

Liittyvät kaavioperheet

Mikä tahansa äärellinen sointugraafi on jäsennettävä, ja mikä tahansa sointukuvaajan poissulkemisjärjestys (kärkipistejärjestys, jossa kunkin kärjen äärelliset naapurit muodostavat klikin ) on kelvollinen jäsennysjärjestys. On kuitenkin olemassa äärettömiä sointukaavioita, jotka eivät ole voittajia poliisille [11] .

Mikä tahansa graafi, jolla on universaali kärki , jäsennetään, koska kaikkia muita pisteitä hallitsee universaali kärkipiste ja mikä tahansa kärkijärjestys, joka sijoittuu universaalin kärkipisteen viimeiseksi, on oikea jäsennysjärjestys. Sitä vastoin melkein kaikilla jäsennetyillä graafeilla on universaali kärki siinä mielessä, että kaikista jäsennetyistä graafista, jossa on n kärkeä, universaalin kärjen omaavien graafien osuus pyrkii yhteen, kun taas n pyrkii äärettömyyteen [12] .

Poliisin perinnöllisesti voittavat graafit ovat kaavioita, joissa jokainen isometrinen osagraafi on poliisin voitto. Tämä ei päde kaikkiin voittaviin poliisikaavioihin. Esimerkiksi pyörä , jossa on viisi kärkeä, on voittoisa poliisille, mutta sisältää isometrisen 4-syklin, joka ei ole voittoisa, joten kuvaaja on perinnöllisesti voittava. Perinnöllisesti voittavat cop-graafit ovat samoja kuin siltagraafit, joissa millä tahansa syklillä, jonka pituus on neljä tai enemmän, on katkaisupolku, pistepari, jotka ovat lähempänä graafia kuin syklissä [13] . Poliisin voittokaavio on perinnöllinen voitto poliisille, jos ja vain, jos hänellä ei ole generoituna syklinä 4- tai 5-sykliä. Perinnöllisesti voittavan poliisigraafin kohdalla minkä tahansa leveys-ensimmäisen läpikäynnin kääntäminen on oikea lajittelujärjestys, mikä tarkoittaa, että mikä tahansa kärki voidaan valita lajittelujärjestyksen viimeiseksi kärjeksi [14] .

Samanlaista peliä, jossa on enemmän poliiseja, voidaan käyttää kaavion poliisien lukumäärän määrittämiseen, joka on pienin määrä poliisia, joka tarvitaan pelin voittamiseen. Voittajapoliisikaaviot ovat täsmälleen niitä kaavioita, joissa poliisien lukumäärä on yksi [15] .

Muistiinpanot

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski ja Winkler, 1983 , s. 235-239.
  4. ↑ 1 2 Chepoi, 1998 , s. 414–436.
  5. ↑ Siitä tosiasiasta, että tiukka polkutulo on voittava graafi, katso Nowakowskin ja Winklerin artikkeli ( Nowakowski, Winkler 1983 ). Katso siitä, että kuninkaan kreivi on tiukka tuote, katso Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , s. 5588–5595.
  7. ↑ Gavenciak, 2010 , s. 1557-1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , s. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , s. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , s. 27–41.
  12. ↑ Bonato, Kemkes, Prałat, 2012 , s. 1652-1657
  13. ↑ Anstee, Farber, 1988 , s. 22–28.
  14. ↑ Chepoi, 1997 , s. 97-100.
  15. ↑ Aigner, Fromme, 1984 , s. 1–11.

Kirjallisuus

Linkit