Kreivi Woodiness

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. lokakuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Suuntaamattoman graafin puuisuus on metsien vähimmäismäärä , joihin reunat voidaan jakaa . Vastaavasti tämä on vähimmäismäärä virittäviä puita , jotka tarvitaan peittämään kaavion reunat.

Esimerkki

Kuvassa on täydellinen kaksiosainen graafi K 4,4 , jossa graafi on jaettu kolmeen eri väreillä väritettyyn metsään. K 4,4 :ää ei voida jakaa vähemmälle määrälle metsiä, koska missä tahansa kahdeksan kärjen metsässä on enintään seitsemän reunaa, kun taas koko graafissa on kuusitoista reunaa, mikä on yli kaksinkertainen määrä yhden metsän reunoja. Siten graafin K 4,4 puuisuus on yhtä suuri kuin kolme.

Puuisuus tiheyden mittana

Graafin puuisuus on graafin tiheyden mitta – graafissa, jossa on paljon reunoja, on korkea puuviivaisuus, ja graafisissa, joissa on korkea puuisuus, on oltava tiheät osagraafit.

Tarkemmin sanottuna, koska missä tahansa n -pisteen metsässä on enintään n − 1 reunaa, graafin, jossa on n kärkeä ja m reunaa, puuisuus on vähintään . Lisäksi minkään graafin aligraafien puuisuus ei voi olla suurempi kuin itse graafin puuisuus, tai vastaavasti graafin puuisuuden tulee olla vähintään yhtä suuri kuin sen aligraafien enimmäispuuisuus. Nash-Williams osoitti, että nämä kaksi tosiasiaa voidaan yhdistää kuvaamaan puuisuutta - jos n S ja m S tarkoittavat vastaavasti tietyn graafin mielivaltaisen aligraafin S kärkien ja reunojen määrää , niin graafin puuisuus on yhtä suuri kuin $\lceil m/(n-1)\rceil$ $\max\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Jokaisella tasograafilla , jossa on kärkipisteet, on maksimi reunoja, mikä tarkoittaa Nash-Williamsin kaavaa, että tasograafin puuisuus ei ylitä kolmea. Schneider käytti erityistä tasograafin hajottamista kolmeen metsään, jota kutsutaan Schneiderin metsäksi , löytääkseen minkä tahansa graafin viivasegmentin upotettuna pienen alueen hilaan. $n$ $3n-6$

Algoritmit

Graafin puuisuus voidaan ilmaista yleisemmän matroidihajoamisongelman erikoistapauksena , jossa matroidin alkioiden lukumäärä on ilmaistava pienemmän määrän riippumattomien joukkojen liitoksena . Tämän seurauksena puuisuus voidaan laskea käyttämällä polynomiaikaista algoritmia [1] .

Aiheeseen liittyvät käsitteet

Graafin tähtipuu on minimimetsän koko, jonka jokainen puu on tähti (enintään yksi kärki ei ole lehti), johon graafin reunat voidaan jakaa. Jos puu ei itse ole tähti, sen tähtipuisuus on kaksi, mikä näkyy, jos reunat jaetaan kahteen osajoukkoon - parittoman ja parillisella etäisyydellä juuresta. Siten graafin tähtien arboresenssi ei ole pienempi kuin sen arboresenssi eikä suurempi kuin kaksi kertaa sen arboresenssi.

Graafin lineaarinen puusto on sen vähimmäislineaarimetsän koko ( metsä , jossa kaikki kärjet osuvat korkeintaan kahteen reunaan), johon graafin reunat voidaan hajottaa. Graafin lineaarinen puuisuus liittyy läheisesti sen huippupisteiden maksimiasteeseen ja sen kaltevuuden määrään .

Graafin pseudopuu on pseudometsienvähimmäismäärä,joihin reunat voidaan hajottaa. Vastaavasti tämä luku on yhtä suuri kuin reunojen ja kärkien maksimisuhde graafin missä tahansa aligraafissa. Kuten arboresenssissa, myös pseudoarboresenssilla on matroidirakenne, joka mahdollistaa laskennan tehokkuuden [1] .

