Vinnande Cop Count

Snutens vinnande graf är en oriktad graf på vilken förföljaren (snuten) kan vinna jaktflyktsspelet där han jagar rånaren och spelarna turas om att röra sig längs kanterna på grafen eller stå stilla tills snuten tar spetsen där rånaren är [1] . Polismannens slutliga vinnande grafer kallas också parserbara grafer eller konstruerade grafer , eftersom de kan analyseras genom att ta bort den dominerade vertexen om och om igen (hörn, slutet områdesom är en delmängd av grannskapet till en annan vertex) eller konstrueras genom att upprepade gånger lägga till en sådan vertex. Vinnande polisgrafer kan kännas igen i polynomtid av en girig algoritm som genererar en sorteringsordning. Denna klass innehåller ackordsgrafer och grafer som innehåller en universell vertex .

Definition

Undvikande jakt

Polismannens vinnande grafer (och den kompletterande klassen av grafer, rånarens vinnande grafer) introducerades av Nowakowski och Winkler [2] i samband med följande jakt-undvikande spel, som de tillskriver G. Gabor och A Kiyo. Två spelare, en polis och en rånare, befinner sig vid olika initiala hörn av en given graf. De turas om att spela. Under sin tur kan spelaren antingen flytta till en intilliggande vertex eller stanna på plats. Spelet slutar och snuten vinner om snuten kan avsluta sin tur vid samma hörn som rånaren. Rånaren vinner om han kan undvika snuten på obestämd tid. En vinnande polisgraf är en graf med egenskapen att oavsett var de två spelarna börjar spelet kan snuten alltid vinna [3] .

Demontering

En sluten grannskap N [ v ] av en vertex v i en given graf är uppsättningen av hörn som består av själva vertex v och alla andra hörn som gränsar till v . En vertex v sägs domineras av en annan vertex w if . Det vill säga v och w är intilliggande, och vilken granne som helst till v är en granne till w [4] . Nowakowski och Winkler [2] kallar en vertex som domineras av en annan vertex för en irreducibel vertex [3] .

Ordningen för demontering eller ordningen för eliminering av dominerade hörn i en given graf motsvarar en ordning av hörn så att om hörn tas bort en efter en i den ordningen, domineras varje hörn (utom den sista). Grafen analyseras om och endast om den har en analysordning [3] [4] .

Stängningsegenskaper

Familjen med vinnande polisgrafer är sluten under den starka produkten av grafer . Snuten kan vinna i den strikta produkten av polisens vinnande grafer genom att spela på en av produktens multiplikatorer och sedan göra samma sak på de andra multiplikatorerna, stanna på samma vertex som rånaren i multiplikatorerna som redan vunnit [3] . Till exempel är kungens rörelsegraf , den starka produkten av två banor , en vinnande polisgraf [5] .

Det är inte sant att en godtyckligt genererad subgraf av vinnande polisgrafer vinner. Vissa specialgenererade subgrafer fortsätter dock att vinna. Nowakowski och Winkler [2] definierar sammandragningen av en graf G till en av dess genererade subgrafer H som en avbildning från hörn av G till hörn av H som mappar varje hörn av H till sig själv, och mappar varannan angränsande hörn av G till antingen samma vertex eller till ett par angränsande hörn i H . Sedan, som de säger, familjen av vinnande polisman grafer är sammandragning stängd. För att vinna på H kan man simulera ett spel på G. Om den vinnande strategin i G för polismannen är att stå still eller röra sig längs en båge vars båda hörn mappar till samma vertex i H , står polismannen stilla i H . I alla andra fall rör sig polismannen längs kanten i H , vilket är bilden av den vinnande kanten i G under kontraktion [3] .

Cop payoff ekvivalens och parsability

Alla analyserade grafer är vinnande för polisen. Den vinnande strategin för polismannen är att hitta en dominerad vertex v och följa (genom induktion) den optimala strategin på grafen som bildas genom att radera v , förutsatt att rånaren befinner sig på en vertex som dominerar vertex v . Detta resulterar i att antingen polismannen tar tag i rånaren, eller befinner sig i en position där rånaren är vid vertex v och snuten är vid den dominerande vertexen, från vilken snuten kan vinna genom att göra ett extra drag [3] . Denna strategi kan användas för att bevisa genom induktion att i en graf med n hörn kan en polisman tvingas vinna i högst n − 4 drag [6] [7] .

