Hrabě Woodiness

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. října 2021; ověření vyžaduje 1 úpravu .

Stromovitost neorientovaného grafu je minimální počet lesů, na které lze rozložit okraje . Ekvivalentně se jedná o minimální počet kostry , které jsou potřeba k pokrytí okrajů grafu.

Příklad

Obrázek ukazuje kompletní bipartitní graf K 4,4 s rozdělením grafu do tří lesů zbarvených různými barvami. K 4,4 nelze rozdělit na méně lesů, protože každý les na osmi vrcholech má maximálně sedm hran, zatímco celý graf má šestnáct hran, což je více než dvojnásobek hran v jednom lese. Stromovitost grafu K 4,4 je tedy rovna třem.

Dřevitost jako míra hustoty

Stromovitost grafu je mírou hustoty grafu – grafy s velkým počtem hran mají vysokou stromovitost a grafy s vysokou stromovitostí musí mít husté podgrafy.

Přesněji řečeno, protože každý n -vrcholový les má nejvýše n − 1 hran, stromovost grafu s n vrcholy a m hranami je nejméně . Kromě toho podgrafy žádného grafu nemohou mít stromovost větší než je strom samotný, nebo, ekvivalentně, stromovost grafu musí být alespoň tak velká jako maximální stromovost jeho podgrafů. Nash-Williams dokázal, že tyto dvě skutečnosti lze kombinovat, aby charakterizovaly stromovost — jestliže n S respektive m S označují počet vrcholů a hran libovolného podgrafu S daného grafu, pak stromovost grafu je rovný $\lceil m/(n-1)\rceil$ $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Jakýkoli rovinný graf s vrcholy má maximum hran, z čehož vyplývá Nash-Williamsův vzorec, že stromovost rovinného grafu nepřesahuje tři. Schneider použil speciální rozklad rovinného grafu na tři lesy, nazývané Schneider forest , aby našel vložení úsečky libovolného grafu do mřížky malé oblasti. $n$ $3n-6$

Algoritmy

Stromovitost grafu lze vyjádřit jako speciální případ obecnějšího problému rozkladu matroidu , ve kterém je potřeba vyjádřit počet prvků matroidu pomocí sjednocení menšího počtu nezávislých množin . V důsledku toho lze stromovost vypočítat pomocí algoritmu s polynomiálním časem [1] .

Související pojmy

Hvězdná stromořadí grafu je velikost minimálního lesa, jehož každý strom je hvězda (strom s nejvýše jedním vrcholem, který není listem), na kterou lze rozložit okraje grafu. Pokud strom není sám o sobě hvězdou, jeho hvězdná stromovitost je dvě, což lze vidět, pokud jsou okraje rozděleny na dvě podmnožiny - s lichou a sudou vzdáleností od kořene. Hvězdná stromatost grafu tedy není menší než jeho stromatost a není větší než dvojnásobek jeho stromatosti.

Lineární stromořadí grafu je velikost minimálního lineárního lesa ( les , ve kterém všechny vrcholy spadají maximálně do dvou hran), do kterého lze rozložit okraje grafu. Lineární stromovost grafu úzce souvisí s jeho maximálním stupněm vrcholů a počtem sklonů .

Pseudostrom grafu je minimální početpseudolesů,na které lze rozložit hrany. Ekvivalentně se toto číslo rovná maximálnímu poměru hran k vrcholům v libovolném podgrafu grafu. Stejně jako u stromatosti má pseudoarborescence matroidní strukturu umožňující výpočetní efektivitu [1] .

Tloušťka grafu je minimální počet rovinných podgrafů, na které lze rozdělit hrany. Protože každý rovinný graf má stromořadí tři, tloušťka každého grafu je alespoň třetina stromatosti a nanejvýš stromeství.

Degenerace grafu je maximální počet, ve všech vygenerovaných podgrafech grafu, minimálního stupně vrcholů podgrafu. Degenerace stromového grafunení ani menšíani větší než. Číslo zbarvení grafu, známé také jako Szekeres-Wilfovo číslo [2] , se vždy rovná jeho degeneraci plus 1 [3] . $A$ $A$ $2a-1$

Mocnina grafu je zlomková hodnota, jejíž celočíselná část udává maximální počet nepřekrývajících se kostry, které lze do grafu nakreslit. Výpočet tohoto čísla je problém s balením, který je duální s problémem pokrytí vyplývajícím z problému stromečnosti.

Frakční stromatost je pokročilá stromatost definovaná pro graf jako Jinými slovy stromatost grafu je stropem frakční stromatosti. $G$ $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$

(a,b) -Rozložitelnost zobecňuje stromovost. Graf je -rozložitelný, pokud lze jeho okraje rozložit namnožiny, z nichž každá dává les, kromě jedné, která dává graf s maximálním stupněm. Stromový grafje-rozložitelný. $(a,b)$ $a+1$ $b$ $A$ ${\displaystyle(a,0)}$

Literatura

N. Alon. Lineární stromořadost grafů // Israel Journal of Mathematics . - 1988. - T. 62 , no. 3 . — S. 311–325 . - doi : 10.1007/BF02783300 .
B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. Krátký důkaz Nash-Williamsovy věty pro stromořadost grafu // Grafy a kombinatorika. - 1994. - T. 10 , no. 1 . — S. 27–28 . - doi : 10.1007/BF01202467 .
P. Erdős, A. Hajnal. O chromatickém počtu grafů a soustav množin // Acta Mathematica Hungarica . - 1966. - T. 17 , no. 1–2 . — S. 61–99 . - doi : 10.1007/BF02020444 .
HN Gabow, HH Westermann. Lesy, rámce a hry: Algoritmy pro součty a aplikace matroidů // Algorithmica . - 1992. - T. 7 , vydání. 1 . — S. 465–497 . - doi : 10.1007/BF01758774 .
S. L. Hakimi, J. Mitchem, E. E. Schmeichel. Hvězdicová stromořadost grafů // Diskrétní matematika . - 1996. - T. 149 . — S. 93–98 . - doi : 10.1016/0012-365X(94)00313-8 .
TR Jensen, B. Toft. Problémy s barvením grafů. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
c.st. JA Nash-Williams. Hranové disjunktní kostry konečných grafů // Journal of the London Mathematical Society . - 1961. - T. 36 , čís. 1 . — S. 445–450 . - doi : 10.1112/jlms/s1-36.1.445 .
c.st. JA Nash-Williams. Dekompozice konečných grafů do lesů // Journal of the London Mathematical Society . - 1964. - T. 39 , čís. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
W. Schnyder. Proč. 1. ACM/SIAM Symposium on Discrete Algorithms (SODA). - 1990. - S. 138-148.
G. Szekeres, H. S. Wilf. Nerovnice pro chromatické číslo grafu // Journal of Combinatorial Theory . - 1968. - doi : 10.1016/s0021-9800(68)80081-x .
WT Tutte. K problému rozkladu grafu na n spojených faktorů // Journal of the London Mathematical Society . - 1961. - T. 36 , čís. 1 . — S. 221–230 . - doi : 10.1112/jlms/s1-36.1.221 .