Shelter (teorie grafů)

V teorii grafů je úkryt určitým typem funkce na množinách vrcholů neorientovaného grafu . Pokud existuje krytí, může jej uprchlík použít k vítězství ve hře na honěnou-vyhýbání se na grafu pomocí této funkce v každém kroku hry k určení bezpečných množin vrcholů, do kterých má jít. Kryty poprvé představili Seymour a Thomas [1] jako prostředek k charakterizaci stromové šířky grafů [2] . Dalšími aplikacemi tohoto konceptu jsou důkazy existence malých oddělovačů v rodinách grafů uzavřených v minors [3] a popis hranic a klikových minorů nekonečných grafů [4] [5] .

Definice

Pokud je G neorientovaný graf a X je množina vrcholů, pak hrana X je neprázdná souvislá složka podgrafu G vytvořená vymazáním X. Úkryt řádu k v grafu G je funkce β , která mapuje jakoukoli množinu X s méně než k vrcholy na desku X β ( X ). Tato funkce musí také splňovat další omezení, která jsou různými způsoby definována různými autory. Číslo k se nazývá pořadí krytí [6] .

Původní definice přístřešku podle Seymoura a Thomase [2] vyžaduje vlastnost, že libovolné dvě strany β ( X ) a β ( Y ) se musí navzájem dotýkat – buď musí mít společný vrchol, nebo musí existovat hrana, jejíž konce patří k těmto dvěma stranám. V definici, kterou později použili Alon, Seymour a Thomas [3] , skrývání vyžaduje uspokojení slabší vlastnosti monotonie — pokud X ⊆ Y a obě množiny X a Y mají méně než k vrcholů, pak β ( Y ) ⊆ β ( X ) . Vlastnost tečnosti implikuje vlastnost monotónnosti, ale opak nemusí nutně platit. Z výsledků Seymoura a Thomase [2] však vyplývá, že pokud v konečných grafech existuje krytí s vlastností monotonie, pak existuje krytí se stejným řádem a vlastností tečnosti.

Úkryty s tečnou definicí úzce souvisejí s ostružiníky , rodinami spojených podgrafů daného grafu, které jsou navzájem tečné. Řád ostružiny je minimální počet požadovaných vrcholů v sadě vrcholů, která má zástupce v každém podgrafu rodiny. Množina desek β ( X ) pro pokrytí řádu k (s definicí tečnosti) tvoří ostružinu řádu alespoň k , protože jakákoli množina Y s méně než k vrcholy nemůže pokrýt podgraf β ( Y ). Naopak z libovolného ostružiní řádu k lze zkonstruovat úkryt stejného řádu definováním β ( X ) (pro každé X ) jako X - korálku, která zahrnuje všechny podgrafy v ostružiní, které nesdílejí body s   X . Požadavek, aby se podgrafy v ostružince dotýkaly, lze použít k prokázání, že taková X -board existuje a že všechny takto zvolené desky β ( X ) se navzájem dotýkají. Graf má tedy ostružiní řádu k právě tehdy, když má úkryt řádu k .

Příklad

Jako příklad: nechť G je mřížka s devíti vrcholy. Definujte úkryt řádu 4 v G mapováním každé sady X se třemi nebo méně vrcholy na X - board β ( X ) následovně:

Je snadné ověřit přímo případovou analýzou , že tato funkce β vyhovuje monotónním vlastnostem úkrytu. Pokud má X ⊆ Y a X méně než dva vrcholy nebo X sestává ze dvou vrcholů, které nejsou dvěma sousedy rohového vrcholu mřížky, pak existuje pouze jedna deska X a obsahuje libovolnou desku Y. Ve zbývajícím případě se X skládá ze dvou sousedů rohového vrcholu a má dvě strany X – jednu tvoří rohový vrchol a druhou (vybranou jako β ( X )) tvoří šest zbývajících vrcholů. Nezáleží na tom, který vrchol se přidá k X , aby vytvořil Y , bude zde Y -board s alespoň čtyřmi vrcholy, což musí být unikátní největší deska, protože obsahuje více než polovinu vrcholů, které nejsou z Y . Tato velká Y -kulička bude vybrána jako β ( Y ) a bude podmnožinou β ( X ). Tím je v každém případě splněna vlastnost monotonie.

Úhybné pronásledování

Úkryty modelují určité třídy strategií pro uprchlíka ve hře na pronásledování, ve které se méně než k pronásledovatelů pokouší zajmout jediného uprchlíka. Pozice pronásledovatelů i uprchlíka jsou ohraničeny vrcholy daného neorientovaného grafu a pozice pronásledovatelů i uprchlíka jsou oběma hráčům známy. V každém tahu hry lze do libovolného vrcholu grafu přidat nového pronásledovatele (dokud nedosáhneme hodnoty k pronásledovatelů) nebo lze z grafu odstranit jednoho z již existujících pronásledovatelů. Před přidáním nového pronásledovatele však uprchlík obdrží informaci, kam bude pronásledovatel přidán, a může se pohybovat po okrajích grafu do libovolného neobsazeného vrcholu. Během pohybu nemůže uprchlík projít vrcholem obsazeným jedním z pronásledovatelů.

Pokud existuje k - kryt (s vlastností monotónnosti), pak se uprchlík může donekonečna vyhýbat zajetí a vyhrát, pokud se vždy pohybuje směrem k vrcholu β ( X ), kde X je množina vrcholů obsazených pronásledovateli do konce roku pohyb. Vlastnost úkrytu monotonie zajišťuje, že když je do vrcholu grafu přidán nový pronásledovatel, budou vrcholy v β ( X ) vždy přístupné z aktuální pozice uprchlíka [2] .

