Menedék (gráfelmélet)

A gráfelméletben a menedék egy bizonyos típusú függvény egy irányítatlan gráf csúcshalmazain . Ha létezik fedezet, a szökevény felhasználhatja az üldözéses-elkerülési játék megnyerésére a grafikonon úgy, hogy a játék minden lépésében ezt a funkciót használja, hogy meghatározza a biztonságos csúcskészleteket, ahová menni kell. A borítókat először Seymour és Thomas vezette be [1] a gráfok faszélességének jellemzésére [2] . Ennek a koncepciónak további alkalmazásai a kis elválasztók létezésének bizonyítása a kisebbekre zárt gráfcsaládokban [3] és a határok leírása. ésa végtelen gráfokkisebb klikkjei [4][5].

Definíció

Ha G egy irányítatlan gráf, X pedig csúcsok halmaza, akkor az X -él a G egy részgráfjának nem üres összefüggő komponense, amely X törlésével keletkezik . A G gráf k - rendű menedékhelye egy β függvény , amely bármely k -nál kevesebb csúcsú X halmazt leképez a β X - táblára ( X ). Ennek a függvénynek további megszorításoknak is eleget kell tennie, amelyeket különböző szerzők többféleképpen határoznak meg. A k számot fedőrendnek [6] nevezzük .

Seymour és Thomas [2] eredeti definíciója a menedékről megköveteli azt a tulajdonságot, hogy bármely két β ( X ) és β ( Y ) oldalnak érintkeznie kell egymással - vagy közös csúcsuk van, vagy kell lennie egy élnek, amelynek végei. ehhez a két oldalhoz tartoznak. A későbbiekben Alon, Seymour és Thomas [3] által használt definícióban az elrejtés megköveteli a monotonitás gyengébb tulajdonságának kielégítését – ha X ⊆ Y és mindkét X és Y halmaznak kevesebb, mint k csúcsa van, akkor β ( Y ) ⊆ β ( X ) ) . Az érintés tulajdonsága magában foglalja a monotonitás tulajdonságát, de ennek az ellenkezője nem feltétlenül áll fenn. Seymour és Thomas [2] eredményeiből azonban az következik, hogy véges gráfokban, ha létezik monotonitási tulajdonságú fedő, akkor létezik ugyanilyen sorrendű és érintő tulajdonságú fedő.

Az érintődefiníciós menedékhelyek szorosan kapcsolódnak a brambles -hez, egy adott gráf összefüggő részgráfjaihoz, amelyek érintik egymást. A szeder sorrendje a csúcsok minimális száma szükséges abban a csúcshalmazban, amelynek a család minden részgráfjában van egy képviselője. A k rend lefedésére szolgáló β ( X ) táblák halmaza (az érintő definíciójával) legalább k rendű szederhalmazt képez , mivel bármely k-nál kevesebb csúcsú Y halmaz nem fedheti le a β ( Y ) részgráfot. Megfordítva, bármely k rendű szárból létrehozhatunk egy ugyanolyan rendű menedéket, ha β ( X )-t (mindegyik X -re ) X -gyöngyként definiáljuk, amely tartalmazza az összes olyan részgráfot a karámban, amelyek nem osztoznak   X -szel . Az a követelmény, hogy a szederben a részgráfok érintsék egymást, megmutathatjuk, hogy létezik ilyen X -tábla, és hogy az így kiválasztott β ( X ) táblák érintik egymást. Így egy gráfnak akkor és csak akkor van k -rendű karámja, ha van k rendű menedéke .

Példa

Példaként: legyen G kilenc csúcsú rács . Határozzon meg egy 4-es sorrendű menedéket G -ben úgy, hogy minden három vagy kevesebb csúcsot tartalmazó X halmazt leképez egy X - táblára β ( X ) a következőképpen:

