TreeEdit

puu on suuntaamaton kuvaaja G, joka täyttää jonkin seuraavista vastaavista ehdoista:

• G on yhtenäinen ja asyklinen (ei sisällä syklejä).
• G on asyklinen, ja yksinkertainen sykli muodostuu, jos g: hen lisätään mikä tahansa reuna.
• G on yhtenäinen, mutta epäyhtenäinen, jos jokin yksittäinen reuna poistetaan G: stä.
• G on yhtenäinen ja 3-verteksinen täydellinen kaavio K3 ei ole g: n molli.
• mitkä tahansa g: n kaksi kärkipistettä voidaan yhdistää ainutlaatuisella yksinkertaisella polulla.

Jos G: llä on finitely monta kärkipistettä, sanotaan n, niin edellä mainitut lauseet vastaavat myös jotain seuraavista ehdoista:

• G on yhtenäinen ja siinä on N − 1 särmät.
• G on yhtenäinen, ja jokainen g: n alalaji sisältää vähintään yhden kärkipisteen, jossa on nolla tai yksi tapahtumareunus. (Eli G on kytketty ja 1-degeneroitunut.)
• G: ssä ei ole yksinkertaisia syklejä ja siinä on N − 1-särmät.

kuten muuallakin graafiteoriassa, kertalukua kuvaavaa nollakäyrää (kuvaajaa, jossa ei ole kärkipisteitä) ei yleensä pidetä puuna: vaikka se on tyhjästi kytketty kuvaajaksi (mikä tahansa kaksi kärkipistettä voidaan yhdistää polulla), se ei ole 0-kytketty (tai jopa (-1)-kytketty) algebrallisessa topologiassa, toisin kuin ei-tyhjät puut, ja rikkoo ”one more vertex than edges” – suhteen. Sitä voidaan kuitenkin pitää nollapuista koostuvana metsänä.

sisäinen huippupiste (tai sisempi huippupiste tai haarapiste) on huippupiste, jonka aste on vähintään 2. Samoin ulkoinen huippupiste (tai ulompi huippupiste, päätepiste tai lehti) on huippupiste, jonka aste on 1.

irreducible tree (tai series-reduced tree) on puu, jossa ei ole asteen 2 kärkipistettä (lueteltu OEIS: n järjestyksessä A000014).

Metsä

metsä on suuntaamaton kuvaaja, jossa mikä tahansa kaksi kärkipistettä yhdistyy korkeintaan yhdellä polulla. Vastaavasti metsä on suuntaamaton asyklinen kuvaaja, jonka kaikki toisiinsa liittyvät osat ovat puita; toisin sanoen kuvaaja koostuu puiden hajanaisesta liitosta. Erityistapauksina esimerkkejä metsistä ovat järjestys-nolla-kaavio (nollapuusta koostuva metsä), yksittäinen puu ja reunaton kaavio.Koska jokaiselle puulle V-E = 1, voimme helposti laskea niiden puiden määrän, jotka ovat metsässä vähentämällä erotus yhteensä vertices ja yhteensä reunat. TV-TE = puiden lukumäärä metsässä.

Polytreedit

polytree (tai suunnattu puu tai suuntautunut puu tai yksiyhteinen verkko) on suunnattu asyklinen kuvaaja (DAG), jonka taustalla oleva suuntaamaton kuvaaja on puu. Toisin sanoen, jos korvaamme sen suunnatut reunat suuntaamattomilla reunoilla, saamme suuntaamattoman kuvaajan, joka on sekä kytketty että asyklinen.

jotkut kirjoittajat rajoittavat lauseen ”suunnattu puu” tapaukseen, jossa reunat on kaikki suunnattu tiettyyn huippupisteeseen tai kaikki suunnattu pois tietystä huippupisteestä (katso arborescence).

PolyforestEdit

polyforest (tai suunnattu metsä tai suuntautunut metsä) on suunnattu asyklinen graafi, jonka taustalla oleva suuntaamaton kuvaaja on metsä. Toisin sanoen, jos korvaamme sen suunnatut reunat suuntaamattomilla reunoilla, saamme suuntaamattoman kuvaajan, joka on asyklinen.

jotkut kirjoittajat rajoittavat lauseen ”suunnattu metsä” tapaukseen, jossa jokaisen yhdistetyn komponentin reunat on kaikki suunnattu tiettyyn huippupisteeseen tai kaikki suunnattu pois tietystä huippupisteestä (katso haarautuminen).

