Shelter (grafteori)

I grafteorin är ett skydd en viss typ av funktion på vertexuppsättningarna av en oriktad graf . Om täckning finns kan den användas av flyktingen för att vinna jakt-undvikande spelet på grafen genom att använda den här funktionen i varje steg av spelet för att bestämma säkra vertexuppsättningar att gå till. Omslag introducerades först av Seymour och Thomas [1] som ett sätt att karakterisera grafernas trädbredd [2] . Andra tillämpningar av detta koncept är beviset på förekomsten av små separatorer i familjer av grafer stängda i moll [3] och beskrivningen av gränser och klickmolor för oändliga grafer [4] [5] .

Definition

Om G är en oriktad graf och X är en uppsättning av hörn, så är X -kanten en icke-tom ansluten komponent av en subgraf av G bildad genom att radera X. Ett skydd av ordningen k i en graf G är en funktion β som mappar vilken uppsättning X som helst med färre än k hörn till X -tavlan β ( X ). Denna funktion måste också uppfylla ytterligare begränsningar, som definieras på olika sätt av olika författare. Talet k kallas täckordern [ 6] .

Den ursprungliga definitionen av Seymour och Thomas [2] av ett skydd kräver egenskapen att alla två sidor β ( X ) och β ( Y ) måste vidröra varandra - antingen måste de ha en gemensam vertex, eller så måste det finnas en kant vars ändar tillhör dessa två sidor. I definitionen som senare används av Alon, Seymour och Thomas [3] kräver att dölja att man uppfyller den svagare egenskapen monotoni - om X ⊆ Y och båda mängderna X och Y har färre än k hörn, då β ( Y ) ⊆ β ( X ) . Egenskapen tangens innebär egenskapen monotoni, men det omvända kommer inte nödvändigtvis att gälla. Emellertid följer det av resultaten av Seymour och Thomas [2] att i finita grafer, om ett täcke med monotoniegenskapen existerar, så finns det ett täcke med samma ordningsföljd och tangensegenskapen.

Tangent-definitionsskydd är nära besläktade med brönor , familjer av sammankopplade subgrafer av en given graf som tangerar varandra. Ordningen på björnbäret är det minsta antal hörn som krävs i vertexuppsättningen som har en representant i varje subgraf i familjen. Uppsättningen av brädor β ( X ) för att täcka ordning k (med definitionen av tangency) bildar en björnbär av ordning åtminstone k , eftersom varje uppsättning Y med färre än k hörn inte kan täcka subgrafen β ( Y ). Omvänt, från vilken tröja av ordningen k som helst , kan man konstruera ett skydd av samma ordning genom att definiera β ( X ) (för varje X ) som en X -pärla som inkluderar alla subgrafer i tröskan som inte delar punkter med   X . Kravet att subgrafer i en björnbär berör varandra kan användas för att visa att en sådan X -bräda finns, och att alla brädor β ( X ) som väljs på detta sätt berör varandra. Således har en graf en torn av ordningen k om och endast om den har ett skydd av ordningen k .

Exempel

Som ett exempel: låt G vara ett gitter med nio hörn. Definiera en order-4 skydd i G genom att mappa varje uppsättning X med tre eller färre hörn till en X -board β ( X ) enligt följande:

Det är lätt att direkt kontrollera med fallanalys att denna funktion β uppfyller skyddets monotoniska egenskaper. Om X ⊆ Y och X har mindre än två hörn, eller X består av två hörn som inte är två grannar till en hörnhörn på gittret, så finns det bara en X -tavla och den innehåller valfri Y -tavla. I det återstående fallet består X av två grannar till hörnpunkten och har två X -sidor - den ena består av hörnpunkten och den andra (vald som β ( X )) består av de sex återstående hörnpunkterna. Det spelar ingen roll vilken vertex som läggs till X för att bilda Y , det kommer att finnas en Y -bräda med minst fyra hörn, vilket måste vara en unikt största bräda eftersom den innehåller mer än hälften av hörnen som inte kommer från Y . Denna stora Y -pärla kommer att väljas som β ( Y ) och kommer att vara en delmängd av β ( X ). Sålunda är i alla fall monotonicitetsegenskapen uppfylld.

Undvikande jakt

Hideouts modellerar vissa klasser av strategier för en flykting i ett jakt-undvikande spel där färre än k förföljare försöker fånga en enda flykting. Positionerna för både förföljarna och flyktingen begränsas av hörnen på en given oriktad graf, och positionerna för både förföljarna och flyktingen är kända för båda spelarna. Vid varje varv i spelet kan en ny förföljare läggas till i en godtycklig hörn av grafen (tills vi når ett värde på k förföljare) eller så kan en av de redan befintliga förföljarna tas bort från grafen. Men innan han lägger till en ny förföljare, får den flyktiga informationen var förföljaren kommer att läggas till, och kan röra sig längs kanterna på grafen till valfri oupptagen vertex. Under rörelsen kan flyktingen inte passera genom toppen som ockuperas av en av förföljarna.