Esetanalízissel könnyen ellenőrizhető, hogy ez a β függvény kielégíti-e a menedék monotonitási tulajdonságait. Ha X ⊆ Y és X kettőnél kevesebb csúcsot tartalmaz, vagy X két olyan csúcsból áll, amelyek nem két szomszédja a rács egyik sarokcsúcsának, akkor csak egy X -tábla van , és ez tartalmaz bármilyen Y -táblát. A fennmaradó esetben X a sarokcsúcs két szomszédjából áll, és két X -oldala van - az egyik a sarokcsúcsból, a másik pedig ( β ( X )) a fennmaradó hat csúcsból áll. Nem számít, hogy melyik csúcsot adjuk hozzá X -hez, hogy Y -t hozzunk létre , lesz egy Y -tábla, amelynek legalább négy csúcsa van, aminek egyedi legnagyobb táblának kell lennie, mivel a csúcsok több mint felét nem Y -ból tartalmazza . Ezt a nagy Y -gyöngyöt β ( Y ) -nek választjuk, és β ( X ) részhalmaza lesz . Így mindenesetre a monotonitási tulajdonság teljesül.

Kitérő üldözés

A búvóhelyek bizonyos stratégiákat modelleznek a szökevények számára egy üldözéses elkerülő játékban, amelyben k - nál kevesebb üldöző próbál meg egyetlen szökevényt elfogni. Mind az üldözők, mind a szökevény pozícióit egy adott irányítatlan gráf csúcsai határolják, és mind az üldözők, mind a szökevény pozícióit mindkét játékos ismeri. A játék minden fordulójában a gráf tetszőleges csúcsához hozzáadható egy új üldöző (amíg el nem érjük a k üldözők értékét), vagy a már meglévő üldözők egyike eltávolítható a gráfból. Azonban, mielőtt új üldözőt adna hozzá, a szökevény információt kap arról, hogy hol lesz hozzáadva az üldözőhöz, és a gráf élei mentén mozoghat bármely nem foglalt csúcsra. A mozgás során a menekülő nem tud áthaladni az egyik üldöző által elfoglalt tetején.

Ha létezik k - fedő (a monotonitás tulajdonságával), akkor a szökevény korlátlanul elkerülheti az elfogást, és így nyerhet, ha mindig a β ( X ) csúcs felé mozog, ahol X az üldözők által elfoglalt csúcsok halmaza a végére. a mozgás. A menedék monotonitás tulajdonsága biztosítja, hogy amikor egy új üldözőt adunk egy gráfcsúcshoz, a β ( X ) csúcsai mindig elérhetőek lesznek a menekülő aktuális pozíciójából [2] .

Például a szökevény megnyeri ezt a játékot három üldözővel szemben egy 3 × 3 -as rácson a leírt stratégiát alkalmazva, a példában leírt 4. sorrend fedezésére támaszkodva. Azonban ugyanabban a játékban négy üldöző mindig elkaphat egy szökevényt, ha az üldözőket három csúcsra helyezi, ami a rácsot két, egyenként három csúcsú útra vágja. Ezután helyezzük az üldözőt a szököttet tartalmazó ösvény közepére, végül eltávolítjuk azt az üldözőt, amelyik nem szomszédos a sarokkal, és ráhelyezzük a szököttre. Így egy 3 × 3-as rácsnak nincs 5-ös fedési sorrendje.

Az érintési tulajdonsággal rendelkező burkolatok lehetővé teszik a menekülő számára, hogy nyerjen erősebb üldözők ellen, akik egyszerre tudnak egyik pozícióból a másikba ugrani [2] .

Kapcsolat a faszélességgel, az elválasztókkal és a minorokkal

A fedők használhatók egy gráf faszélességének leírására - a gráfnak akkor és csak akkor van k nagyságrendű fedője, ha a faszélessége legalább k − 1 . A fa dekompozícióval leírható az üldözők nyerési stratégiája ugyanabban az üldözés-elkerülő játékban, így a grafikonnak akkor és csak akkor van k sorrendű borítója, ha a szökevény helyes játékban nyer k -nél kevesebb üldözővel szemben . A szökevény által nyert játékokban mindig van egy optimális stratégia fedezék formájában, az üldözők által nyert játékokban pedig mindig van egy optimális stratégia fabontás formájában [2] . Például, mivel egy 3 × 3 -as rácsnak van egy 4-es rendű fedője, de nincs 5-ös rendű fedője, a faszélességnek pontosan 3-mal kell egyenlőnek lennie. Ugyanez a minimax-tétel általánosítható véges faszélességű végtelen gráfokra , ha a a faszélesség meghatározása, a mögöttes fának nem kell vége lenni [2] .