Graafin paksuus on tasomaisten aligraafien vähimmäismäärä, joihin reunat voidaan jakaa. Koska minkä tahansa tasograafin arboresenssi on kolme, minkä tahansa graafin paksuus on vähintään kolmasosa arboresenssista ja korkeintaan arboreenssista.

Graafin degeneraatio on aligraafin pisteiden minimiasteen enimmäismäärä kaikkien generoitujen graafinaligraafien osalta. Puukaavion rappeutuminenei ole pienempieikä suurempi kuin. Graafin väritysluku, joka tunnetaan myös nimellä Szekeres-Wilf-luku [2] , on aina yhtä suuri kuin sen rappeutuminen plus 1 [3] . $a$ $a$ $2a-1$

Kuvaajan potenssi on murto-osa, jonka kokonaislukuosa antaa graafiin piirrettävien ei-päällekkäisten virittävien puiden enimmäismäärän. Tämän luvun laskeminen on pakkausongelma, joka on kaksinkertainen puuisuusongelmasta johtuvan peitto-ongelman kanssa.

Murto- arboresenssi on kehittynyt arboresenssi, joka on määritelty graafille nimellä Toisin sanoen graafin arboresenssi on murto-osan arboresenssin katto. $G$ $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$

(a,b)-Hajotavuus yleistää puuisuuden. Graafi on -hajottava, jos sen reunat voidaan hajottaajoukoiksi, joista jokainen antaa metsän, paitsi yksi, joka antaa graafin, jonka enimmäisaste on. Puukaavio on-hajottava. $(a, b)$ $a+1$ $b$ $a$ ${\näyttötyyli(a,0)}$

Kirjallisuus

N. Alon. Graafeiden lineaarinen arboricity // Israel Journal of Mathematics . - 1988. - T. 62 , no. 3 . — S. 311–325 . - doi : 10.1007/BF02783300 .
B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. Lyhyt todistus Nash-Williamsin teoreemasta graafin arboriteetista // Grafit ja kombinatoriikka. - 1994. - T. 10 , no. 1 . — S. 27–28 . - doi : 10.1007/BF01202467 .
P. Erdős, A. Hajnal. Graafeiden ja joukkojärjestelmien kromaattisesta määrästä // Acta Mathematica Hungarica . - 1966. - T. 17 , no. 1-2 . — S. 61–99 . - doi : 10.1007/BF02020444 .
HN Gabow, HH Westermann. Metsät, kehykset ja pelit: Matroid-summien ja -sovellusten algoritmit // Algorithmica . - 1992. - T. 7 , numero. 1 . — S. 465–497 . - doi : 10.1007/BF01758774 .
S.L. Hakimi, J. Mitchem, E.E. Schmeichel. Graafeiden tähtimäisyys // Diskreetti matematiikka . - 1996. - T. 149 . — S. 93–98 . - doi : 10.1016/0012-365X(94)00313-8 .
TR Jensen, B. Toft. Kuvaajan väritysongelmat. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
c.st. JA Nash-Williams. Äärillisten graafien reunahajoja virittävät puut // Journal of the London Mathematical Society . - 1961. - T. 36 , no. 1 . — S. 445–450 . - doi : 10.1112/jlms/s1-36.1.445 .
c.st. JA Nash-Williams. Äärillisten graafien hajoaminen metsiin // Journal of the London Mathematical Society . - 1964. - T. 39 , no. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
W. Schnyder. Proc. Ensimmäinen ACM/SIAM-symposium diskreetistä algoritmista (SODA). - 1990. - S. 138-148.
G. Szekeres, H. S. Wilf. Epäyhtälö graafin kromaattiselle luvulle // Journal of Combinatorial Theory . - 1968. - doi : 10.1016/s0021-9800(68)80081-x .
WT Tutte. Ongelmasta graafin hajottamiseksi n:ään toisiinsa liittyvään tekijään // Journal of the London Mathematical Society . - 1961. - T. 36 , no. 1 . — S. 221–230 . - doi : 10.1112/jlms/s1-36.1.221 .