juurtunut puu

juurtunut puu on puu, jonka yksi kärkipää on nimetty juureksi. Juurtuneen puun reunoille voidaan osoittaa luonnollinen suunta, joko poispäin juuresta tai kohti juurta, jolloin rakenteesta tulee suuntautunut Juurinen puu. Kun suunnattu juurtunut puu on suuntautunut pois juuresta, sitä kutsutaan arboresenssiksi tai ulospuuksi; kun se on suuntautunut juureen, sitä kutsutaan anti-arboresenssiksi tai in-puuksi. Puujärjestys on osittainen järjestys sellaisen puun kärkipisteissä, jonka u < v, Jos ja vain jos ainutlaatuinen polku juuresta v kulkee u: n kautta. juurtunut Puu T, joka on jonkin kaavion g alalaji, on normaali Puu, jos jokaisen G: n t-polun päät ovat vertailukelpoiset tässä puujärjestyksessä (Diestel 2005, s. 15). Juurtuneet puut, joilla on usein lisärakenne, kuten naapureiden tilaaminen kussakin huippupisteessä, ovat tietojenkäsittelytieteen keskeisiä tietorakenteita; katso puun tietorakenne.

asiayhteydessä, jossa puilla oletetaan olevan juuri, puuta, jolla ei ole nimettyä juurta, kutsutaan vapaaksi puuksi.

leimattu puu on puu, jossa jokaiselle kärkipisteelle annetaan yksilöllinen merkki. The vertices, merkitty puu n vertices ovat tyypillisesti annetaan etiketit 1, 2,…, n. rekursiivinen puu on merkitty juurtunut puu, jossa kärkimerkinnät kunnioittavat puun järjestystä (ts., jos u < v kahden pisteen u ja v kohdalla, niin u: n merkki on pienempi kuin V: n merkki).

juurtuneessa puussa kärkipisteen V emäpiste on v: hen liitetty kärkipiste juureen johtavalla polulla; jokaisella kärkipisteellä on ainutlaatuinen emäpiste lukuun ottamatta juurta, jolla ei ole emäpistettä. A lapsi on huippupiste v on huippupiste, jonka v on vanhempi. A ascendant, huippupiste v on mikä tahansa huippupiste, joka on joko vanhemman v tai on (rekursiivisesti) ascendant, vanhemman v. A descendant, huippupiste v on mikä tahansa huippupiste, joka on joko lapsi, v tai on (rekursiivisesti) descendant tahansa lasten V. A sisarus, joka huippupiste v on mikä tahansa muu huippupiste, puu, joka on sama vanhempi kuin v. lehti on huippupiste, jolla ei ole lapsia. Sisäinen huippupiste on huippupiste, joka ei ole lehtiä.

juurtuneen puun kärkipisteen korkeus on pisimmän alaspäin vievän polun pituus kyseisen kärkipisteen lehteen. Puun korkeus on juuren korkeus. Verteksin syvyys on sen juureen johtavan polun pituus (juuripolku). Tätä tarvitaan yleisesti erilaisten itsestään tasapainoilevien puiden, erityisesti AVL-puiden, manipuloinnissa. Juurella on syvyys nolla, lehdillä korkeus nolla, ja puulla, jossa on vain yksi kärki (siis sekä juuri että lehti), on syvyys ja korkeus nolla. Perinteisesti tyhjällä puulla (puu, jossa ei ole kärkipisteitä, jos sellainen sallitaan) on syvyys ja korkeus -1.

k-ary-puu on juurtunut puu, jossa kussakin kärkipäässä on korkeintaan k-lapsia. 2-ary puita kutsutaan usein binary puita, kun taas 3-ary puita kutsutaan joskus ternary puita.

tilattu puu

tilattu puu (tai tasopuu) on juurtunut puu, jossa kunkin kärkipään lapsille on määritelty tilaus. Tätä kutsutaan ”plane tree”, koska tilaus, lapset vastaa embedding, puu, plane, jossa juuri yläosassa ja lapset kunkin huippupiste pienempi kuin huippupiste. Koska embedding, juurtunut puu, lentokone, jos yksi korjaa suuntaan lapsia, sano vasemmalta oikealle, sitten embedding antaa tilaus, lapset. Kääntäen, koska tilattu puu, ja perinteisesti piirustus juuri yläosassa, niin lapsi vertices, tilattu puu voidaan piirtää vasemmalta oikealle, jolloin saadaan olennaisesti ainutlaatuinen planar embedding.