Om k - täckning (med egenskapen monotonitet) existerar, kan flyktingen undvika fångst på obestämd tid och därmed vinna om han alltid rör sig mot vertex β ( X ), där X är uppsättningen av hörn som upptas av förföljarna i slutet av Förflyttningen. Skyddsmonotonicitetsegenskapen säkerställer att när en ny förföljare läggs till en grafvertex, kommer hörnen i β ( X ) alltid att vara åtkomliga från flyktingens nuvarande position [2] .

Till exempel vinner flyktingen det här spelet mot tre förföljare på ett 3 × 3 rutnät med den beskrivna strategin, beroende på omslaget av ordning 4 som beskrivs i exemplet. Men i samma spel kan fyra förföljare alltid fånga en flykting genom att placera förföljarna vid tre hörn, vilket skär gallret i två banor med tre hörn vardera. Vi placerar sedan förföljaren i mitten av vägen som innehåller rymden, och tar slutligen bort den förföljare som inte ligger intill hörnet och placerar den på rymlingen. Således har ett 3 × 3 gitter inte täckordning 5.

Omslag med beröringsegenskapen tillåter flyktingen att vinna mot starkare förföljare som samtidigt kan hoppa från en position till en annan [2] .

Förhållande med trädbredd, avgränsare och mindreåriga

Omslag kan användas för att beskriva trädbredden på en graf - en graf har en täckning av ordningen k om och endast om den har en trädbredd på minst k − 1 . Trädsönderdelningen kan användas för att beskriva den vinnande strategin för förföljarna i samma jakt-undvikande spel, så att grafen har en täckning av ordningen k om och endast om den flyende vinner i ett korrekt spel mot mindre än k förföljare. I spel som vunnits av en flykting finns det alltid en optimal strategi i form av täckning, och i spel vunna av förföljare finns det alltid en optimal strategi i form av en trädnedbrytning [2] . Till exempel, eftersom ett 3 × 3 gitter har en täckning av ordning 4 men ingen täckning av ordning 5, måste det ha en trädbredd exakt lika med 3. Samma minimaxsats kan generaliseras till oändliga grafer med en ändlig trädbredd om, i definition av trädbredd måste det underliggande trädet inte ha några ändar [2] .

Gömställen är också nära besläktade med förekomsten av separatorer , en liten storlek av X vertexuppsättningar i en n - vertexgraf så att vilken X -kant som helst har högst 2n /3 hörn. Om grafen G inte har en separator med k hörn, så har varje uppsättning X med högst k hörn en (unik) X -kant med mer än 2n /3 hörn. I detta fall har G ett skydd av ordningen k + 1 , där β ( X ) definieras som en unik stor X -bräda. Det vill säga, vilken graf som helst har antingen en liten separator eller en hög ordningsomslag [3] .

Om grafen G har en täckning av ordningen k , för k ≥ h 3/2 n 1/2 för något heltal h , så måste G också ha hela grafen K h som moll . Med andra ord har Hadwiger-talet för en n -vertexgraf med täckordning k ett värde på minst k 2/3 n −1/3 . Som en följd av detta har grafer fria från K h minors trädbredd mindre än h 3/2 n 1/2 och separatorer med storlek mindre än h 3/2 n 1/2 . Mer generellt gäller trädbredden O(√ n ) bunden och separatorstorleken för alla icke-triviala familjer av grafer som kan karakteriseras av förbjudna grafer , eftersom det för en sådan familj finns en konstant h så att familjen inte inkluderar K h [3] .

I oändliga grafer

Om en graf G innehåller en stråle, en semi-oändlig enkel bana som har en startpunkt men ingen slutpunkt, så har den en täckning av ordningen ℵ 0 , det vill säga en funktion β som mappar varje ändlig mängd X av hörn till en X -board som uppfyller täckningsvillkoren. Vi definierar nämligen β ( X ) som ett unikt X -board, som består av ett obegränsat antal strålhörn. Sålunda, i fallet med oändliga grafer, bryts sambandet mellan trädbredd och skydd – en enda stråle, trots att den är ett träd i sig själv, har skydd av alla ändliga ordningar, och ännu starkare, ett skydd av storleksordningen ℵ 0 . Två strålar i en oändlig graf anses vara ekvivalenta om det inte finns någon ändlig uppsättning av hörn som skiljer ett oändligt antal hörn av en stråle från ett oändligt antal hörn av en annan stråle. Denna ekvivalensrelation och dess ekvivalensrelationer kallas ändarna av grafen.

Slutpunkterna för varje graf har en en-till-en-överensstämmelse med gömställen för ordning ℵ 0 . Vilken stråle som helst definierar ett hölje, och alla två ekvivalenta strålar definierar samma hölje [4] . Omvänt bestäms varje täckning av strålarna på ett sådant sätt som kan visas genom följande analys av alternativ:

Sålunda definierar vilken strålekvivalensklass som helst en unik täckning, och varje täckning definieras av en strålekvivalensklass.

För vilket kardinalnummer som helst har en oändlig graf G en täckning av ordningen κ om och endast om den har en klick moll av ordningen κ. Det vill säga, för oräkneliga kardinaltal är den största gömordningen i G Hadwiger -talet på grafen G [4] .

Anteckningar

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

Litteratur