Například uprchlík vyhraje tuto hru proti třem pronásledovatelům na mřížce 3 × 3 pomocí popsané strategie, spoléhá se na krytí rozkazu 4 popsaného v příkladu. Ve stejné hře však mohou čtyři pronásledovatelé vždy chytit uprchlíka umístěním pronásledovatelů na tři vrcholy, čímž se mříž rozřízne na dvě cesty se třemi vrcholy. Poté umístíme pronásledovatele do středu cesty obsahující uprchlíka a nakonec odstraníme jednoho pronásledovatele, který nesousedí s rohem, a položíme ho na uprchlíka. Mříž 3 × 3 tedy nemá pořadí krytí 5.

Kryty s dotykovou vlastností umožňují uprchlíkovi vyhrát proti silnějším pronásledovatelům, kteří mohou současně přeskakovat z jedné pozice do druhé [2] .

Vztah se šířkou stromu, oddělovači a nezletilými

Pokrytí lze použít k popisu šířky stromu grafu – graf má pokrytí řádu k právě tehdy, když má šířku stromu alespoň k − 1 . Stromový rozklad lze použít k popisu vítězné strategie pro pronásledovatele ve stejné hře o vyhýbání se pronásledování, takže graf má pokrytí pořadí k tehdy a pouze tehdy, když uprchlík vyhraje ve správné hře proti méně než k pronásledovatelům. Ve hrách vyhraných uprchlíkem je vždy optimální strategie v podobě krytí a ve hrách vyhraných pronásledovateli je vždy optimální strategie v podobě rozkladu stromu [2] . Například, protože mřížka 3 × 3 má pokrytí řádu 4, ale žádné pokrytí řádu 5, musí mít šířku stromu přesně rovnou 3. Stejný teorém minimaxu lze zobecnit na nekonečné grafy s konečnou šířkou stromu, pokud v Definice šířky stromu, základní strom musí mít žádné konce [2] .

Úkryty jsou také úzce spjaty s existencí oddělovačů , malé velikosti X vertexových sad v n -vertexovém grafu tak, že každá X -hrana má nejvýše 2n /3 vrcholů. Pokud graf G nemá oddělovač s k vrcholy, pak jakákoliv množina X s nejvýše k vrcholy má (jedinečnou) desku X s více než 2n /3 vrcholy. V tomto případě má G úkryt řádu k + 1 , ve kterém je β ( X ) definováno jako jedinečná velká X - deska. To znamená, že každý graf má buď malý oddělovač, nebo obálku vyššího řádu [3] .

Pokud má graf G pokrytí řádu k , pro k ≥ h 3/2 n 1/2 pro nějaké celé číslo h , pak G musí mít také celý graf K h jako vedlejší . Jinými slovy, Hadwigerovo číslo n -vrcholového grafu s řádem pokrytí k má hodnotu alespoň k 2/3 n −1/3 . V důsledku toho mají grafy bez Kh minors šířku stromu menší než h 3/2 n 1/2 a oddělovače o velikosti menší než h 3/2 n 1/2 . Obecněji platí, že hranice šířky stromu O(√ n ) a velikost separátoru platí pro jakoukoli netriviální rodinu grafů, kterou lze charakterizovat zakázanými grafy , protože pro každou takovou rodinu existuje konstanta h taková, že rodina nezahrnuje Kh [ 3] .

V nekonečných grafech

Pokud graf G obsahuje paprsek, polonekonečnou jednoduchou cestu, která má počáteční vrchol, ale žádný koncový vrchol, pak má pokrytí řádu ℵ 0 , tedy funkci β , která mapuje každou konečnou množinu X vrcholů na X -board splňující podmínky krytí. Jmenovitě definujeme β ( X ) jako unikátní X -board, který se skládá z neomezeného počtu vrcholů paprsků. V případě nekonečných grafů se tedy spojení mezi šířkou stromu a úkryty přeruší – jediný paprsek, přestože je sám o sobě stromem, má úkryty všech konečných řádů a ještě silněji úkryt řádu ℵ 0 . Dva paprsky nekonečného grafu jsou považovány za ekvivalentní, pokud neexistuje žádná konečná množina vrcholů, která by oddělovala nekonečný počet vrcholů jednoho paprsku od nekonečného počtu vrcholů druhého paprsku. Tento vztah ekvivalence a jeho relace ekvivalence se nazývají konce grafu.

Koncové body libovolného grafu mají vzájemnou korespondenci s úkryty řádu ℵ 0 . Libovolný paprsek definuje krytí a libovolné dva ekvivalentní paprsky definují stejné krytí [4] . Naopak jakýkoli kryt je určen paprsky takovým způsobem, který lze ukázat pomocí následující analýzy možností:

Jakákoli třída ekvivalence paprsků tedy definuje jedinečné krytí a jakékoli krytí je definováno třídou ekvivalence paprsků.

Pro libovolné kardinální číslo má nekonečný graf G kryt řádu κ právě tehdy, když má klikovou menší řád κ. To znamená, že pro nesčetná kardinální čísla je největší úkryt v G Hadwigerovo číslo grafu G [4] .

Poznámky

  1. ↑ Seymour, Thomas, 1993 .
  2. ↑ 1 2 3 4 5 6 7 Seymour a Thomas, 1993 , s. 22–33.
  3. ↑ 1 2 3 4 Alon, Seymour, Thomas, 1990 , str. 801–808.
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1991 , str. 303–319.
  5. ↑ 1 2 Diestel, Kühn, 2003 , s. 197–206.
  6. ↑ Johnson, Robertson, Seymour, Thomas, 2001 , str. 138–155.

Literatura