Adăpost (teoria grafurilor)

În teoria grafurilor, un adăpost este un anumit tip de funcție pe seturile de vârfuri ale unui graf nedirecționat . Dacă există acoperire, ea poate fi folosită de fugar pentru a câștiga jocul de urmărire-evaziune pe grafic, folosind această funcție la fiecare pas al jocului pentru a determina seturile de vârfuri sigure la care să meargă. Coperțile au fost introduse pentru prima dată de Seymour și Thomas [1] ca mijloc de caracterizare a lățimii arborelui graficelor [2] . Alte aplicații ale acestui concept sunt dovada existenței micilor separatori în familii de grafuri închise în minore [3] și descrierea limitelor . șiclicuriminore de grafuri infinite[4][5].

Definiție

Dacă G este un graf nedirecționat și X este un set de vârfuri, atunci muchia X este o componentă conexă nevidă a unui subgraf al lui G format prin ștergerea lui X. Un adăpost de ordinul k într-un grafic G este o funcție β care mapează orice mulțime X cu mai puține de k vârfuri la placa X β ( X ). Această funcție trebuie să satisfacă și constrângeri suplimentare, care sunt definite în diferite moduri de către diverși autori. Numărul k se numește ordine de acoperire [6] .

Definiția originală a lui Seymour și Thomas [2] a unui adăpost necesită proprietatea că oricare două laturi β ( X ) și β ( Y ) trebuie să se atingă - fie trebuie să aibă un vârf comun, fie trebuie să existe o margine ale cărei capete aparțin acestor două părți. În definiția folosită mai târziu de Alon, Seymour și Thomas [3] , ascunderea necesită satisfacerea proprietății mai slabe a monotonității — dacă X ⊆ Y și ambele mulțimi X și Y au mai puține de k vârfuri, atunci β ( Y ) ⊆ β ( X ) . Proprietatea tangenței implică proprietatea monotonității, dar inversul nu va fi neapărat valabil. Totuși, din rezultatele lui Seymour și Thomas [2] rezultă că în graficele finite, dacă există o acoperire cu proprietatea monotonității, atunci există o acoperire cu aceeași ordine și proprietatea de tangență.

Adăposturile cu definiție tangentă sunt strâns legate de mărăcini , familii de subgrafe conectate ale unui graf dat care sunt tangente unele la altele. Ordinea murului este numărul minim de vârfuri necesare în setul de vârfuri care are un reprezentant în fiecare subgraf al familiei. Setul de scânduri β ( X ) pentru acoperirea ordinului k (cu definiția tangenței) formează un mur de ordin cel puțin k , deoarece orice mulțime Y cu mai puține de k vârfuri nu poate acoperi subgraful β ( Y ). Dimpotrivă, din orice mărgănuri de ordinul k , se poate construi un adăpost de același ordin definind β ( X ) (pentru fiecare X ) ca o mărgele X care include toate subgrafele din mărăcinile care nu împart punctele cu   X . Cerința ca subgrafele dintr-o mură să se atingă între ele poate fi folosită pentru a arăta că există o astfel de placă X și că toate plăcile β ( X ) alese în acest fel se ating. Astfel, un grafic are un mărăcini de ordinul k dacă și numai dacă are un adăpost de ordinul k .

Exemplu

Ca exemplu: fie G o rețea cu nouă vârfuri. Definiți un adăpost de ordin-4 în G mapând fiecare set X cu trei sau mai puține vârfuri la o placă X β ( X ) după cum urmează:

Este ușor de verificat direct prin analiza de caz că această funcție β satisface proprietățile de monotonitate ale adăpostului. Dacă X ⊆ Y și X are mai puțin de două vârfuri, sau X este format din două vârfuri care nu sunt două vecine ale unui vârf de colț al rețelei, atunci există o singură placă X și conține orice placă Y. În cazul rămas, X este format din doi vecini ai vârfului colțului și are două laturi X - una este formată din vârful colțului, iar cealaltă (aleasă ca β ( X )) este formată din cele șase vârfuri rămase. Nu contează ce vârf este adăugat la X pentru a forma Y , va exista o placă Y cu cel puțin patru vârfuri, care trebuie să fie o placă unică cea mai mare, deoarece conține mai mult de jumătate din vârfurile care nu sunt din Y. Această granulă Y mare va fi aleasă ca β ( Y ) și va fi un subset de β ( X ). Astfel, în orice caz, proprietatea de monotonitate este satisfăcută.

Urmărire evazivă

Ascunzătoarele modelează anumite clase de strategii pentru un fugar într-un joc de urmărire-evitare în care mai puțin de k urmăritori încearcă să captureze un singur fugar. Pozițiile atât ale urmăritorilor, cât și ale fugarului sunt delimitate de vârfurile unui grafic nedirecționat dat, iar pozițiile atât ale urmăritorilor, cât și ale fugarului sunt cunoscute de ambii jucători. La fiecare tură a jocului, un nou urmăritor poate fi adăugat la un vârf arbitrar al graficului (până când ajungem la o valoare de k urmăritori) sau unul dintre urmăritorii deja existenți poate fi eliminat din grafic. Cu toate acestea, înainte de a adăuga un nou urmăritor, fugarul primește informații unde va fi adăugat urmăritorul și se poate deplasa de-a lungul marginilor graficului până la orice vârf neocupat. În timpul deplasării, fugarul nu poate trece prin vârful ocupat de unul dintre urmăritori.

