Nyertes Cop Count

A zsaru nyerő gráfja egy irányítatlan gráf , amelyen az üldöző (a zsaru) megnyerheti az üldözéses-elkerülési játékot , amelyben üldözi a rablót, és a játékosok felváltva mozognak a grafikon szélein, vagy mozdulatlanul állnak, amíg a zsaru el nem éri a csúcsot. ahol a rabló [ 1] . A véges nyerő rendőrségi gráfokat elemezhető gráfoknak vagy konstruált gráfoknak is nevezik , mert elemezhetők egy dominált csúcs újra és újra eltávolításával (olyan csúcs, amelynek zárt szomszédsága egy másik csúcs szomszédságának részhalmaza), vagy létrehozhatók egy ilyen csúcs ismételt hozzáadásával. A győztes zsarugráfok polinomiális időben felismerhetők egy mohó algoritmussal , amely rendezési sorrendet generál. Ebbe az osztályba tartoznak az akkordgráfok és az univerzális csúcsot tartalmazó gráfok .

Definíció

Kitérő üldözés

A rendőr nyerő gráfjait (és a gráfok kiegészítő osztályát, a rabló nyerő gráfjait) Nowakowski és Winkler [2] mutatta be a következő üldözéses-elkerülési játékkal összefüggésben, amelyet G. Gábornak és A.-nak tulajdonítanak. Kiyo. Két játékos, egy rendőr és egy rabló, egy adott gráf különböző kezdeti csúcsaiban található. Felváltva játszanak. A köre során a játékos vagy egy szomszédos csúcsra léphet, vagy a helyén maradhat. A játék akkor ér véget, és a zsaru nyer, ha a zsaru ugyanazon a csúcson tudja befejezni a körét, mint a rabló. A rabló nyer, ha a végtelenségig kikerülheti a zsarut. A nyertes zsaru grafikonja egy olyan grafikon, amely azzal a tulajdonsággal rendelkezik, hogy függetlenül attól, hogy a két játékos hol kezdi a játékot, a zsaru mindig nyerhet [3] .

Szétszerelés

Egy adott gráf v csúcsának N [ v ] zárt környezete a csúcsok halmaza, amely magából a v csúcsból és a v -vel szomszédos összes többi csúcsból áll . Egy v csúcsot egy másik w csúcs uralja, ha . Vagyis v és w szomszédosak, és v bármely szomszédja w szomszédja [4] . Nowakowski és Winkler [2] egy másik csúcs által uralt csúcsot irreducibilis csúcsnak [3] nevezi .

Egy adott gráf dominált csúcsainak szétszedésének vagy kiküszöbölésének sorrendje a csúcsok olyan sorrendjének felel meg, hogy ha a csúcsokat egyenként távolítjuk el ebben a sorrendben, akkor minden csúcs (az utolsó kivételével) dominál. A gráf akkor és csak akkor kerül elemzésre, ha van elemzési sorrendje [3] [4] .

Bezárás tulajdonságai

A győztes rendőrgráfok családját a gráfok erős szorzata zárja be . A zsaru úgy nyerhet a zsaru nyerési grafikonjainak szigorú szorzatában, hogy a szorzat egyik szorzóján hazárdzik, majd ugyanezt teszi a többi szorzón, és ugyanazon a csúcson marad, mint a rabló a már megnyert szorzókban [3] . Például a király mozgásgráfja , két út erős szorzata , egy győztes rendőrgráf [5] .

