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.

Definíció

Az itt látható gráf 1-sekély minora a K₄ teljes gráf. A szaggatott téglalapok által kijelölt négy csúcs-részhalmaz mindegyike egy összefüggő, 1 sugarú részgráfot feszít ki, és bármely két részhalmaz között húzódik él.

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 S_i részhalmazainak olyan gyűjteményét, melyek mindegyike H-beli H_i összefüggő feszített részgráfot alkot. A minor egy-egy v_i csúccsal rendelkezik minden S_i részhalmazhoz, és a v_iv_j él akkor létezik, ha van olyan él az S_i és az S_j 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 H_i részgráfok mindegyikének a sugara legfeljebb d, tehát tartalmaz olyan központi helyzetű c_i csúcsot, ami H_i többi csúcsától legfeljebb d távolságra van. Vegyük észre, hogy a távolság a H_i-beli lépések számát méri, ezért nagyobb lehet a G-beli távolságnál.

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

(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). 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(n^1 + ε) éllel rendelkeznek; tehát a sehol sem sűrű gráfok ritka gráfok.

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). 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 (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 K_h teljes gráf nem d-sekély minora egy n-csúcsú G gráfnak, akkor létezik G-nek O(dh² 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 K_h minort. 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.

Fordítá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

• 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.