Faszerkesztés

a fa egy irányítatlan g gráf, amely megfelel az alábbi ekvivalens feltételek bármelyikének:

• G összefüggő és aciklikus (nem tartalmaz ciklusokat).
• G aciklikus, és egy egyszerű ciklus jön létre, ha bármilyen él hozzáadódik G-hez.
• G csatlakozik, de leválasztódik, ha egyetlen él eltávolításra kerül G-ből.
• G csatlakozik, és a 3 csúcsú teljes gráf K3 nem minorja G-nek.
• G bármely két csúcsa összekapcsolható egy egyedi egyszerű úttal.

Ha G − nek véges számú csúcsa van, mondjuk n, akkor a fenti állítások a következő feltételek bármelyikével egyenértékűek:

• G-nek N-1 éle van.
• g össze van kötve, és G minden részgráfja tartalmaz legalább egy csúcsot nulla vagy egy beeső éllel. (Azaz, G kapcsolódik, és 1-degenerált.)
• G – nek nincsenek egyszerű ciklusai és N − 1 élei vannak.

mint másutt a gráfelméletben, a sorrend-nulla gráf (csúcsok nélküli gráf) általában nem tekinthető fának: bár vákuumban gráfként kapcsolódik (bármely két csúcs összekapcsolható egy úttal), az algebrai topológiában nem 0-összefüggő (vagy akár (-1)-összefüggő), ellentétben a nem üres fákkal, és megsérti az “eggyel több csúcs, mint él” relációt. Ez azonban lehet tekinteni, mint egy erdő, amely nulla fák.

a belső csúcs (vagy belső csúcs vagy ágcsúcs) legalább 2 fokos csúcs. Hasonlóképpen, egy külső csúcs (vagy külső csúcs, terminális csúcs vagy levél) az 1.fokú csúcs.

az irreducibilis fa (vagy sorozatcsökkentett fa) olyan fa, amelyben nincs 2.fokozatú csúcs (az oeis a000014 szekvenciájában soroljuk fel).

ForestEdit

az erdő egy irányítatlan gráf, amelyben bármely két csúcsot legfeljebb egy út köt össze. Ekvivalens módon az erdő egy irányítatlan aciklusos gráf, amelynek összes összekapcsolt összetevője fa; más szóval, a gráf a fák diszjunkt uniójából áll. Különleges esetként az order-zero gráf (egy nulla fából álló erdő), egy fa és egy él nélküli gráf példák az erdőkre.Mivel minden fára V-E = 1, könnyen megszámolhatjuk az erdőn belüli fák számát, kivonva az összes csúcs és az összes él közötti különbséget. TV-TE = fák száma az erdőben.

PolytreeEdit

a polytree (vagy irányított fa vagy orientált fa vagy egyedül összekapcsolt hálózat) egy irányított aciklikus gráf (dag), amelynek mögöttes irányítatlan gráfja egy fa. Más szavakkal, ha irányított éleit irányítatlan élekkel helyettesítjük, akkor egy irányítatlan gráfot kapunk, amely mind összekapcsolt, mind aciklusos.

egyes szerzők az “irányított fa” kifejezést arra az esetre korlátozzák, amikor az élek mind egy adott csúcs felé irányulnak, vagy mind egy adott csúcstól távol vannak (lásd arboreszcencia).

PolyforestEdit

a polyforest (vagy irányított erdő vagy orientált erdő) egy irányított aciklusos gráf, amelynek mögöttes irányítatlan gráfja erdő. Más szavakkal, ha irányított éleit irányítatlan élekkel helyettesítjük, akkor egy irányítatlan gráfot kapunk, amely aciklusos.

egyes szerzők az “irányított erdő” kifejezést arra az esetre korlátozzák, amikor az egyes összekapcsolt komponensek élei mind egy adott csúcs felé irányulnak, vagy mind egy adott csúcstól távol vannak (lásd elágazás).

Rooted treeEdit

