Arboricitás

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf arboricitása alatt az erdők minimális számát értjük, amire a gráf élei felbonthatók. Ezzel egyenértékű megfogalmazás szerint, a minimális számú feszítőerdő, ami lefedi a gráf összes élét.

Példa

A K_4,4 teljes páros gráf felbontása három erdőre; a gráf arboricitása tehát 3.

Az ábrán látható K_4,4 teljes páros gráf színezése megmutatja éleinek három erdőre való felbontását. A K_4,4 kevesebb erdőre nem bontható föl, hiszen bármely, nyolc csúcsú erdő legfeljebb hét éllel rendelkezhet, míg a szóban forgó gráfnak tizenhat éle van, ami több mint duplája. Ezért a K_4,4 arboricitása három.

Arboricitás a sűrűség mértékeként

Egy gráf arboricitása a gráf sűrűségére jellemző: a sok éllel rendelkező gráfoknak magas az arboricitása, és a magas arboricitású gráfoknak rendelkezniük kell sűrű részgráffal.

Mivel tetszőleges n-csúcsú erdőnek legfeljebb n−1 éle lehet, ezért elmondható, hogy az n csúccsal és m éllel rendelkező gráf arboricitása legalább $\lceil m/(n-1)\rceil$. Ráadásul a gráf részgráfjainak arboricitása nem lehet magasabb magának a gráfnak az arboricitásánál, vagy másképp megfogalmazva, a gráf arboricitása legalább akkora, mint részgráfjainak maximális arboricitása. Crispin Nash-Williams bizonyítása szerint a két állítás kombinálásával lehetséges az arboricitás karakterizálása: ha a gráf bármely S részgráfjának csúcsait, illetve éleit n_S-sel, illetve m_S-sel jelöljük, akkor a gráf arboricitása pontosan $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Egy $n$ csúcsú síkbarajzolható gráf éleinek száma nem haladhatja meg a $3n-6$-ot, amiből Nash-Williams képlete alapján következik, hogy arboricitásuk legfeljebb 3 lehet. Schnyder a síkbarajzolható gráfok speciális, három erdőre történő felbontását Schnyder wood-nak nevezte el; a felbontás célja a síkbarajzolható gráf kis területű háromszögrácsba történő, egyenes vonalú lerajzolása volt.

Algoritmusok

Egy gráf arboricitása felfogható az általánosabb matroidfelbontás-probléma speciális eseteként; ott egy matroid elemeinek egy halmazát kívánjuk kifejezni kisebb független halmazok uniójaként. Ennek következményeként az arboricitás polinom idejű algoritmussal számítható (Gabow & Westermann 1992) alapján.

Kapcsolódó fogalmak

Egy gráf anarboricitása (az arboricitás invariáns párja) alatt azon nem-aciklikus részgráfok maximális számát értjük, melyekre a gráf élei felbonthatók.

Egy gráf csillagarboricitása azon erdők minimális száma, melyekbe a gráf élei felbonthatók, ha előírjuk, hogy az erdő minden fája csillag kell legyen. Ha egy fagráf nem csillag, akkor csillagarboricitása kettő, ami belátható a fa éleinek kettéosztásával a fa gyökerétől páros, illetve páratlan távolságra lévő élekre. Tehát egy gráf csillagarboricitása minimum az arboricitással, maximálisan az arboricitás kétszeresével egyezik meg.

Egy gráf lineáris arboricitása azon lineáris erdők (diszjunkt útgráfok uniója) minimális száma, melyekbe a gráf élei felbonthatók. A lineáris arboricitás szorosan kapcsolódik a gráf maximális fokszámához és lejtőszámához.

Egy gráf pszeudoarboricitása azon pszeudoerdők (összefüggő komponensenként legfeljebb egy kört tartalmazó gráfok) minimális száma, melyekbe a gráf élei felbonthatók. Ezzel egyenértékű megfogalmazás szerint a gráf összes részgráfjában az élek és csúcsok számának arányai közül a maximálisnak egész számra felkerekített értéke. Az arboricitáshoz hasonlóan a pszeudoarboricitás is rendelkezik a hatékony kiszámítást lehetővé tevő matroidszerkezettel (Gabow & Westermann 1992).

