Vítězný počet policistů

Policův vítězný graf je neorientovaný graf , na kterém může pronásledovatel (policajt) vyhrát hru na honěnou-únik , ve které pronásleduje lupiče a hráči se střídají v pohybu podél okrajů grafu nebo stojí na místě, dokud policista nezaujme vrchol. kde je lupič [1] . Konečné vítězné policejní grafy se také nazývají analyzovatelné grafy nebo konstruované grafy , protože je lze analyzovat opakovaným odebíráním dominantního vrcholu (vrchol, jehož uzavřené okolí je podmnožinou sousedství jiného vertexu) nebo konstruovat opakovaným přidáváním takového vrcholu. Vítězné grafy policistů lze rozpoznat v polynomiálním čase pomocí chamtivého algoritmu , který generuje pořadí řazení. Tato třída zahrnuje akordické grafy a grafy obsahující univerzální vrchol .

Definice

Úhybné pronásledování

Vítězné grafy policisty (a doplňkovou třídu grafů, vítězné grafy lupiče) představili Nowakowski a Winkler [2] v kontextu následující hry o pronásledování a úniku, kterou připisují G. Gaborovi a A. Kiyo. Dva hráči, policista a lupič, se nacházejí v různých počátečních vrcholech daného grafu. Střídají se ve hře. Během svého tahu se hráč může buď přesunout do sousedního vrcholu, nebo zůstat na místě. Hra končí a policista vyhrává, pokud může ukončit svůj tah ve stejném vrcholu jako lupič. Lupič vyhraje, pokud může donekonečna uhýbat policistovi. Graf vítězného policisty je graf s vlastností, že bez ohledu na to, kde dva hráči začnou hru, vždy může vyhrát policista [3] .

Demontáž

Uzavřené okolí N [ v ] vrcholu v daného grafu je množina vrcholů sestávající z vrcholu v samotného a všech ostatních vrcholů sousedících s v . O vrcholu v se říká, že je ovládán jiným vrcholem w if . To znamená, že v a w jsou sousedící a každý soused v je sousedem w [4] . Nowakowski a Winkler [2] nazývají vrchol, kterému dominuje jiný vrchol , neredukovatelný vrchol [3] .

Pořadí rozebrání nebo pořadí odstranění dominantních vrcholů daného grafu odpovídá takovému pořadí vrcholů, že pokud jsou vrcholy odstraněny jeden po druhém v tomto pořadí, dominuje každý vrchol (kromě posledního). Graf je analyzován tehdy a pouze tehdy, má-li pořadí analýzy [3] [4] .

Vlastnosti uzávěru

Rodina vítězných grafů policistů je uzavřena pod silným součinem grafů . Policajt může vyhrát v přísném součinu výherních grafů policisty tak, že vsadí na jeden z multiplikátorů součinu a poté udělá to samé na ostatních multiplikátorech, přičemž zůstane na stejném vrcholu jako lupič v již vyhraných multiplikátorech [3] . Například graf tahu krále , silný součin dvou cest , je vítězným grafem policisty [5] .

Není pravda, že libovolně vygenerovaný podgraf vítězných grafů policistů vyhrává. Některé speciální generované podgrafy však zůstávají vítězné. Nowakowski a Winkler [2] definují kontrakci grafu G do jednoho z jeho vygenerovaných podgrafů H jako zobrazení z vrcholů G do vrcholů H , které mapuje každý vrchol H do sebe sama a mapuje každé dva sousední vrcholy G na jeden z nich . stejný vrchol nebo do dvojice sousedních vrcholů v H . Pak, jak se říká, rodina vítězných grafů policistů je kontrakce uzavřena. Chcete-li vyhrát na H , můžete simulovat hru na G. Pokud je vítěznou strategií v G pro policistu stát na místě nebo se pohybovat po oblouku, jehož oba vrcholy mapují do stejného vrcholu v H , policista stojí v klidu v H. Ve všech ostatních případech se policista pohybuje po hraně v H , což je obraz vítězné hrany v G pod kontrakcí [3] .

Ekvivalence a parsabilita policistů

Jakýkoli analyzovaný graf je pro policistu vítězný. Vítěznou strategií pro policistu je najít dominantní vrchol v a následovat (indukcí) optimální strategii na grafu vytvořeném smazáním v za předpokladu, že lupič je na vrcholu, který dominuje vrcholu v . To vede buď k tomu, že policista lupiče popadne, nebo je v pozici, kdy je lupič ve vrcholu v a policista je v dominantním vrcholu, z čehož může policista vyhrát provedením jednoho pohybu navíc [3] . Touto strategií lze indukcí dokázat, že v grafu s n vrcholy lze policistu donutit k výhře maximálně v n − 4 tazích [6] [7] .

Naopak každý vítězný graf policistů má dominantní vrchol. Pokud lupič hraje optimálně s cílem protáhnout hru a poslední pozici ve hře před tím, než policista chytí lupiče v uzlu c a lupiče v uzlu r , pak c musí dominovat r , jinak by lupič mohl hru prodloužit o alespoň jeden pohyb. Funkce, která mapuje r na c a ponechává zbytek vrcholů na místě, je kontrakce, takže graf vytvořený odstraněním dominantního vrcholu musí být pro policistu stále vítězný. Indukcí dostaneme, že každý vítězný policejní graf lze analyzovat [3] . Stejné argumenty ukazují, že v grafu bez dominantních vrcholů lupič nikdy neprohraje – vždy dojde k přesunu do vrcholu, který nesousedí s policistou. V libovolném grafu, který pro policistu nevyhrává, může lupič vyhrát odstraněním všech dominantních vrcholů a hraním na zbývajícím podgrafu, který musí být neprázdný, jinak bude graf parsovatelný.