Nem igaz, hogy a győztes rendőrgráfok tetszőlegesen generált részgráfja nyer. Néhány speciálisan generált részgráf azonban továbbra is nyerő. Nowakowski és Winkler [2] egy G gráf összehúzódását a generált H részgráfok egyikébe úgy határozza meg , mint egy leképezést G csúcsairól H csúcsaira, amely H minden csúcsát önmagába képezi le, és G minden két szomszédos csúcsát leképezi valamelyikre . ugyanarra a csúcsra vagy egy szomszédos csúcspárra H -ben . Aztán, ahogy mondani szokás, a győztes rendőr grafikonok családja összehúzódással zárva van. Ahhoz, hogy H pontban nyerjünk, szimulálhatunk egy játékot G -nél . Ha a nyerő stratégia G -ben a rendőr számára az, hogy egy helyben áll, vagy egy olyan ív mentén mozog, amelynek mindkét csúcsa ugyanarra a H -beli csúcsra van leképezve, akkor a rendőr mozdulatlanul áll H -ban . Minden más esetben a rendőr a H -beli él mentén mozog, ami a G -beli nyerő él képe összehúzódás alatt [3] .

Zsaru kifizetésének egyenértékűsége és értelmezhetősége

Bármely elemzett gráf nyerő a rendőr számára. A rendőr nyerő stratégiája az, hogy keres egy dominált v csúcsot , és követi (indukcióval) az optimális stratégiát a v törlésével kialakított gráfon, feltételezve, hogy a rabló a v csúcsot domináló csúcson van . Ez azt eredményezi, hogy vagy a rendőr megragadja a rablót, vagy olyan helyzetbe kerül, ahol a rabló a v csúcsban , a zsaru pedig a domináns csúcsban van, ahonnan a zsaru egy plusz mozdulattal nyerhet [3] . Ezzel a stratégiával indukcióval bizonyítható, hogy egy n csúcsú gráfban egy rendőr legfeljebb n − 4 lépésben kényszeríthető nyerésre [6] [7] .

Ezzel szemben minden győztes rendőr gráfnak van egy dominált csúcsa. Ha a rabló optimálisan játszik azzal a céllal, hogy elhúzza a játékot, és az utolsó pozíció a játékban, mielőtt a rendőr megragadja a rablót a c csomópontban és a rablót az r csomópontban , akkor c - nek uralnia kell r -t , különben a rabló meghosszabbíthatja a játékot legalább egy mozdulatot. Az a függvény, amely r -t c -re képezi le, és a többi csúcsot a helyén hagyja, egy összehúzódás, tehát a dominált csúcs eltávolításával létrehozott gráfnak továbbra is nyerőnek kell lennie a rendőr számára. Indukcióval azt kapjuk, hogy bármely nyerő rendőrségi gráf értelmezhető [3] . Ugyanezek az érvek azt mutatják, hogy a dominált csúcsok nélküli gráfban a rabló soha nem veszít – mindig van egy olyan csúcs, amely nem szomszédos a rendőrrel. Egy tetszőleges gráfban, amely nem nyerő a rendőr számára, a rabló nyerhet, ha eltávolítja az összes dominált csúcsot, és a fennmaradó részgráfon játszik, amelynek nem szabad üresnek lennie, különben a gráf értelmezhető lesz.

Felismerési algoritmusok és az összes szétszerelési parancs családja

Ha a győztes cop gráf egy csúcsa dominált, akkor (ha a többi dominált csúcsot eltávolítjuk) addig marad dominált, amíg magát el nem távolítják, vagy az elemzési sorrend végső csúcsa marad. Ezért a helyes értelmezési sorrendek halmaza egy antimatroid szerkezetű , és az elemzési sorrend egy egyszerű mohó algoritmussal kereshető meg, amely lépésről lépésre eltávolítja a dominált csúcsokat. A folyamat akkor és csak akkor sikerül, ha a gráf a rendőr számára nyer, így adva egy algoritmust az elemzés sorrendjének megállapítására, ez a módszer egy algoritmust ad annak ellenőrzésére, hogy egy adott gráf nyer-e a rendőr számára.

A következő eltávolítandó csúcs megtalálásának egyik módja a következő lépések végrehajtása:

Egy n csúcsot, m élt és d degenerációt tartalmazó gráfban ez a folyamat O ( dm ) idő alatt befejezhető [8] .