A rejtekhelyek szintén szorosan kapcsolódnak az elválasztók létezéséhez , amelyek egy kis méretű X csúcskészlet egy n csúcsú gráfban , így bármely X -élnek legfeljebb 2n /3 csúcsa van. Ha a G gráfnak nincs k csúcsú elválasztója, akkor bármely legfeljebb k csúcsot tartalmazó X halmaznak van egy (egyedi) X -éle, amelynek több mint 2n /3 csúcsa van. Ebben az esetben G -nek van egy k + 1 rendű menedéke , amelyben β ( X ) egyedi nagy X - táblaként van definiálva . Vagyis minden gráfnak van vagy kis elválasztója, vagy magasrendű fedője [3] .

Ha a G gráfnak k rendű fedője van, ha k ≥ h 3/2 n 1/2 valamilyen h egész számra , akkor G - nek a teljes K h gráfnak is kisebbnek kell lennie . Más szóval, egy k fedőrendű n csúcsú gráf Hadwiger-számának értéke legalább k 2/3 n −1/3 . Következésképpen a K h molloktól mentes gráfok faszélessége kisebb, mint h 3/2 n 1/2 , és az elválasztóké h 3/2 n 1/2 -nél kisebb . Általánosabban, a faszélesség O(√ n ) korlátja és az elválasztó mérete érvényes minden olyan nem triviális gráfcsaládra, amely tiltott gráfokkal jellemezhető , mivel minden ilyen családhoz létezik h állandó , amely nem tartalmazza a családot. K h [3] .

Végtelen gráfokban

Ha egy G gráf tartalmaz egy sugarat, egy félvégtelen egyszerű utat, amelynek van kezdőcsúcsa, de nincs végcsúcsa, akkor van egy ℵ 0 rendű fedője , azaz egy β függvény, amely minden véges X csúcshalmazt leképez egy A fedezeti feltételeknek megfelelő X -board. A β ( X )-t ugyanis egyedi X -táblaként definiáljuk , amely korlátlan számú sugárcsúcsból áll. Így a végtelen gráfok esetében megszakad a kapcsolat a faszélesség és az oltalmak között – egyetlen sugárnak, annak ellenére, hogy önmagában fa, minden véges rendű menedéke van, és még erősebben egy ℵ 0 rendű menedék . Egy végtelen gráf két sugarát ekvivalensnek tekintjük, ha nincs véges csúcshalmaz, amely egy sugár végtelen számú csúcsát választja el egy másik sugár végtelen számú csúcsától. Ezt az ekvivalenciarelációt és ekvivalenciarelációit a gráf végeinek nevezzük .

Bármely gráf végpontjai egy az egyhez megfelelnek a ℵ 0 sorrendű rejtekhelyekkel . Bármely sugár meghatároz egy fedelet, és bármely két egyenértékű sugár ugyanazt a fedelet [4] . Fordítva, bármely borítást a sugarak határoznak meg oly módon, hogy az az opciók alábbi elemzésével kimutatható:

Így minden sugárekvivalencia osztály egyedi borítást definiál, és minden borítást egy sugárekvivalencia osztály határoz meg.

Bármely bíborszám esetén egy végtelen G gráfnak akkor és csak akkor van κ rendű fedője , ha van egy κ rendű klikkmoll . Ez azt jelenti, hogy megszámlálhatatlan kardinális számok esetén G-ben a legnagyobb rejtett sorrend a G gráf Hadwiger - száma [ 4] .

Jegyzetek

  1. ↑ Seymour, Thomas, 1993 .
  2. ↑ 1 2 3 4 5 6 7 Seymour és 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 Diestel, Kühn, 2003 , p. 197–206.
  6. ↑ Johnson, Robertson, Seymour, Thomas, 2001 , p. 138–155.

Irodalom