Egy gráf vastagsága azon rész-síkgráfok minimális száma, melyekbe a gráf élei felbonthatók. Mivel a síkgráfok arboricitása legfeljebb három lehet, egy gráf vastagsága legalább az arboricitás harmadával, legfeljebb pedig az arboricitás értékével egyezik meg.

Egy gráf degeneráltsága a gráf összes feszített részgráfjainak minimális fokszámú csúcsai közül kiválasztott maximális fokszámmal egyezik meg. Az $a$ arboricitású gráf degeneráltsága legalább $a$-val, legfeljebb pedig $2a-1$-gyel egyezik meg. A gráf színezési száma vagy Szekeres–Wilf-száma (Szekeres & Wilf 1968) mindig eggyel nagyobb a degeneráltságánál (Jensen & Toft 1995, p. 77f.).

Egy gráf erőssége egy arányszám, melynek egészrésze megadja a gráfba rajzolható diszjunkt feszítőfák maximális számát. Ez egy pakolási probléma, ami az arboricitás fedési problémájának duálisa. A két paramétert Tutte és Nash-Williams közösen tanulmányozták.

A tört arboricitás vagy frakcionális arboricitás az arboricitás fogalmának finomítása. Definíciója szerint a $G$ gráf tört arboricitása $\max\{m_{S}/(n_{S}-1)|S\subseteq G\}.$ Más megfogalmazásban a gráf arboricitása a tört arboricitásának felső egészrésze.

Az (a, b)-felbonthatóság az arboricitás fogalmának általánosítása. Egy gráf akkor $(a,b)$-felbontható, ha éleinek szétoszthatók $a+1$ halmazba oly módon, hogy mindegyik egy erdőt feszít ki, kivéve egyet, mely egy $b$ maximális fokszámú gráfot. Egy $a$ arboricitású gráf $(a,0)$-felbontható.

Egy gráf fa-száma megegyezik a gráf éleit lefedő fák minimális számával.

Fordítás

• Ez a szócikk részben vagy egészben az Arboricity című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Alon, N. (1988). „The linear arboricity of graphs”. Israel Journal of Mathematics 62 (3), 311–325. o. DOI:10.1007/BF02783300.  
• (1994) „A short proof of Nash-Williams' theorem for the arboricity of a graph”. Graphs and Combinatorics 10 (1), 27–28. o. DOI:10.1007/BF01202467.  
• (1966) „On chromatic number of graphs and set-systems”. Acta Mathematica Hungarica 17 (1–2), 61–99. o. [2013. május 24-i dátummal az eredetiből archiválva]. DOI:10.1007/BF02020444. (Hozzáférés: 2017. szeptember 24.)  
• (1992) „Forests, frames, and games: Algorithms for matroid sums and applications”. Algorithmica 7 (1), 465–497. o. DOI:10.1007/BF01758774.  
• (1996) „Star arboricity of graphs”. Discrete Mathematics 149, 93–98. o. DOI:10.1016/0012-365X(94)00313-8.  
• Graph Coloring Problems. New York: Wiley-Interscience (1995). ISBN 0-471-02865-7 
• C. St. J. A. Nash-Williams (1961). „Edge-disjoint spanning trees of finite graphs”. Journal of the London Mathematical Society 36 (1), 445–450. o. 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. o. DOI:10.1112/jlms/s1-39.1.12.  
• W. Schnyder (1990). „Embedding planar graphs on the grid”. Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA): 138–148. 
• (1968) „An inequality for the chromatic number of a graph”. Journal of Combinatorial Theory. DOI:10.1016/s0021-9800(68)80081-x.  
• 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. o. DOI:10.1112/jlms/s1-36.1.221.