Sekély minor
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 (Plotkin, Rao & Smith 1994) vezették be, akik az elsőbbséget Charles E. Leisersonnak és Sivan Toledónak tulajdonítják.[1]
Definíció
[szerkesztés]
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.[1]
Speciális esetek
[szerkesztés]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.[1]
Gráfcsaládok osztályozása
[szerkesztés](Nešetřil & Ossona de Mendez 2012) 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).[2] 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.[3]
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).[4] 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
[szerkesztés]Ahogy (Plotkin, Rao & Smith 1994) 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.[5] 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. (Teng 1998) 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.[6]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Shallow minor című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ a b c (Nešetřil & Ossona de Mendez 2012), Section 4.2 "Shallow Minors", pp. 62–65.
- ↑ (Nešetřil & Ossona de Mendez 2012), section 5.3 "Classification of Classes by Clique Minors", pp. 100–102.
- ↑ (Nešetřil & Ossona de Mendez 2012), Theorem 5.3, p. 100.
- ↑ (Nešetřil & Ossona de Mendez 2012), Section 5.5 "Classes with Bounded Expansion", pp. 104–107.
- ↑ Plotkin et al. algoritmusa O(mn/d) időben fut le, ahol m a bemenet éleinek száma. (Wulff-Nilsen 2011) ezt nem ritka gráfok esetében O(m + n2 + ε/d)-re javították.
- ↑ Dvořák & Norin (2015).
- Dvořák, Zdeněk & Norin, Sergey (2015), Strongly sublinear separators and polynomial expansion.
- Plotkin, Serge; Rao, Satish & Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 462–470, <http://www.stanford.edu/~plotkin/lminors.ps>.
- Teng, Shang-Hua (1998), "Combinatorial aspects of geometric graphs", Comput. Geom. 9 (4): 277–287, DOI 10.1016/S0925-7721(96)00008-9.
- Wulff-Nilsen, Christian (2011), "Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications", Proc. 52nd IEEE Symp. Foundations of Computer Science (FOCS), pp. 37–46, DOI 10.1109/FOCS.2011.15.
- Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Springer, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.