Egy alternatív, de bonyolultabb Spinrad algoritmus [9] egy számot használ, amelyet deficitnek nevez , minden szomszédos csúcspárhoz ( x , y ) , és ez a szám tartalmazza x azon szomszédok számát, amelyek nem szomszédai y -nak . Az algoritmus csak akkor épít fel és tart fenn hiányhalmazt ( x szomszédai , amelyek nem szomszédai y -nak ), ha a hiány kicsi. A számítások felgyorsítása érdekében az algoritmus döntési fákat használ , amelyek a csúcsokat aszerint osztályozzák, hogy szomszédosak a csúcsokkal rendelkező kis blokkokkal. Az algoritmus a következő lépéseket hajtja végre:

Ennek az eljárásnak a futási ideje [10] .

Kapcsolódó grafikoncsaládok

Bármely véges akkordgráf elemezhető, és bármely akkordgráf-kizárási sorrend (a csúcsok sorrendje, amelyben az egyes csúcsok véges szomszédai egy klikket alkotnak ) érvényes elemzési sorrend. Vannak azonban végtelen akkordgráfok, amelyek nem nyerőek a rendőr számára [11] .

Minden olyan gráf, amelynek univerzális csúcsa van, elemzésre kerül, mert az összes többi csúcsot az univerzális csúcs uralja, és minden olyan csúcsrendezés, amely az univerzális csúcsot utolsó helyre teszi, a helyes elemzési sorrend. Ezzel szemben szinte minden elemzett gráfnak van univerzális csúcsa abban az értelemben, hogy az összes elemzett, n csúcsú gráf között az univerzális csúcsú gráfok aránya egyre hajlik, míg n a végtelenbe [12] .

A rendőr örökletesen nyerő grafikonjai olyan grafikonok, amelyekben minden izometrikus részgráf nyerő a rendőr számára. Ez nem igaz minden győztes zsaru grafikonra. Például egy öt csúcsú kerék nyer a rendőr számára, de tartalmaz egy izometrikus 4-ciklust, amely nem nyer, tehát a grafikon örökletesen nyer. Az örökletesen nyerő cop gráfok ugyanazok, mint a hídgráfok, amelyekben minden négy vagy annál hosszabb ciklusnak van egy cutoff útvonala, egy olyan csúcspár, amely közelebb van a gráfban, mint a ciklusban [13] . Egy rendőr győzelmi grafikonja akkor és csak akkor nyer örökletesen egy rendőr számára, ha generált ciklusa nincs sem 4-, sem 5-ciklusú. Egy örökletesen nyerő rendőrségi gráf esetében bármely szélesség-első bejárás megfordítása megfelelő rendezési sorrend, ami azt jelenti, hogy bármelyik csúcsot kiválaszthatjuk a rendezési sorrend utolsó csúcsaként [14] .

Egy hasonló játék több zsaruval meghatározható a grafikonon szereplő zsaruk számának meghatározására, ami a játék megnyeréséhez szükséges legkisebb számú rendőr. A győztes rendőr grafikonok pontosan azok a grafikonok, amelyeknél a rendőrök száma eggyel egyenlő [15] .

Jegyzetek

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski és Winkler, 1983 , p. 235–239.
  4. ↑ 1 2 Chepoi, 1998 , p. 414–436.
  5. ↑ Arról, hogy a szigorú út szorzata nyerő gráf, lásd Nowakowski és Winkler cikkét ( Nowakowski, Winkler 1983 ). Arról, hogy a király grófja szigorú termék, lásd Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , p. 5588–5595.
  7. ↑ Gavenciak, 2010 , p. 1557–1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , p. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , p. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , p. 27–41.
  12. ↑ Bonato, Kemkes, Prałat, 2012 , p. 1652–1657
  13. ↑ Anstee, Farber, 1988 , p. 22–28.
  14. ↑ Chepoi, 1997 , p. 97–100.
  15. ↑ Aigner, Fromme, 1984 , p. 1–11.

Irodalom

Linkek