Contele Woodiness

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 octombrie 2021; verificarea necesită 1 editare .

Arborescitatea unui grafic nedirecționat este numărul minim de păduri în care marginile pot fi descompuse . În mod echivalent, acesta este numărul minim de arbori de acoperire care sunt necesari pentru a acoperi marginile graficului.

Exemplu

Figura prezintă un grafic bipartit complet K 4,4 cu partiții ale graficului în trei păduri colorate în culori diferite. K 4,4 nu poate fi împărțit în mai puține păduri, deoarece orice pădure de pe opt vârfuri are maximum șapte muchii, în timp ce întregul grafic are șaisprezece muchii, ceea ce reprezintă mai mult de două ori numărul de muchii dintr-o singură pădure. Astfel, gradul de arbore al graficului K 4,4 este egal cu trei.

Lemnitatea ca măsură a densității

Caracterul arborescent al unui grafic este o măsură a densității unui grafic - graficele cu un număr mare de muchii au arboreitate mare, iar graficele cu arbore ridicat trebuie să aibă subgrafe dense.

Mai precis, deoarece orice pădure cu n vârfuri are cel mult n − 1 muchii, arborescul unui graf cu n vârfuri și m muchii este de cel puțin . În plus, subgrafele oricărui graf nu pot avea o arboresitate mai mare decât cea a graficului însuși sau, echivalent, arboresitatea graficului trebuie să fie cel puțin la fel de mare ca arborescul maxim al subgrafelor sale. Nash-Williams a dovedit că aceste două fapte pot fi combinate pentru a caracteriza arboreetatea - dacă n S și m S denotă, respectiv, numărul de vârfuri și muchii ale unui subgraf arbitrar S al unui graf dat, atunci arborescul acestuia este egal cu $\lceil m/(n-1)\rceil$ $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Orice graf planar cu vârfuri are un maxim de muchii, ceea ce implică formula Nash-Williams conform căreia caracterul arborescent al unui graf plan nu depășește trei. Schneider a folosit o descompunere specială a unui graf plan în trei păduri, numită pădure Schneider , pentru a găsi încorporarea segmentului de linie a oricărui graf într-o rețea cu suprafață mică. $n$ $3n-6$

Algoritmi

Treeness-ul unui graf poate fi exprimat ca un caz special al unei probleme mai generale de descompunere a matroidei , în care este necesar să se exprime numărul de elemente ale unui matroid în termeni de unire a unui număr mai mic de mulțimi independente . În consecință, treeness poate fi calculat folosind un algoritm de timp polinomial [1] .

Concepte înrudite

Treehood-ul stelar al unui grafic este dimensiunea pădurii minime, fiecare copac fiind o stea (un copac cu cel mult un vârf care nu este o frunză), în care marginile graficului pot fi descompuse. Dacă un copac nu este el însuși o stea, arboretatea lui este de două, ceea ce poate fi văzut dacă marginile sunt împărțite în două subseturi - cu o distanță pară și impară de la rădăcină. Astfel, arboricitatea stelară a unui grafic nu este mai mică decât arborescența sa și nu mai mare de două ori arborescența sa.

Treehood liniar al unui grafic este dimensiunea pădurii liniare minime ( o pădure în care toate vârfurile sunt incidente cu cel mult două muchii) în care muchiile graficului pot fi descompuse. Arborescitatea liniară a unui grafic este strâns legată de gradul maxim de vârfuri și numărul de pante .

Pseudo-arborele al unui grafic este numărul minim depseudo-păduriîn care marginile pot fi descompuse. În mod echivalent, acest număr este egal cu raportul maxim dintre muchii și vârfuri din orice subgraf al graficului. Ca și în cazul arborescenței, pseudo-arborescența are o structură matroide care permite eficiența computațională [1] .

Grosimea unui grafic este numărul minim de subgrafe plane în care pot fi împărțite muchiile. Deoarece orice graf plan are o arborescență de trei, grosimea oricărui graf este de cel puțin o treime din arborescență și cel mult arborealitate.

Degenerarea unui graf este numărul maxim, peste toate subgrafele generate ale grafului, al gradului minim al vârfurilor subgrafului. Degenerarea unui grafic arborenu este nici mai mică, nici mai mare decât. Numărul de colorare a graficului, cunoscut și sub numele de numărul Szekeres-Wilf [2] , este întotdeauna egal cu degenerarea lui plus 1 [3] . $A$ $A$ $2a-1$

Puterea unui grafic este o valoare fracționară, a cărei parte întreagă dă numărul maxim de arbori care se întind nesuprapuși care pot fi desenați pe grafic. Calcularea acestui număr este o problemă de ambalare, care este dublă cu problema de acoperire care decurge din problema arborelui.

Arborescența fracțională este o arborescență avansată definită pentru un graf ca. Cu alte cuvinte, arborescența unui graf este plafonul arborescenței fracționale. $G$ $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$

(a,b)-Descompunerea generalizează arboreitatea. Un grafic este -descomposabil dacă muchiile sale pot fi descompuse înmulțimi, fiecare dintre acestea dând o pădure, cu excepția uneia, care dă un grafic cu gradul maxim. Un grafic arboreeste-descomposabil. $(a,b)$ $a+1$ $b$ $A$ ${\displaystyle(a,0)}$

Literatură

N. Alon. Arboricitatea liniară a graficelor // Israel Journal of Mathematics . - 1988. - T. 62 , nr. 3 . — S. 311–325 . - doi : 10.1007/BF02783300 .
B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. O scurtă demonstrație a teoremei lui Nash-Williams pentru arboricitatea unui graf // Grafice și combinatorie. - 1994. - T. 10 , nr. 1 . — S. 27–28 . - doi : 10.1007/BF01202467 .
P. Erdős, A. Hajnal. Despre numărul cromatic de grafice și sisteme de mulțimi // Acta Mathematica Hungarica . - 1966. - T. 17 , nr. 1–2 . — S. 61–99 . - doi : 10.1007/BF02020444 .
HN Gabow, HH Westermann. Păduri, cadre și jocuri: algoritmi pentru sume și aplicații matroide // Algorithmica . - 1992. - T. 7 , nr. 1 . — S. 465–497 . - doi : 10.1007/BF01758774 .
S.L. Hakimi, J. Mitchem, E. E. Schmeichel. Arboricitatea în stele a graficelor // Matematică discretă . - 1996. - T. 149 . — S. 93–98 . - doi : 10.1016/0012-365X(94)00313-8 .
TR Jensen, B. Toft. Probleme de colorare a graficelor. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
c.st. JA Nash-Williams. Arbori care se întind pe margini disjunși ai graficelor finite // Journal of the London Mathematical Society . - 1961. - T. 36 , nr. 1 . — S. 445–450 . - doi : 10.1112/jlms/s1-36.1.445 .
c.st. JA Nash-Williams. Descompunerea graficelor finite în păduri // Journal of the London Mathematical Society . - 1964. - T. 39 , nr. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
W. Schnyder. Proc. Primul Simpozion ACM/SIAM despre algoritmi discreti (SODA). - 1990. - S. 138-148.
G. Szekeres, H. S. Wilf. O inegalitate pentru numărul cromatic al unui grafic // Journal of Combinatorial Theory . - 1968. - doi : 10.1016/s0021-9800(68)80081-x .
WT Tutte. Despre problema descompunerii unui grafic în n factori conectați // Journal of the London Mathematical Society . - 1961. - T. 36 , nr. 1 . — S. 221–230 . - doi : 10.1112/jlms/s1-36.1.221 .