A matematika, azon belül a gráfelmélet területén egy sekély minor vagy korlátos mélységű minor (shallow minor, limited-depth minor) a gráfminorok olyan, korlátozottabb változata, ahol a részgráfok, amelyekből a minort összehúzzuk, kis átmérővel rendelkeznek. A sekély minorokat vezették be, akik az elsőbbséget Charles E. Leisersonnak és Sivan Toledónak tulajdonítják.

Definíció

Egy irányítatlan G gráf egy minora például a következőképpen definiálható: adjuk meg G egy részgráfját, H-t és G csúcsai diszjunkt Si részhalmazainak olyan gyűjteményét, melyek mindegyike H-beli Hi összefüggő feszített részgráfot alkot. A minor egy-egy vi csúccsal rendelkezik minden Si részhalmazhoz, és a vivj él akkor létezik, ha van olyan él az Si és az Sj között, ami H-ba tartozik.

Ebben a megfogalmazásban egy d-sekély minor (vagy d mélységű sekély minor) olyan minor, ami előállítható úgy, hogy a Hi részgráfok mindegyikének a sugara legfeljebb d, tehát tartalmaz olyan központi helyzetű ci csúcsot, ami Hi többi csúcsától legfeljebb d távolságra van. Vegyük észre, hogy a távolság a Hi-beli lépések számát méri, ezért nagyobb lehet a G-beli távolságnál., Section 4.2 "Shallow Minors", pp. 62–65.

Speciális esetek A nulla mélységű minorok az adott gráf részgráfjaival egyeznek meg. Elegendően nagy d értékre (ideértve azt is, ha az érték eléri a csúcsok számát), adott gráf d-sekély minorai egybeesnek az összes minorával.

Gráfcsaládok osztályozása a korlátos mélységű minorok segítségével a véges gráfok családjait két típusra osztják fel. Egy F gráfcsaládot akkor neveznek valahol sűrűnek (somewhere dense), ha létezik olyan véges d érték, amire az F család d-sekély minorai az összes véges gráfot tartalmazzák. Egyébként a gráfcsalád sehol sem sűrű (nowhere dense)., section 5.3 "Classification of Classes by Clique Minors", pp. 100–102. Ezt a terminológiát igazolja az a tény, hogy ha F gráfok sehol sem sűrű családja, akkor (minden ε > 0 esetben) az F-beli n-csúcsú gráfok O(n1 + ε) éllel rendelkeznek; tehát a sehol sem sűrű gráfok ritka gráfok., Theorem 5.3, p. 100.

Hasonló módon, de szigorúbban meghatározott gráfcsaládok a korlátos expanziójú gráfok családjai. Ezek a gráfcsaládok, melyekhez létezik olyan f függvény, melyre minden d-sekély minorban az élek és csúcsok aránya legfeljebb f(d)., Section 5.5 "Classes with Bounded Expansion", pp. 104–107. Ha ez a függvény létezik és egy polinom felső korlátját képezi, akkor a gráfcsalád polinom expanziójú.

Szeparátortételek Ahogy megmutatták, a sekély minorok nélküli gráfok a síkbarajzolható gráfok síkgráf-felbontási tételével analóg módon particionálhatók. Konkrét példát tekintve, ha a Kh teljes gráf nem d-sekély minora egy n-csúcsú G gráfnak, akkor létezik G-nek O(dh2 log n + n/d) méretű S részhalmaza, melyre igaz, hogy G\S minden összefüggő komponense legfeljebb 2n/3 csúccsal rendelkezik. Ez az eredmény konstruktív: létezik olyan polinom idejű algoritmus, ami vagy ilyen szeparátort talál, vagy egy d-sekély Kh minort.Plotkin et al. algoritmusa O(mn/d) időben fut le, ahol m a bemenet éleinek száma. ezt nem ritka gráfok esetében O(m + n2 + ε/d)-re javították. Ennek eredményeként kimutatták, hogy minden minorzárt gráfcsaládhoz csaknem olyan erős szeparátortétel tartozik, mint a síkbarajzolható gráfoké.

Plotkin et al. ezt az eredményt felhasználták a végeselemes módszer magasabb dimenziójú rácsainak particionálására is; ebben az általánosításban a korlátos mélységű minorok azért szükségesek, mert (a mélység megszorítása nélkül) a három vagy többdimenziós rácsok családja az összes gráfot tartalmazza minorként. magas dimenziószámú gráfok szélesebb osztályára terjeszti ki ezeket az eredményeket.

Általánosabban, egy örökletes gráfcsalád pontosan akkor rendelkezik szeparátortétellel, amiben a szeparátor mérete n szublineáris hatványa, ha van polinom expanziója.

Fordítás

Jegyzetek

. . . . .

Kategória:Gráfminorok