Dacă k - acoperire (cu proprietatea monotonității) există, atunci fugarul poate evita capturarea la infinit și astfel câștigă dacă se deplasează întotdeauna spre vârful β ( X ), unde X este mulțimea de vârfuri ocupate de urmăritori până la sfârșitul lui. miscarea. Proprietatea de monotonitate a adăpostului asigură că atunci când un nou urmăritor este adăugat la un vârf de graf, vârfurile din β ( X ) vor fi întotdeauna accesibile din poziția curentă a fugarului [2] .

De exemplu, fugarul câștigă acest joc împotriva a trei urmăritori pe o grilă 3 × 3 folosind strategia descrisă, bazându-se pe coperta ordinului 4 descris în exemplu. Cu toate acestea, în același joc, patru urmăritori pot prinde întotdeauna un fugar plasând urmăritorii la trei vârfuri, ceea ce taie zăbrelele în două căi cu câte trei vârfuri fiecare. Apoi plasăm urmăritorul în centrul căii care conține evadatul și, în cele din urmă, îl scoatem pe următorul care nu este adiacent colțului și îl plasăm pe evadat. Astfel, o zăbrele 3 × 3 nu are ordinul de acoperire 5.

Acoperirile cu proprietatea touch permit fugarului să câștige împotriva urmăritorilor mai puternici care pot sări simultan dintr-o poziție în alta [2] .

Relația cu lățimea arborelui, separatorii și minorii

Coperta poate fi folosită pentru a descrie lățimea arborelui unui grafic - un grafic are o acoperire de ordinul k dacă și numai dacă are o lățime a arborelui de cel puțin k − 1 . Descompunerea arborelui poate fi folosită pentru a descrie strategia câștigătoare pentru urmăritori în același joc de urmărire-evitare, astfel încât graficul să aibă o acoperire de ordinul k dacă și numai dacă fugarul câștigă într-un joc corect împotriva mai puțin de k urmăritori. În jocurile câștigate de un fugar, există întotdeauna o strategie optimă sub formă de acoperire, iar în jocurile câștigate de urmăritori, există întotdeauna o strategie optimă sub forma unei descompunere a arborelui [2] . De exemplu, deoarece o rețea 3 × 3 are o acoperire de ordinul 4, dar nu are o acoperire de ordinul 5, trebuie să aibă o lățime a arborelui exact egală cu 3. Aceeași teoremă minimax poate fi generalizată la grafice infinite cu o lățime a arborelui finită dacă, în Definiția lățimii arborelui, arborele subiacent trebuie să nu aibă capete [2] .

Ascunzătoarele sunt, de asemenea, strâns legate de existența separatorilor , o dimensiune mică a seturilor de noduri X într-un grafic de n - vârfuri , astfel încât orice muchie X are cel mult 2n /3 vârfuri. Dacă graficul G nu are un separator cu k vârfuri, atunci orice mulțime X cu cel mult k vârfuri are o muchie X (unica) cu mai mult de 2n /3 vârfuri. În acest caz, G are un adăpost de ordinul k + 1 , în care β ( X ) este definit ca o placă X mare unică . Adică, orice grafic are fie un mic separator, fie o acoperire de ordin înalt [3] .

Dacă graficul G are o acoperire de ordinul k , pentru k ≥ h 3/2 n 1/2 pentru un număr întreg h , atunci G trebuie să aibă și graficul complet K h ca minor . Cu alte cuvinte, numărul Hadwiger al unui grafic n -vertex cu ordinul de acoperire k are o valoare de cel puțin k 2/3 n -1/3 . În consecință, graficele fără K h minori au lățimea arborelui mai mică de h 3/2 n 1/2 și separatoare de dimensiune mai mică de h 3/2 n 1/2 . Mai general, lățimea arborelui O(√ n ) și dimensiunea separatorului sunt valabile pentru orice familie de grafice netriviale care pot fi caracterizate prin grafice interzise , ​​deoarece pentru orice astfel de familie există o constantă h astfel încât familia nu include K h [3] .

În grafice infinite

Dacă un grafic G conține o rază, o cale semi-infinită simplă care are un vârf de început, dar niciun vârf de sfârșit, atunci are o acoperire de ordinul ℵ 0 , adică o funcție β care mapează fiecare mulțime finită X de vârfuri la un X -board care satisface conditiile de acoperire. Și anume, definim β ( X ) ca o placă X unică , care constă dintr-un număr nelimitat de vârfuri de raze. Astfel, în cazul graficelor infinite, legătura dintre lățimea copacului și adăposturi se rupe - o singură rază, în ciuda faptului că este un copac în sine, are adăposturi de toate ordinele finite și, chiar mai puternic, un adăpost de ordinul ℵ 0 . Două raze ale unui graf infinit sunt considerate echivalente dacă nu există un set finit de vârfuri care să separe un număr infinit de vârfuri ale unei raze de un număr infinit de vârfuri ale altei raze. Această relație de echivalență și relațiile sale de echivalență se numesc capetele ale graficului.

Punctele de capăt ale oricărui grafic au o corespondență unu-la-unu cu locurile de ascundere a ordinii ℵ 0 . Orice rază definește o acoperire, iar oricare două fascicule echivalente definesc aceeași acoperire [4] . În schimb, orice acoperire este determinată de raze într-un astfel de mod care poate fi arătat prin următoarea analiză a opțiunilor:

Astfel, orice clasă de echivalență a razei definește o acoperire unică, iar orice acoperire este definită de o clasă de echivalență a razei.

Pentru orice număr cardinal , un grafic infinit G are o acoperire de ordinul κ dacă și numai dacă are o clică minoră de ordinul κ. Adică, pentru numerele cardinale nenumărate, cea mai mare ordine de ascundere din G este numărul Hadwiger al graficului G [4] .

Note

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

Literatură