Арборицитет

Арборицитет неусмереног графа је минималан број Шума у којима се налазе гране графа. Еквивалентно је минималаном броју разапињућих шума потребних да се обухвате све гране графа.

Пример

Подела комплетног бипартитног графаK_4,4 у три шуме, што показује да је арборицитет графа три.

Слика приказује комплетни бипартитни граф K_4,4, са бојама које показују поделу грана у три шуме. K_4,4 не могу бити подељене у мање шуме, јер свака шума, на осам чворова, има највише седам грана, док је граф има укупно шеснаест грана, дупло већи број грана у једној шуми. Дакле, арборицитет K_4,4 је три.

Арборицитет као мера густине

Арборицитет графа је мера која даје информцију о густини графа: графови са више грана имају висок арборицитет, и графови са високим арборицитетом морају имати густ подграф.

Детаљније, као и свака n-степена шума има највише n-1 грану, арборицитет графа са n чворова и m грана је најмање $\lceil m/(n-1)\rceil$ . Поред тога, подграф било ког графа не може имати арборицитет већи од самог графа, илити; арборицитет графа мора бити најмање максимални арборицитет било ког његовог подграфа. Nash-Williams је доказао да ове две чињенице могу да се комбинују чиме окарактеришу арборицитет: ако узмемо да n_S и m_S означавају број чворова и грана, респективно, једног подграфа S , задатог графа, онда арборицитет графа износи $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Сваки планарни граф са $n$ чворова има највише $3n-6$, из чега следи по формули Nash-Williams-a, да планарни графови имају арборицитет највише три. Schnyder је користио посебно разлагање планарног графа у три шуме : Schnyder-ово дрво да пронађе праволинијско уграђивање једног планарног графа у мрежу у малом простору.

Алгоритам

Арборицитет графа се може изразити као посебан случај општије матроидне поделе проблема, у коме се изражава скуп елемената матроид као заједница малог броја независних скупова. Као последица тога, арборицити може се израчунати полинома-алгоритам .

Сродни концепти

Арборицитет-звезда графа је величина минималне шуме, код које је свако стабло Звезда (стабло са највише једним чвором без листове), у који гране графа могу бити подељене. Ако дрво није звезда, њен арборицитет-звезда је два, што се може видети поделом грана у две подгрупе : парних и непарних растојањима од корена стабла, респективно. Дакле, арборицитет-звезда једног графа је барем једнак арборицитет-у, а максимално једнак двоструком арборицитет-у.

Линеарни арборицитет графа је величина минималне линеарне шуме (шума у којој су сви чворови инцидентни са највише две гране) у којој могу да се налазе гране графа. Линеарни арборицитет графа је уско повезан са максималним степеном графа и његовим нагибним бројем.

Псеудоарборицитет графа је минималан број псеудошума у којима су његове гране постављене. Еквивалентно, то је максимални однос грана и чворова из било ког подграфа. Као и код арборицитета, псеудоарборицитет има матроидну структуру што омогућава да се ефикасно израчунава .

Дебљина графа је минималан број планарних подграфа који могу да садрже гране графа. Као и сваки, планарни граф има арборицитет три, дебљина једног графа је најмање једнака трећини арборицитета, а највише једнака арборицитету.

Дегенерација графа је максимум, свих индукованих подграфа графа, са најмањим степеном чворова у подграфу. Дегенерација графа са арборицитетом $a$ је најмање једнака $a$ а највише једнака $2a-1$. Број бојења графа, такође познат као Szekeres-Wilf-ов број .

Снага графа је фракциона вредност чији цео део даје максималан број дисјунктних разапињућих стабала, која се могу уцртати на графу. То је проблем паковања који је дуалан проблему покривања вођен арборицитетом. Ова два параметра су заједно изучавали Tutte, W. T. и Nash-Williams.

Литература

• 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. Архивирано из оригинала (PDF) 24. 5. 2013. г. Приступљено 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). стр. 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.