Vindende politimand

Strisserens vindergraf er en urettet graf , hvorpå forfølgeren (betjenten) kan vinde jagt-unddragelsesspillet , hvor han jagter røveren, og spillerne skiftes til at bevæge sig langs grafens kanter eller stå stille, indtil politimanden tager toppunktet hvor røveren er [1] . Endeligt vindende politigrafer kaldes også parserbare grafer eller konstruerede grafer , fordi de kan parses ved at fjerne et domineret toppunkt igen og igen (et toppunkt, hvis lukkede naboskab er en delmængde af et andet toppunkts nabolag) eller konstrueres ved gentagne gange at tilføje et sådant toppunkt. Vindende politigrafer kan genkendes i polynomisk tid af en grådig algoritme , der genererer en sorteringsrækkefølge. Denne klasse inkluderer akkordgrafer og grafer, der indeholder et universelt toppunkt .

Definition

Undvigende forfølgelse

Politimandens vindergrafer (og den komplementære klasse af grafer, røverens vindergrafer) blev introduceret af Nowakowski og Winkler [2] i forbindelse med det følgende forfølgelses-unddragelsesspil, som de tilskriver G. Gabor og A. Kiyo. To spillere, en politimand og en røver, er placeret ved forskellige indledende hjørner af en given graf. De spiller på skift. Under sin tur kan spilleren enten flytte til et tilstødende hjørne eller blive på plads. Spillet slutter, og betjenten vinder, hvis betjenten kan afslutte sin tur på samme toppunkt som røveren. Røveren vinder, hvis han kan undvige betjenten på ubestemt tid. En vindende politigraf er en graf med den egenskab, at uanset hvor de to spillere starter spillet, kan politimanden altid vinde [3] .

Demontering

Et lukket naboskab N [ v ] af et toppunkt v i en given graf er det sæt af toppunkter, der består af selve toppunktet v og alle andre toppunkter, der støder op til v . Et toppunkt v siges at være domineret af et andet toppunkt w hvis . Det vil sige, at v og w er naboer, og enhver nabo til v er en nabo til w [4] . Nowakowski og Winkler [2] kalder et toppunkt, der er domineret af et andet toppunkt, for et irreducerbart toppunkt [3] .

Demonteringsrækkefølgen eller rækkefølgen af ​​eliminering af dominerede hjørner af en given graf svarer til en rækkefølge af knudepunkter, sådan at hvis spidser fjernes en efter en i den rækkefølge, domineres hvert knudepunkt (undtagen den sidste). Grafen parses, hvis og kun hvis den har en parsingrækkefølge [3] [4] .

Lukningsegenskaber

Familien af ​​vindende politimandsgrafer er lukket under det stærke produkt af grafer . Strisseren kan vinde i det strenge produkt af politimandens vindergrafer ved at spille på en af ​​produktets multiplikatorer og derefter gøre det samme på de andre multiplikatorer, forblive på samme toppunkt som røveren i multiplikatorerne, der allerede har vundet [3] . For eksempel er kongens bevægelsesgraf , det stærke produkt af to stier , en vindergraf for politimanden [5] .

Det er ikke sandt, at en vilkårlig genereret undergraf af vindende politimandsgrafer vinder. Nogle specialgenererede subgrafer vinder dog stadig. Nowakowski og Winkler [2] definerer sammentrækningen af ​​en graf G til en af ​​dens genererede undergrafer H som en afbildning fra toppunkter af G til toppunkter af H , der kortlægger hvert hjørne af H ind i sig selv, og kortlægger hvert andet tilstødende hjørne af G til enten samme toppunkt eller til et par tilstødende toppunkter i H . Så, som de siger, familien af ​​vindende politimand grafer er sammentrækning lukket. For at vinde ved H , kan man simulere et spil ved G. Hvis vinderstrategien i G for politimanden er at stå stille eller bevæge sig langs en bue, hvis begge toppunkter er afbildet til samme toppunkt i H , står politimanden stille i H. I alle andre tilfælde bevæger politimanden sig langs kanten i H , som er billedet af vinderkanten i G under sammentrækning [3] .

Cop payoff ækvivalens og parsability

Enhver parset graf er en vinder for politimanden. Vinderstrategien for politimanden er at finde et domineret toppunkt v og følge (ved induktion) den optimale strategi på grafen dannet ved at slette v , idet det antages at røveren er på et toppunkt der dominerer toppunkt v . Dette resulterer i, at enten politimanden griber røveren eller er i en position, hvor røveren er i toppunktet v og politimanden er på det dominerende toppunkt, hvorfra politimanden kan vinde ved at lave et ekstra træk [3] . Denne strategi kan bruges til at bevise ved induktion, at i en graf med n toppunkter kan en politimand blive tvunget til at vinde i højst n − 4 træk [6] [7] .

