Blackberry (teorie grafů)

V teorii grafů je ostružina pro neorientovaný graf G rodina spojených podgrafů grafu G , které se vzájemně dotýkají: pro každou dvojici podgrafů, které nemají společné vrcholy, musí existovat hrana, jejíž koncové vrcholy leží v těchto dvou podgrafy. Řád ostružiny je nejmenší velikost množiny vrcholů G , která má neprázdný průsečík s každým podgrafem ostružiny. Ostružiny se používají k popisu šířky stromu grafu G [1] .

Šířka dřeva a kryt

Krytí řádu k v grafu G je funkce β , která vezme každou množinu X s méně než k vrcholy do spojené složky G − X tak , že se libovolné dvě podmnožiny β ( X ) a β ( Y ) navzájem dotýkají . To znamená, že obrazy β tvoří ostružinu s řádem k v G . Naopak pro vytvoření úkrytu lze použít jakoukoli ostružinu — pro každou množinu X menší, než je řád ostružiníku, existuje jedna spojená složka β ( X ) obsahující všechny podgrafy v ostružině, které nejsou spojeny s X .

Jak ukázali Seymour a Thomas , řád ostružiny (nebo ekvivalentně úkryt) popisuje šířku stromu — graf má ostružinu řádu k právě tehdy, když je šířka stromu alespoň k − 1 [1] .

Velikost ostružin

Jak poznamenali Grohe a Marx, expandéry ohraničených stupňů mají šířku stromu úměrnou počtu vrcholů, a aby zahrnovaly všechny podgrafy, které nesdílejí vrcholy s každou podmnožinou této velikosti, ostružina pro takové grafy musí obsahovat exponenciálně mnoho různých podgrafů. Přesněji řečeno, pro tyto grafy i ty ostružiny, jejichž řád je o něco větší než druhá odmocnina šířky stromu, musí mít exponenciální velikost. Groh a Marx však také ukázali, že každý graf se šířkou stromu k má ostružiní polynomiální velikosti a řádu [2] . $\Omega (k^{1/2}/\log ^{2}k)$

Výpočetní složitost

Protože ostružiní může mít exponenciální velikost, není vždy možné je sestrojit v polynomiálním čase pro grafy s neomezenou šířkou stromu. Pokud je však šířka stromu omezená, je možná doba výstavby polynomu - je možné najít ostružinu řádu k , pokud existuje, v čase , kde n je počet vrcholů v grafu. Pro grafy s malým počtem minimálních oddělovačů jsou možné ještě rychlejší algoritmy [3] . $O(n^{k+2})$

Bodlender, Grigoriev a Coster [4] studovali heuristické algoritmy pro hledání ostružin vysokého řádu. Jejich metody ne vždy dávaly ostružiny s řádem blízkým šířce stromu, ale pro rovinné grafy dávají konstantní aproximační faktor . Kreutzer a Tazari [5] navrhují polynomiálně-časové pravděpodobnostní vyhledávací algoritmy na grafech s stromořadím k ostružiní polynomiální velikosti a řádu , což odpovídá faktoru logaritmického uspořádání odvozenému Grohe a Marxem ( Grohe, Marx 2009 ) pro existenci ostružiní polynomu. velikost. $\Omega (k^{1/2}/\log ^{3}k)$

Odkazy

↑ 1 2 Paul D. Seymour, Robin Thomas. Prohledávání grafů a věta min-max pro šířku stromu // Journal of Combinatorial Theory . - 1993. - T. 58 , no. 1 . — S. 22–33 . - doi : 10.1006/jctb.1993.1027 . . V tomto článku se ostružiny nazývají "síta" a jejich objednávky se nazývají "tloušťka".
↑ Martin Grohe, Daniel Marx. O šířce stromu, velikosti ostružiní a expanzi // Journal of Combinatorial Theory . - 2009. - T. 99 , č.p. 1 . — S. 218–228 . - doi : 10.1016/j.jctb.2008.06.004 . .
↑ Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Matematické základy informatiky 2009: 34. mezinárodní sympozium, MFCS 2009, Nový Smokovec, Vysoké Tatry, Slovensko, 24.-28. srpna 2009, sborník příspěvků. - Berlín: Springer, 2009. - T. 5734. - S. 223-234. - doi : 10.1007/978-3-642-03816-7_20 . .
↑ Bodlaender. Dolní hranice šířky stromu s ostružiníky. — Algorithmica . - 2008. - T. 51. - S. 81–98. - doi : 10.1007/s00453-007-9056-z . .
↑ Stephan Kreutzer, Siamak Tazari. Sborník příspěvků z 21. výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA '10). - 2010. - S. 354-364. .