Algoritmy rozpoznávání a rodina všech příkazů demontáže

Pokud je vrchol ve vítězném grafu policisty dominantní, pak (když jsou odstraněny ostatní dominantní vrcholy) zůstává dominantní, dokud není sám odstraněn, nebo zůstává konečným vrcholem pořadí analýzy. Sada správných příkazů analýzy má tedy strukturu antimatroidu a pořadí analýzy lze nalézt pomocí jednoduchého zištného algoritmu , který postupně odstraňuje dominantní vrcholy. Proces je úspěšný tehdy a jen tehdy, když je graf pro policistu vítězný, takže poskytnutím algoritmu pro zjištění pořadí analýzy poskytuje tato metoda algoritmus pro kontrolu, zda daný graf vyhrává pro policistu.

Jedním ze způsobů, jak najít další vrchol k odstranění, je provést následující kroky:

V grafu s n vrcholy, m hranami a degenerací d lze tento proces dokončit v čase O ( dm ) [8] .


Alternativní, ale složitější Spinradův algoritmus [9] používá pro každou sousední dvojici vrcholů ( x , y ) číslo, které nazývá deficit , a toto číslo obsahuje počet sousedů x , kteří nejsou sousedy y . Algoritmus vytváří a udržuje množinu deficitů (sousedy x , kteří nejsou sousedy y ) pouze tehdy, když je deficit malý. Pro urychlení výpočtů používá algoritmus rozhodovací stromy , které klasifikují vrcholy podle jejich sousedství s malými bloky s vrcholy. Algoritmus provádí následující kroky:

Doba trvání této procedury je [10] .

Související rodiny grafů

Jakýkoli konečný tětivový graf je analyzovatelný a jakékoli pořadí vyloučení tětivového grafu (pořadí vrcholů, ve kterém koneční sousedé každého vrcholu tvoří kliku ) je platným pořadím analýzy. Existují však nekonečné akordické grafy, které pro policistu nevyhrávají [11] .

Každý graf, který má univerzální vrchol , je analyzován, protože všem ostatním vrcholům dominuje univerzální vrchol a jakékoli pořadí vrcholů, které umístí univerzální vrchol jako poslední, je správným pořadím analýzy. Naopak téměř všechny analyzované grafy mají univerzální vrchol v tom smyslu, že mezi všemi analyzovanými grafy s n vrcholy se podíl grafů s univerzálním vrcholem blíží jedné, zatímco n má tendenci k nekonečnu [12] .

Policajtovy dědičně vítězné grafy jsou grafy, ve kterých pro policistu vyhrává každý izometrický podgraf. To neplatí pro všechny grafy vítězných policistů. Například kolo s pěti vrcholy je pro policistu vítězné, ale obsahuje izometrický 4-cyklus, který není vítězný, takže graf je dědičně vítězný. Dědičně vítězné grafy policistů jsou stejné jako grafy mostů, ve kterých má každý cyklus délky čtyři nebo více hraniční cestu, tedy dvojici vrcholů, které jsou v grafu blíže než v cyklu [13] . Policajtův vítězný graf je pro policistu dědičně vítězný právě tehdy, když nemá jako vygenerovaný cyklus ani 4-cyklový, ani 5-cyklový. Pro dědičně vítězný policejní graf je obrácení jakéhokoli přechodu na první šířku správným pořadím řazení, což znamená, že jako poslední vrchol pořadí řazení lze zvolit jakýkoli vrchol [14] .

Podobnou hru s více policisty lze použít k určení počtu policistů v grafu, nejmenšího počtu policistů potřebných k vítězství ve hře. Vítězné grafy policistů jsou přesně ty grafy, u kterých je počet policistů roven jednomu [15] .

Poznámky

  1. ↑ Bonato, Nowakowski, 2011 .
  2. ↑ 1 2 3 Nowakowski, Winkler, 1983 .
  3. ↑ 1 2 3 4 5 6 7 Nowakowski a Winkler, 1983 , s. 235–239.
  4. ↑ 1 2 Chepoi, 1998 , str. 414–436.
  5. ↑ O tom, že součin striktní cesty je vítězný graf, viz článek Nowakowského a Winklera ( Nowakowski, Winkler 1983 ). O tom, že královský hrabě je striktní produkt, viz Berend, Korach, Zucker ( Berend, Korach, Zucker 2005 )
  6. ↑ Bonato, Golovach, Hahn, Kratochvíl, 2009 , str. 5588–5595.
  7. ↑ Gavenciak, 2010 , str. 1557–1563
  8. ↑ Lin, Soulignac, Szwarcfiter, 2012 , str. 75–90.
  9. ↑ Spinrad, 2004 .
  10. ↑ Spinrad, 2004 , str. 203–213.
  11. ↑ Hahn, Laviolette, Sauer, Woodrow, 2002 , str. 27–41.
  12. ↑ Bonato, Kemkes, Prałat, 2012 , s. 1652–1657
  13. ↑ Anstee, Farber, 1988 , s. 22–28.
  14. ↑ Chepoi, 1997 , str. 97–100.
  15. ↑ Aigner, Fromme, 1984 , str. 1–11.

Literatura

Odkazy