Omvendt har enhver vindende politimandsgraf et domineret toppunkt. Hvis røveren spiller optimalt med det formål at trække spillet og den sidste position i spillet ud, før politimanden griber røveren ved node c og røveren ved node r , så skal c dominere r , ellers kan røveren forlænge spillet med mindst et træk. En funktion, der kortlægger r til c og efterlader resten af ​​hjørnerne på plads, er en sammentrækning, så grafen, der dannes ved at fjerne et domineret knudepunkt, skal stadig vinde for politimanden. Ved induktion får vi, at enhver vindende politigraf kan parses [3] . De samme argumenter viser, at i en graf uden dominerede hjørner taber røveren aldrig - der er altid en flytning til et hjørne, der ikke støder op til politimanden. I en vilkårlig graf, der ikke vinder for politimanden, kan røveren vinde ved at fjerne alle dominerede hjørner og spille på den resterende undergraf, som ikke skal være tom, ellers vil grafen være parserbar.

Genkendelsesalgoritmer og en familie af alle demonteringsordrer

Hvis et toppunkt i en vindende politigraf er domineret, så (når andre dominerede toppunkter fjernes) forbliver det domineret, indtil det selv fjernes, eller forbliver det sidste toppunkt i parsingsrækkefølgen. Derfor har sættet af korrekte parsing-rækkefølger strukturen som en antimatroide , og parsing-rækkefølgen kan findes ved en simpel grådig algoritme , der fjerner dominerede hjørner trin for trin. Processen lykkes, hvis og kun hvis grafen vinder for politimanden, så giver denne metode en algoritme til at finde rækkefølgen af ​​parsing, en algoritme til at kontrollere, om en given graf vinder for politimanden.

En måde at finde det næste hjørne, der skal fjernes, er ved at tage følgende trin:

I en graf med n hjørner, m kanter og degeneration d kan denne proces gennemføres på O ( dm ) tid [8] .


En alternativ men mere kompliceret algoritme af Spinrad [9] bruger et tal, som han kalder deficit , for hvert tilstødende par af hjørner ( x , y ) og dette tal indeholder antallet af naboer til x , der ikke er naboer til y . Algoritmen opbygger og vedligeholder et underskudssæt (naboer til x , der ikke er naboer til y ), når underskuddet er lille. For at fremskynde beregningerne bruger algoritmen beslutningstræer, der klassificerer toppunkter i henhold til deres naboskab til små blokke med toppunkter. Algoritmen udfører følgende trin:

Kørselstiden for denne procedure er [10] .

Beslægtede familier af grafer

Enhver finit akkordgraf er parserbar, og enhver akkordgrafekskluderingsrækkefølge (hjørnerækkefølge, hvor hvert toppunkts endelige naboer danner en klike ) er en gyldig parsingsrækkefølge. Der er dog uendelige akkordgrafer, der ikke vinder for politimanden [11] .

Enhver graf, der har et universelt toppunkt , analyseres, fordi alle andre toppunkter er domineret af det universelle toppunkt, og enhver toppunktsrækkefølge, der placerer det universelle toppunkt sidst, er den korrekte parsingsrækkefølge. Omvendt har næsten alle parsede grafer et universelt toppunkt i den forstand, at blandt alle parsede grafer med n toppunkter har andelen af ​​grafer med et universelt toppunkt en tendens til én, da n har en tendens til uendelig [12] .

Politimandens arveligt vindende grafer er grafer, hvor hver isometrisk subgraf vinder for politimanden. Dette er ikke sandt for alle vindende politigrafer. For eksempel vinder et hjul med fem hjørner for politimanden, men indeholder en isometrisk 4-cyklus, der ikke vinder, så grafen vinder arveligt. Arveligt vindende politigrafer er de samme som brografer, hvor enhver cyklus af længde fire eller mere har en afskæringsbane, et par hjørner, der er tættere på grafen end i cyklussen [13] . En politimands vindergraf er arvelig gevinst for en politimand, hvis og kun hvis han hverken har en 4-cyklus eller en 5-cyklus som en genereret cyklus. For en arvelig vindende politigraf er vendingen af ​​enhver bredde-først-gennemgang en korrekt sorteringsrækkefølge, hvilket indebærer, at et hvilket som helst toppunkt kan vælges som det sidste hjørne af sorteringsrækkefølgen [14] .

Et lignende spil med flere betjente kan bruges til at bestemme antallet af betjente på grafen, det mindste antal betjente, der er nødvendige for at vinde spillet. De vindende politimandsgrafer er præcis de grafer, hvor antallet af politimænd er lig med én [15] .

Noter

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski og Winkler, 1983 , s. 235-239.
  4. ↑ 1 2 Chepoi, 1998 , s. 414-436.
  5. ↑ Om det faktum, at et strengt stiprodukt er en vindende graf, se artiklen af ​​Nowakowski og Winkler ( Novakowski, Winkler 1983 ). For det faktum, at kongens greve er et strengt produkt, se 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.

Litteratur

Links