Omvänt har varje vinnande polisgraf en dominerad vertex. Om rånaren spelar optimalt med syfte att dra ut spelet och den sista positionen i spelet innan polismannen tar tag i rånaren vid nod c och rånaren vid nod r , så måste c dominera r , annars kan rånaren förlänga spelet med minst ett drag. En funktion som mappar r till c och lämnar resten av hörnen på plats är en sammandragning, så grafen som bildas genom att ta bort en dominerad vertex måste fortfarande vinna för polismannen. Genom induktion får vi att vilken vinnande polisgraf som helst kan analyseras [3] . Samma argument visar att i en graf utan dominerade hörn förlorar rånaren aldrig – det sker alltid en flytt till en vertex som inte ligger i anslutning till polisen. I en godtycklig graf som inte vinner för polisen, kan rånaren vinna genom att ta bort alla dominerade hörn och spela på den återstående subgrafen, som måste vara tom, annars kommer grafen att kunna analyseras.

Igenkänningsalgoritmer och en familj av alla demonteringsorder

Om en vertex i en vinnande polisgraf domineras, förblir den (när andra dominerade hörn tas bort) dominerad tills den själv tas bort, eller förblir den sista hörn i analysordningen. Därför har uppsättningen av korrekta analysorder strukturen av en antimatroid , och analysordningen kan hittas av en enkel girig algoritm som tar bort dominerade hörn steg för steg. Processen lyckas om och endast om grafen vinner för polismannen, så att ge en algoritm för att hitta ordningsföljden för analys, tillhandahåller denna metod en algoritm för att kontrollera om en given graf vinner för polismannen.

Ett sätt att hitta nästa vertex att ta bort är att ta följande steg:

I en graf med n hörn, m kanter och degeneration d , kan denna process slutföras på O ( dm ) tid [8] .


En alternativ men mer komplicerad algoritm av Spinrad [9] använder ett tal, som han kallar deficit , för varje angränsande par av hörn ( x , y ) och detta tal innehåller antalet grannar till x som inte är grannar till y . Algoritmen bygger och underhåller en underskottsmängd (grannar till x som inte är grannar till y ) endast när underskottet är litet. För att påskynda beräkningarna använder algoritmen beslutsträd som klassificerar hörn efter deras närhet till små block med hörn. Algoritmen utför följande steg:

Körtiden för denna procedur är [10] .

Besläktade familjer av grafer

Alla ändliga kordalgrafer är parserbara, och alla exkluderingsordningar för kordagrafer (vertexordning där varje vertexs finita grannar bildar en klick ) är en giltig analysordning. Det finns dock oändliga ackordsgrafer som inte vinner för polisen [11] .

Varje graf som har en universell vertex tolkas eftersom alla andra hörn domineras av den universella vertexen och all vertexordning som placerar den universella vertexen sist är den korrekta analysordningen. Omvänt har nästan alla analyserade grafer ett universellt hörn i den meningen att bland alla tolkade grafer med n hörn tenderar andelen grafer med en universal vertex till ett eftersom n tenderar mot oändligheten [12] .

Polismannens ärftligt vinnande grafer är grafer där varje isometrisk subgraf vinner för polismannen. Detta är inte sant för alla vinnande polisgrafer. Till exempel, ett hjul med fem hörn vinner för polisen, men innehåller en isometrisk 4-cykel som inte vinner, så grafen vinner ärftligt. Ärftligt vinnande polisgrafer är samma som brografer, där varje cykel av längd fyra eller mer har en avskärningsbana, ett par hörn som är närmare i grafen än i cykeln [13] . En polismans vinnande graf är en ärftlig vinst för en polis om och endast om han varken har en 4-cykel eller en 5-cykel som en genererad cykel. För en ärftligt vinnande polisgraf är omkastningen av en bredd-först-traversering en korrekt sorteringsordning, vilket innebär att vilken vertex som helst kan väljas som den sista hörn i sorteringsordningen [14] .

Ett liknande spel med fler poliser kan användas för att bestämma antalet poliser i grafen, det minsta antalet poliser som behövs för att vinna spelet. De vinnande polisgraferna är exakt de grafer för vilka antalet poliser är lika med en [15] .

Anteckningar

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski och Winkler, 1983 , sid. 235–239.
  4. ↑ 1 2 Chepoi, 1998 , sid. 414–436.
  5. ↑ Om det faktum att en strikt vägprodukt är en vinnande graf, se artikeln av Nowakowski och Winkler ( Nowakowski, Winkler 1983 ). För det faktum att kungens greve är en strikt produkt, se Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , sid. 5588–5595.
  7. ↑ Gavenciak, 2010 , sid. 1557–1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , sid. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , sid. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , sid. 27–41.
  12. ↑ Bonato, Kemkes, Prałat, 2012 , sid. 1652–1657
  13. ↑ Anstee, Farber, 1988 , sid. 22–28.
  14. ↑ Chepoi, 1997 , sid. 97–100.
  15. ↑ Aigner, Fromme, 1984 , sid. 1–11.

Litteratur

Länkar