Mělké menší - Shallow minor

v teorie grafů, a mělký menší nebo omezená hloubka menší je omezená forma a graf minor ve kterém podgrafy, které jsou smluvně tvořeny nezletilými, jsou malé průměr. Mělké nezletilé byly představeny Plotkin, Rao & Smith (1994), kteří připsali svůj vynález Charles E. Leiserson a Sivan Toledo.[1]

Definice

Graf, který má kompletní graf K.4 jako 1-mělký nezletilý. Každá ze čtyř podskupin vrcholů označených čárkovanými obdélníky indukuje připojený podgraf s poloměrem jedna a mezi každou dvojicí podskupin existuje hrana.

Jeden způsob, jak definovat menší část neorientovaného grafu G je zadáním podgrafu H z Ga kolekce nesouvislých podmnožin Si vrcholů G, z nichž každá tvoří a připojeno indukovaný podgraf Hi z H. Menší má vrchol protii pro každou podmnožinu Sia okraj protiiprotij kdykoli existuje hrana z Si na Sj kterému patří H.

V této formulaci a d-shallow minor (alternativně nazývaný mělký minor hloubky d) je nezletilý, který lze definovat tak, že každý z podgrafů Hi má poloměr nejvíce d, což znamená, že obsahuje centrální vrchol Ci to je na dálku d všech ostatních vrcholů Hi. Všimněte si, že tato vzdálenost se měří počtem hopů v Hi, a proto může být větší než vzdálenost v G.[1]

Speciální případy

Mělké nezletilé osoby s nulovou hloubkou jsou to samé jako podgrafy daného grafu. Pro dostatečně velké hodnoty d (včetně všech hodnot, které jsou alespoň tak velké jako počet vrcholů), d- mělké nezletilé daného grafu se shodují se všemi jeho nezletilými.[1]

Klasifikace rodin grafů

Nešetřil & Ossona de Mendez (2012) použijte mělké nezletilé k rozdělení rodin konečných grafů do dvou typů. Říkají, že rodina grafů F je někde hustý pokud existuje konečná hodnota d pro které d- mělké nezletilé grafy v F skládají se z každého konečného grafu. Jinak říkají, že rodina grafů je nikde hustá.[2] Tato terminologie je odůvodněna skutečností, že pokud F je nikde hustá třída grafů, pak (pro každé ε> 0) n-vertexové grafy v F mít Ó(n1 + ε) hrany; tudíž nikde nejsou husté grafy řídké grafy.[3]

Přísnějším typem rodiny grafů, popsaným podobně, jsou rodiny grafů ohraničená expanze. Jedná se o rodiny grafů, pro které existuje funkce F tak, že poměr hran k vrcholům v každém d-mělká menší je nanejvýš F(d).[4] Pokud tato funkce existuje a je ohraničena a polynomiální, říká se, že rodina grafů má polynomiální expanzi.

Věty o oddělovačích

Tak jako Plotkin, Rao & Smith (1994) ukázáno, grafy s vyloučenými mělkými nezletilými lze rozdělit analogicky k věta o planárním oddělovači pro rovinné grafy. Zejména pokud je kompletní graf K.h není d-mělká menší z n-vrcholový graf G, pak existuje podmnožina S z G, s velikostí Ó(dh2 logn + n/d), takže každá připojená součást z G\S má maximálně 2n/ 3 vrcholy. Výsledek je konstruktivní: existuje polynomiální časový algoritmus, který buď najde takový oddělovač, nebo d-mělký K.h Méně důležitý.[5]V důsledku toho ukázali, že každá rodina menších uzavřených grafů se řídí oddělovací teorémou téměř tak silnou jako ta pro rovinné grafy.

Plotkin et al. také použil tento výsledek na rozdělení Metoda konečných prvků oka ve vyšších rozměrech; pro toto zobecnění jsou nutné mělké nezletilé, protože (bez omezení hloubky) má rodina sítí ve třech nebo více rozměrech všechny grafy jako nezletilé. Teng (1998) rozšiřuje tyto výsledky o širší třídu výškových grafů.

Obecněji řečeno, dědičná rodina grafů má teorém o oddělovači, kde je velikost oddělovače sublearní silou n právě když má polynomiální expanzi.[6]

Poznámky

  1. ^ A b C Nešetřil & Ossona de Mendez (2012), Oddíl 4.2 „Mělké nezletilé“, s. 62–65.
  2. ^ Nešetřil & Ossona de Mendez (2012), oddíl 5.3 „Klasifikace tříd nezletilými kliky“, s. 100–102.
  3. ^ Nešetřil & Ossona de Mendez (2012), Věta 5.3, s. 100.
  4. ^ Nešetřil & Ossona de Mendez (2012), Oddíl 5.5 „Třídy s ohraničenou expanzí“, s. 104–107.
  5. ^ Algoritmus Plotkin et al. vyžaduje čas Ó(mn/d), kde m je počet hran na vstupu. Wulff-Nilsen (2011) vylepšil to pro neřídké grafy na Ó(m + n2 + ε/d).
  6. ^ Dvořák & Norin (2015).

Reference

  • Dvořák, Zdeněk; Norin, Sergey (2015), Silně podmořské oddělovače a polynomiální expanze, arXiv:1504.04821, Bibcode:2015arXiv150404821D.
  • Plotkin, Serge; Rao, satish; Smith, Warren D. (1994), „Mělké vyloučené nezletilé a vylepšené rozklady grafů“, Proc. 5. ACM-SIAM Symp. na diskrétních algoritmech (SODA), str. 462–470.
  • Teng, Shang-Hua (1998), „Kombinatorické aspekty geometrických grafů“, Comput. Geom., 9 (4): 277–287, doi:10.1016 / S0925-7721 (96) 00008-9, PAN  1609578.
  • Wulff-Nilsen, Christian (2011), „Věty o oddělovačích pro méně významné a mělké menší volné grafy s aplikacemi“, Proc. 52. IEEE Symp. Základy informatiky (FOCS), str. 37–46, arXiv:1107.1292, doi:10.1109 / FOCS.2011.15.
  • Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28Springer, doi:10.1007/978-3-642-27875-4, ISBN  978-3-642-27874-7, PAN  2920058.