Fák

• Fának nevezünk egy összefüggő körmentes gráfot.
• Gyökeres fának nevezünk egy olyan fát, amiben kijelöltünk egy csomópontot (gyökeret)
• Erdőnek nevezünk több fát, azaz egy körmentes gráf (ennek minden összefüggő komponense fa)
• Egy gráf olyan részgráfját, ami fa, részfának nevezzük (spanning tree)

Tulajdonságok

• Egy n pontból álló fának n-1 éle van. (Biz. indukcióval, minden újan bevitt ponthoz pontosan egy élet húzhatunk.)
• Ha egy fából bármelyik élet kitöröljük, akkor már nem lesz összefüggő.

Példa

Az alábbi gráf egy fa:

Ha megválsztjuk benne az 5-ös csomópontot gyökérnek, akkor az alábbi gyökeres fát kapjuk (egy hierarchia jön létre a csomópontok között):

Gyökeres fákkal kapcsolatos fogalmak

• “gyökér” (rădăcină) – a kiinduló pont, ennél fogva “függesztjük fel” a fát, minek során létrejön egy hierarchia
• “szülő” (tată) – az a pont, ami a gyökér felé vezető úton közvetlenül az aktuális után van (tehát felette); a gyökérnek nincs szülője
• „gyerek” (fiu), „közvetlen leszármazott” (descendent direct) – közvetlenül az aktuális pont alatt levő pont
• „leszármazott” (descendent) – az pont alatt levő pont (gyerekek, gyerekek gyerekei stb.)
• „ős” (ascendent) – a gyökér felé vezető úton az egyik pont (szülő, szülő szülője stb.)
• „levél” (frunză) – olyan pont, aminek nincs leszármazottja
• „testvér” (frate) – olyan pont, aminek ugyanaz a szülője, mint az aktuálisnak
• „szint” (nivel) – az adott pont távolsága a gyökértől
• a fa „mélysége” (adâncime) – a legnagyobb távolság a gyökértől
• „átmérő” (diagonală) – a legnagyobb távolság két pont között

A fentebbi példában:

• a gyökér az 5-ös csomópont;
• a 6-osnak a szülője az 5, a 2-esnek pedig a 6;
• a 6-os csomópont gyerekei az 1 és 2;
• a 6-os csomópont leszármazottai az 1, 2 és 3;
• a 2-es ősei: 6 és 5;
• a fa levelei: 4, 1, 3;
• a 4 és 6 csomópontok testvérek;
• az 5-ös pont a 0-s szinten, a 4 és 6 az 1-es szinten, az 1 és 2 a 2-es szinten található
• a fa mélysége 3
• a fa átmérője 4 (leghosszabb út: 3 2 6 5 4)

Gyakorlat

Hány élet kell törölni egy n pontú teljes gráfból ahhoz, hogy fa legyen?

Válasz: komb(n,2) – (n-1) (mennyi volt - mennyi kell maradjon)

Gyökeres fák ábrázolása memóriában

• Ábrázolható, mint gráf (az ismert módszerekkel) + megjegyezzük, hogy ki a gyökér.
• Leszármazott-listák (Reprezentarea prin referințe descendente): minden csomópontra tároljuk, hogy kik a közvetlen leszármazottai (példa lejjebb), illetve tároljuk, hogy melyik pont a gyökér.
• Apák tömbje / ősvektor (vector de tați): minden pontra lementjük, hogy ki az ő szülője (a gyökér esetén valamilyen speciális értéket használunk, pl. 0-t); lesz tehát egy annyi elemű tömbünk, ahány csomópontja van a fának (példa lejjebb).

Példa:

A fa gyökere az 1-es csomópont. Leszármazott-listákkal történő ábrázolás:

    1: 2 3
    2: üres
    3: 4 5
    4: 6
    5: üres
    6: üres

Az apák tömbje:

    { 0, 1, 1, 3, 3, 4 }

A tömb i. eleme jelzi, hogy ki i pont szülője.

Részfák

• Egy gráf „részfájának” nevezünk egy olyan részgráfot, ami fa.
• Gyökeres fák esetén egy pont részfája az az algráfja a fának, amiben megtartjuk csak ezt a pontot és a leszármazottait (az előző példában a 3-as pont részfája az a fa, ami a 3, 4, 5, 6 csomópontokat tartalmazza).