a rooted tree olyan fa, amelynek egyik csúcsa a gyökér. A gyökeres fa szélei természetes tájoláshoz rendelhetők, akár a gyökértől távol, akár a gyökér felé, ebben az esetben a szerkezet irányított gyökeres fává válik. Ha egy irányított gyökeres fa orientációja távol van a gyökértől, akkor an-nak hívják arboreszcencia vagy ki-fa; ha a gyökér felé orientálódik, akkor an anti-arboreszcencia vagy fán belül. A fa-rend a részleges rendezés egy fa csúcsain u < v csak akkor, ha a gyökérből v-be vezető egyedi út áthalad u-n. egy gyökeres t fa, amely néhány g gráf részgráfja, normális fa, ha minden G-ben lévő T-út végei összehasonlíthatók ebben a fa-sorrendben (Diestel 2005, 15. o.). Gyökeres fák, gyakran további struktúrával, például a szomszédok sorrendjével az egyes csúcsokon, kulcsfontosságú adatstruktúra a számítástechnikában; lát fa adatstruktúra.

egy olyan kontextusban, ahol a fáknak állítólag gyökérük van, a kijelölt gyökér nélküli fát szabad fának nevezzük.

a címkézett fa olyan fa, amelyben minden csúcs egyedi címkét kap. Az n csúcson lévő címkézett fa csúcsai általában a címkéket kapják 1, 2,…, n. a rekurzív fa egy címkézett gyökeres fa, ahol a csúcscímkék tiszteletben tartják a fa sorrendjét (azaz., ha u < v két csúcsnál u és v, akkor az u címkéje kisebb, mint a v).

egy gyökeres fában a v csúcs szülője a gyökérhez vezető úton V-hez kapcsolódó csúcs; minden csúcsnak egyedi szülője van, kivéve azt a gyökeret, amelynek nincs szülője. A v csúcs gyermeke olyan csúcs, amelynek v a szülő. A v csúcs felmenője bármely olyan csúcs, amely vagy a v szülője, vagy (rekurzív módon) a v szülőjének felmenője. A leszármazottja a csúcs v bármely csúcs, amely vagy a gyermeke v vagy (rekurzívan) a leszármazottja bármely gyermeke v. a testvér a csúcs v bármely más csúcs a fán, amelynek ugyanaz a szülője, mint v. A levél egy csúcs gyermek nélkül. A belső csúcs olyan csúcs, amely nem levél.

a gyökeres fa csúcsának magassága a levél leghosszabb lefelé vezető útjának hossza. A fa magassága a gyökér magassága. A csúcs mélysége a gyökérhez vezető út hossza (gyökérút). Erre általában szükség van a különféle önkiegyensúlyozó fák, különösen az AVL fák manipulálásakor. A gyökér mélysége nulla, a levelek magassága nulla, és egy fa, amelynek csak egyetlen csúcsa van (tehát mind a gyökér, mind a levél), mélysége és magassága nulla. Hagyományosan egy üres fa (egy fa, amelynek nincsenek csúcsai, ha ilyenek megengedettek) mélysége és magassága -1.

a k-ary fa egy gyökeres fa, amelyben minden csúcsnak legfeljebb k gyermeke van. A 2-ary fákat gyakran bináris fáknak, míg a 3-ary fákat néha hármas fáknak nevezik.

rendezett faszerkesztés

a rendezett fa (vagy síkfa) egy gyökeres fa, amelyben minden csúcs gyermekeinek sorrendje meg van adva. Ezt nevezzük “síkfának”, mert a gyermekek sorrendje egyenértékű a fa beágyazódásával a síkba, amelynek tetején a gyökér, az egyes csúcsok gyermekei pedig alacsonyabbak, mint az adott csúcs. Ha egy gyökeres fa beágyazódik a síkba, ha valaki rögzíti a gyermekek irányát, mondjuk balról jobbra, akkor a beágyazás a gyermekek sorrendjét adja. Fordítva, adott egy rendezett fa, és hagyományosan rajz a gyökér a tetején, akkor a gyermek csúcsok egy rendezett fa lehet felhívni balról jobbra, így lényegében egyedi sík beágyazása.