Woodiness gróf

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 10-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Egy irányítatlan gráf fássága az erdők minimális száma , amelyre az éleket fel lehet bontani . Ezzel egyenértékűen ez a minimális számú feszítőfák , amelyek szükségesek a gráf éleinek lefedéséhez.

Példa

Az ábrán egy teljes kétoldalú K 4,4 gráf látható, a gráf három különböző színű erdőre osztva. A K 4,4 nem bontható fel kevesebb erdőre, hiszen nyolc csúcson lévő bármely erdőnek maximum hét éle van, míg a teljes gráfnak tizenhat éle van, ami több mint kétszerese egy erdő éleinek számának. Így a K 4,4 gráf fássága hárommal egyenlő.

A fásodás mint a sűrűség mértéke

A gráf faszerűsége a gráf sűrűségének mértéke – a nagy számú élű gráfok favonalassága magas, a nagy favonalú gráfoknak pedig sűrű részgráfokkal kell rendelkezniük.

Pontosabban, mivel bármely n csúcsú erdőnek legfeljebb n − 1 éle van, egy n csúcsú és m élű gráf faszerűsége legalább . Ezen túlmenően egyetlen gráf részgráfjainak sem lehet nagyobb fasága, mint magának a gráfnak, vagy ennek megfelelően a gráf fásságának legalább akkorának kell lennie, mint részgráfjainak maximális faértéke. Nash-Williams bebizonyította, hogy ez a két tény kombinálható a fásság jellemzésére – ha n S és m S jelöli egy adott gráf tetszőleges S részgráfjának csúcsainak és éleinek számát , akkor a gráf fásságát. egyenlő $\lceil m/(n-1)\rceil$ $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Minden csúcsokkal rendelkező síkgráfnak maximum éle van, amiből a Nash-Williams képletből következik, hogy egy síkgráf fássága nem haladja meg a hármat. Schneider egy síkgráf három erdőre, úgynevezett Schneider-erdőre történő speciális felosztását használta , hogy megtalálja bármely gráf vonalszakaszát egy kis területű rácsba. $n$ $3n-6$

Algoritmusok

Egy gráf faszerűsége egy általánosabb matroid dekompozíciós probléma speciális eseteként fejezhető ki , amelyben egy matroid elemszámát kisebb számú független halmaz uniójában kell kifejezni . Következésképpen a fásodás polinomiális idejű algoritmussal számítható [1] .

Kapcsolódó fogalmak

Egy gráf csillagfája akkora, mint a minimális erdő mérete, amelynek minden fája egy csillag (legfeljebb egy csúcsú fa, amely nem levél), amelyre a gráf élei felbonthatók. Ha egy fa maga nem csillag, akkor a csillagfája kettő, ami akkor látható, ha az éleket két részhalmazra osztjuk - páratlan és páros távolságra a gyökértől. Így egy gráf csillagarboricitása nem kisebb, mint a fásodása, és nem nagyobb, mint a fásodásának kétszerese.

A gráf lineáris faszerkezete annak a minimális lineáris erdőnek a mérete ( olyan erdő , amelyben minden csúcs legfeljebb két élre esik), amelyre a gráf élei felbonthatók. A gráf lineáris fássága szorosan összefügg a csúcsok maximális fokával és a meredekségeinek számával .

Egy gráf pszeudofája az álerdők minimális száma,amelyekre az éleket fel lehet bontani. Ez a szám megegyezik az élek és csúcsok maximális arányával a gráf bármely részgráfjában. Az arboreszcenciához hasonlóan a pszeudo-arboreszcenciának is van egy matroid szerkezete, amely lehetővé teszi a számítási hatékonyságot [1] .

A gráf vastagsága a sík részgráfok minimális száma, amelyekre az éleket fel lehet osztani. Mivel minden síkgráfnak három fásodási értéke van, bármely gráf vastagsága legalább egyharmada az arboreszcenciának és legfeljebb az arboreszcenciának.

A gráf degeneráltsága a gráf összes generált részgráfján belül a részgráf csúcsainak minimális foka . Egy fagráf degeneráltságanem kisebbés nem nagyobb, mint. A gráf színezőszáma, más néven Szekeres-Wilf szám [2] , mindig egyenlő a degenerációjával plusz 1 [3] . $a$ $a$ $2a-1$

A gráf hatványa egy tört érték, melynek egész része adja meg a gráfra rajzolható, nem átfedő feszülőfák maximális számát. Ennek a számnak a kiszámítása csomagolási probléma, ami kettős a fásodási problémából adódó lefedési problémával.

A töredékes arboreszcencia egy olyan továbbfejlesztett faanyag, amelyet a következőképpen definiálunk: Más szavakkal, egy gráf arboreszcenciája a tört arboreszcencia felső határa. $G$ $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$

(a,b)-A felbonthatóság általánosítja a fát. Egy gráf -felbontható, ha élei halmazokra bonthatók, amelyek mindegyike egy erdőt ad, kivéve egyet, amely maximális fokszámú gráfot ad. A fa gráf-felbontható. $(a,b)$ $a+1$ $b$ $a$ ${\displaystyle(a;0)}$

Irodalom

N. Alon. A grafikonok lineáris arboricitása // Israel Journal of Mathematics . - 1988. - T. 62 , sz. 3 . – S. 311–325 . - doi : 10.1007/BF02783300 .
B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. Nash-Williams gráf arboricitására vonatkozó tételének rövid bizonyítása // Graphs and Combinatorics. - 1994. - T. 10 , sz. 1 . – S. 27–28 . - doi : 10.1007/BF01202467 .
Erdős P., Hajnal A.. A gráfok és halmazrendszerek kromatikus számáról // Acta Mathematica Hungarica . - 1966. - T. 17 , sz. 1–2 . – S. 61–99 . - doi : 10.1007/BF02020444 .
HN Gabow, HH Westermann. Erdők, keretek és játékok: Algoritmusok matroid összegekhez és alkalmazásokhoz // Algorithmica . - 1992. - T. 7 , szám. 1 . – S. 465–497 . - doi : 10.1007/BF01758774 .
S. L. Hakimi, J. Mitchem, E. E. Schmeichel. Grafikonok csillagarboricitása // Diszkrét matematika . - 1996. - T. 149 . – S. 93–98 . - doi : 10.1016/0012-365X(94)00313-8 .
TR Jensen, B. Toft. Grafikonszínezési problémák. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
c.st. JA Nash-Williams. Véges gráfok él-diszjunkt feszítő fái // Journal of the London Mathematical Society . - 1961. - T. 36 , sz. 1 . — S. 445–450 . - doi : 10.1112/jlms/s1-36.1.445 .
c.st. JA Nash-Williams. Véges gráfok bontása erdőkre // Journal of the London Mathematical Society . - 1964. - T. 39 , sz. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
W. Schnyder. Proc. 1. ACM/SIAM szimpózium a diszkrét algoritmusokról (SODA). - 1990. - S. 138-148.
G. Szekeres, H. S. Wilf. Egyenlőtlenség egy gráf kromatikus számához // Journal of Combinatorial Theory . - 1968. - doi : 10.1016/s0021-9800(68)80081-x .
WT Tutte. Egy gráf n összefüggő tényezőre való felbontásának problémájáról // Journal of the London Mathematical Society . - 1961. - T. 36 , sz. 1 . – S. 221–230 . - doi : 10.1112/jlms/s1-36.1.221 .