Haven (grafteori) - Haven (graph theory)
I grafteorin är en fristad en viss typ av funktion på uppsättningar av hörn i en oriktad graf . Om det finns en fristad kan den användas av en evader för att vinna ett jaktflykt- spel i diagrammet genom att konsultera funktionen i varje steg i spelet för att bestämma en säker uppsättning hörn att flytta in i. Havens introducerades först av Seymour & Thomas (1993) som ett verktyg för att karakterisera grafbredden . Deras andra applikationer inkluderar bevisa förekomsten av små separatorer på mindre slutna familjer av grafer och karakterisera ändarna och Clique minderåriga av oändliga grafer .
Definition
Om G är en oriktad graf, och X är en uppsättning av vertexpunkter, då en X -flap är en icke-tom ansluten komponent av subgraf av G bildad genom att ta bort X . En oas av ordning k i G är en funktion β som tilldelar en X- flik β ( X ) till varje uppsättning X på färre än k- hörn. Denna funktion måste också uppfylla ytterligare begränsningar som ges olika av olika författare. Siffran k kallas ordningen för fristaden.
I den ursprungliga definitionen av Seymour och Thomas krävs en fristad för att tillfredsställa egenskapen att varannan flik β ( X ) och β ( Y ) måste röra varandra: antingen delar de en gemensam topp eller så finns det en kant med en slutpunkt i varje klaff. I definitionen som används senare av Alon, Seymour och Thomas krävs tillflyktsort istället för att tillfredsställa en svagare monotonicitetsegenskap : om X ⊆ Y , och både X och Y har färre än k- hörn, då β ( Y ) ⊆ β ( X ) . Den rörande egenskapen innebär monotonicitetsegenskapen, men inte nödvändigtvis vice versa. Det följer dock av resultaten från Seymour och Thomas att, om det finns en oas med monotonicitetsegenskapen i ändliga grafer, finns det en med samma ordning och den rörande egenskapen.
Havens med den rörande definitionen är nära besläktade med brambles , familjer av anslutna underbilder av en given graf som alla rör varandra. Ordningen på en bramble är det minsta antalet hörn som behövs i en uppsättning hörn som träffar alla underbilder i familjen. Uppsättningen av klaffarna β ( X ) för en oas av ordning k (med den rörande definitionen) bildar en ordning av ordning åtminstone k , eftersom varje uppsättning Y på färre än k- hörn misslyckas med att träffa undergrafen β ( Y ). Omvänt kan man från valfri bram av ordning k konstruera en oas av samma ordning genom att definiera β ( X ) (för varje val av X ) för att vara X- fliken som inkluderar alla underbilderna i bramblen som är oskiljaktiga från X . Kravet på att underbilderna i bramblingen alla rör varandra kan användas för att visa att denna X- flik existerar, och att alla de på detta sätt valda flikarna β ( X ) rör varandra. Således har en graf en bramble av ordning k om och endast om den har en oas av ordning k .
Exempel
Som ett exempel, låt G vara ett diagram med nio toppar . Definiera en oas av ordning 4 i G , mappa varje uppsättning X med tre eller färre hörn till en X- flik β ( X ), enligt följande:
- Om det finns en unik X- flik som är större än någon av de andra X- flikarna, låt β ( X ) vara den unika stora X- fliken.
- Annars väljer du β ( X ) godtyckligt för att vara vilken som helst X- flik.
Det är enkelt att verifiera genom en fallanalys att denna funktion β uppfyller den fristående egenskapen hos en oas. Om X ⊆ Y och X har färre än två hörn, eller X har två hörn som inte är de två grannarna till ett hörnhörn i gallret, så finns det bara en X- flik och den innehåller varje Y- flik. I det återstående fallet består X av de två grannarna till ett hörnkropp och har två X- flikar: en bestående av den hörnkanten och en annan (vald som β ( X )) bestående av de sex återstående topparna. Oavsett vilken vertex läggs till X för att bilda Y , kommer det att finnas en Y -flap med minst fyra hörn, som måste vara den unika största fliken eftersom den innehåller mer än hälften av hörnen inte i Y . Denna stora Y- flik kommer att väljas som β ( Y ) och kommer att vara en delmängd av β ( X ). Således gäller i båda fallen monotonicitet.
Förföljelse-undvikande
Havens modellerar en viss klass av strategier för en evader i ett jaktflykt- spel där färre än k- förföljare försöker fånga en enda evader, förföljarna och evaderna är båda begränsade till topparna i en given oriktad graf och positionerna för förföljare och evader är kända för båda spelarna. Vid varje drag i spelet kan en ny förföljare läggas till i en godtycklig topp i diagrammet (så länge färre än k förföljare placeras i diagrammet när som helst) eller en av de redan tillagda förföljarna kan tas bort från Graf. Innan en ny förföljare läggs till informeras emellertid undvikaren först om sin nya plats och kan röra sig längs diagrammets kanter till varje ledig topp. Under rörelse kanske undvikaren inte passerar någon topp som redan är upptagen av någon av förföljarna.
Om en k -haven (med monotonicitetsegenskapen) existerar kan undvikaren undvika att fångas på obestämd tid och vinna spelet genom att alltid flytta till en topp av β ( X ) där X är den uppsättning hörn som kommer att upptas av förföljare i slutet av flytten. Monotonicitetsegenskapen hos ett tillflyktsort garanterar att, när en ny förföljare läggs till i ett toppunkt i diagrammet, kan hörnpunkterna i β ( X ) alltid nås från undvikarens nuvarande position.
Till exempel kan en evader vinna detta spel mot tre förföljare på ett 3 × 3- rutnät genom att följa denna strategi med den oas av ordning 4 som beskrivs i exemplet. Men på samma diagram kan fyra förföljare alltid fånga undvikaren genom att först flytta till tre hörn som delar upp nätet på två tre-vertex banor och sedan flytta in i mitten av banan som innehåller undvikaren och tvinga undvikaren till en av hörnhörnarna och slutligen ta bort en av de förföljare som inte ligger i anslutning till detta hörn och placera den på undvikaren. Därför kan 3 × 3- rutnätet inte ha någon oas av ordning 5.
Havens med den rörande egenskapen gör det möjligt för undvikaren att vinna spelet mot kraftfullare förföljare som samtidigt kan hoppa från en uppsättning ockuperade hörn till en annan.
Anslutningar till träbredd, separatorer och minderåriga
Havens kan användas för att karakterisera diagrambredden : en graf har en oas av ordningen k om och endast om den har trebredd åtminstone k - 1 . En trädnedbrytning kan användas för att beskriva en vinnande strategi för förföljarna i samma jakt-undvikande spel, så det är också sant att en graf har en oas av ordning k om och bara om undvikaren vinner med bästa spel mot färre än k förföljare. I spel som vunnts av undvikaren finns det alltid en optimal strategi i den form som beskrivs av en fristad, och i spel som vunnit förföljaren finns det alltid en optimal strategi i den form som beskrivs av en trädnedbrytning. Till exempel, eftersom 3 × 3- rutnätet har en oas av ordning 4, men inte har en oas av ordning 5, måste den ha trebredd exakt 3. Samma min-max-sats kan generaliseras till oändliga grafer med ändlig trebredd, med en definition av trädbredd där det underliggande trädet måste vara strålfritt (det vill säga utan ändar ).
Havens är också nära besläktade med förekomsten av separatorer , små uppsättningar X av hörn i en n- vertikalgraf så att varje X- flik har högst 2 n / 3 hörn. Om ett diagram G inte har en k- vertikal separator, har varje uppsättning X av högst k- hörn en (unik) X- flik med mer än 2 n / 3 hörn. I detta fall har G en oas av ordningen k + 1 , där β ( X ) definieras som denna unika stora X- flik. Det vill säga att varje graf har antingen en liten avgränsare eller en oas av hög ordning.
Om en graf G har en oas av ordningen k , med k ≥ h 3/2 n 1/2 för något heltal h , måste G också ha ett komplett diagram K h som mindre . Med andra ord är Hadwiger-numret i en n- vertikalgraf med en oas av ordning k minst k 2/3 n −1/3 . Som en konsekvens, den K h -minor fria grafer har treewidth mindre än h 3/2 n 1/2 och separatorer av storlek mindre än h 3/2 n 1/2 . Mer allmänt gäller en O ( √ n ) bunden på trebredd och separatorstorlek för alla icke-småfamiljer av grafer som kan karakteriseras av förbjudna minderåriga , för för en sådan familj finns det en konstant h så att familjen inte inkluderar K h .
I oändliga diagram
Om en graf G innehåller en stråle, en halv-oändlig enkel väg med en startpunkt, men ingen slutpunkt, har den en oas av ordning ℵ 0 : det vill säga en funktion β som mappar varje ändlig uppsättning X av hörn till en X -flik, som uppfyller villkoren för konsistens för tillflyktsort. Definiera nämligen β ( X ) för att vara den unika X- fliken som innehåller oändligt många strålar. Således, i fallet med oändliga grafer, går sambandet mellan trädbredd och tillflyktsort samman: en enda stråle, trots att den är ett träd, har tillflyktsort av alla ändliga ordningar och ännu starkare en oas av ordning ℵ 0 . Två strålar i ett oändligt diagram anses vara ekvivalenta om det inte finns någon ändlig uppsättning av hörn som skiljer oändligt många hörn av en stråle från oändligt många hörn av den andra strålen; detta är en ekvivalensrelation , och dess ekvivalensklasser kallas ändar av grafen.
Ändarna på valfri graf överensstämmer med sin ordning ens 0 . För varje stråle bestämmer en fristad, och varannan ekvivalent strålning bestämmer samma fristad. Omvänt bestäms varje tillflyktsort av en stråle på detta sätt, vilket kan visas av följande fallanalys:
- Om tillflyktsorten har egenskapen att korsningen (där korsningen sträcker sig över alla ändliga uppsättningar X ) i sig är en oändlig uppsättning S , så kan varje ändlig enkel väg som slutar i en topp av S förlängas för att nå en ytterligare topp av S , och upprepa denna förlängningsprocess producerar en stråle som passerar genom oändligt många S- hörn . Denna stråle bestämmer den givna fristaden.
- Å andra sidan, om S är ändlig, kan (genom att arbeta i undergrafen G \ S ) antas vara tom. I det här fallet, för varje ändlig mängd X i hörn finns en ändlig mängd X i + 1 med egenskapen att X i är disjunkta från . Om en rånare följer undflygningsstrategin som bestäms av fristaden, och polisen följer en strategi som ges av denna sekvens av uppsättningar, så bildar vägen som rånaren följer en stråle som bestämmer fristaden.
Således definierar varje ekvivalensklass av strålar en unik oas, och varje oas definieras av en ekvivalensklass av strålar.
För varje huvudnummer har en oändlig graf G en oas av ordning κ om och endast om den har en klick mindre av ordning κ. Det vill säga, för oräkneliga cardinalities, den största ordern i en oas i G är Hadwiger antal av G .
