Arboricitet

Arboricitet neusmerenog grafa je minimalan broj Šuma u kojima se nalaze grane grafa. Ekvivalentno je minimalanom broju razapinjućih šuma potrebnih da se obuhvate sve grane grafa.

Primer

Podela kompletnog bipartitnog grafaK_4,4 u tri šume, što pokazuje da je arboricitet grafa tri.

Slika prikazuje kompletni bipartitni graf K_4,4, sa bojama koje pokazuju podelu grana u tri šume. K_4,4 ne mogu biti podeljene u manje šume, jer svaka šuma, na osam čvorova, ima najviše sedam grana, dok je graf ima ukupno šesnaest grana, duplo veći broj grana u jednoj šumi. Dakle, arboricitet K_4,4 je tri.

Arboricitet kao mera gustine

Arboricitet grafa je mera koja daje informciju o gustini grafa: grafovi sa više grana imaju visok arboricitet, i grafovi sa visokim arboricitetom moraju imati gust podgraf.

Detaljnije, kao i svaka n-stepena šuma ima najviše n-1 granu, arboricitet grafa sa n čvorova i m grana je najmanje $\lceil m/(n-1)\rceil$ . Pored toga, podgraf bilo kog grafa ne može imati arboricitet veći od samog grafa, iliti; arboricitet grafa mora biti najmanje maksimalni arboricitet bilo kog njegovog podgrafa. Nash-Williams je dokazao da ove dve činjenice mogu da se kombinuju čime okarakterišu arboricitet: ako uzmemo da n_S i m_S označavaju broj čvorova i grana, jednog podgrafa S , zadatog grafa, onda arboricitet grafa iznosi $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Svaki planarni graf sa $n$ čvorova ima najviše $3n-6$, iz čega sledi po formuli Nash-Williams-a, da planarni grafovi imaju arboricitet najviše tri. Schnyder je koristio posebno razlaganje planarnog grafa u tri šume : Schnyder-ovo drvo da pronađe pravolinijsko ugrađivanje jednog planarnog grafa u mrežu u malom prostoru.

Algoritam

Arboricitet grafa se može izraziti kao poseban slučaj opštije matroidne podele problema, u kome se izražava skup elemenata matroid kao zajednica malog broja nezavisnih skupova. Kao posledica toga, arboriciti može se izračunati polinoma-algoritam.

Srodni koncepti

Arboricitet-zvezda grafa je veličina minimalne šume, kod koje je svako stablo Zvezda (stablo sa najviše jednim čvorom bez listove), u koji grane grafa mogu biti podeljene. Ako drvo nije zvezda, njen arboricitet-zvezda je dva, što se može videti podelom grana u dve podgrupe : parnih i neparnih rastojanjima od korena stabla. Dakle, arboricitet-zvezda jednog grafa je barem jednak arboricitet-u, a maksimalno jednak dvostrukom arboricitet-u.

Linearni arboricitet grafa je veličina minimalne linearne šume (šuma u kojoj su svi čvorovi incidentni sa najviše dve grane) u kojoj mogu da se nalaze grane grafa. Linearni arboricitet grafa je usko povezan sa maksimalnim stepenom grafa i njegovim nagibnim brojem.

Pseudoarboricitet grafa je minimalan broj pseudošuma u kojima su njegove grane postavljene. Ekvivalentno, to je maksimalni odnos grana i čvorova iz bilo kog podgrafa. Kao i kod arboriciteta, pseudoarboricitet ima matroidnu strukturu što omogućava da se efikasno izračunava.

Debljina grafa je minimalan broj planarnih podgrafa koji mogu da sadrže grane grafa. Kao i svaki, planarni graf ima arboricitet tri, debljina jednog grafa je najmanje jednaka trećini arboriciteta, a najviše jednaka arboricitetu.

Degeneracija grafa je maksimum, svih indukovanih podgrafa grafa, sa najmanjim stepenom čvorova u podgrafu. Degeneracija grafa sa arboricitetom $a$ je najmanje jednaka $a$ a najviše jednaka $2a-1$. Broj bojenja grafa, takođe poznat kao Szekeres-Wilf-ov broj .

Snaga grafa je frakciona vrednost čiji ceo deo daje maksimalan broj disjunktnih razapinjućih stabala, koja se mogu ucrtati na grafu. To je problem pakovanja koji je dualan problemu pokrivanja vođen arboricitetom. Ova dva parametra su zajedno izučavali Tutte, W. T. i Nash-Williams.

Literatura

• Alon, N. (1988). „The linear arboricity of graphs”. Israel Journal of Mathematics. 62 (3): 311—325. MR 0955135. doi:10.1007/BF02783300. 
• Chen, B.; Matsumoto, M.; Wang, J.; Zhang, Z.; Zhang, J. (1994). „A short proof of Nash-Williams' theorem for the arboricity of a graph”. Graphs and Combinatorics. 10 (1): 27—28. MR 1273008. doi:10.1007/BF01202467. 
• Erdős, P.; Hajnal, A. (1966). „On chromatic number of graphs and set-systems” (PDF). Acta Mathematica Hungarica. 17 (1–2): 61—99. MR 0193025. doi:10.1007/BF02020444. Arhivirano iz originala (PDF) 24. 5. 2013. g. Pristupljeno 29. 5. 2013. 
• Gabow, H. N.; Westermann, H. H. (1992). „Forests, frames, and games: Algorithms for matroid sums and applications”. Algorithmica. 7 (1): 465—497. MR 1154585. doi:10.1007/BF01758774. 
• Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996). „Star arboricity of graphs”. Discrete Mathematics. 149: 93—98. MR 1375101. doi:10.1016/0012-365X(94)00313-8. 
• Jensen, T. R.; Toft, B. (1995). Graph Coloring Problems. New York: Wiley-Interscience. ISBN 978-0-471-02865-9. MR 1304254. 
• C. St. J. A. Nash-Williams (1961). „Edge-disjoint spanning trees of finite graphs”. Journal of the London Mathematical Society. 36 (1): 445—450. MR 0133253. doi:10.1112/jlms/s1-36.1.445. 
• C. St. J. A. Nash-Williams (1964). „Decomposition of finite graphs into forests”. Journal of the London Mathematical Society. 39 (1): 12. MR 0161333. doi:10.1112/jlms/s1-39.1.12. 
• Schnyder, W. (1990). „Embedding planar graphs on the grid”. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). str. 138—148. 
• Szekeres, G.; Wilf, H. S. (1968). „An inequality for the chromatic number of a graph”. Journal of Combinatorial Theory. MR 0218269. 
• Tutte, W. T. (1961). „On the problem of decomposing a graph into n connected factors”. Journal of the London Mathematical Society. 36 (1): 221—230. MR 0140438. doi:10.1112/jlms/s1-36.1.221.