Fa (gráfelmélet)

Fa
Címkézett fa 6 csúcsból és 5 élből
Csúcsok száma	n
Élek száma	n − 1
Kromatikus szám	2, ha n>1

A gráfelméletben fának vagy fagráfnak nevezzük azokat a gráfokat, amelynek bármely két csúcsát pontosan egy út köti össze, azaz a fák körmentes összefüggő gráfok. Erdőnek nevezzük azokat a gráfokat, amelynek bármely két csúcsát legfeljebb egy út köti össze, azaz ahogy az elnevezés is utal rá, az erdő olyan gráf, aminek komponensei fák, vagy ami ezzel ekvivalens, az erdők körmentes gráfok.

Tulajdonságok

• Minden fa páros gráf. Minden fa, amelynek megszámlálható sok csúcspontja van, síkgráf.
• Minden összefüggő G gráfnak van feszítő fája, azaz létezik hozzá olyan fa, ami tartalmazza a G összes csúcspontját, és amelynek élei egyben a G gráfnak is élei. Továbbá minden gráfnak van feszítő erdője, tehát létezik hozzá olyan erdő, aminek a komponensei azonosak az eredeti gráféival.
• Minden fának, amelynek van legalább két csúcspontja, van legalább két levele, azaz van legalább két olyan csúcsa, amelynek a fokszáma 1.
• Egy fa csúcsainak száma 1-gyel nagyobb az élek számánál. Erdő esetén a csúcsok és az élek számának különbsége a komponensek száma.
• Egy erdő $\chi _{s}(G)$ csillagkromatikus száma a fakomponensek közül a legnagyobb sugár+1, illetve 3, amelyik ezek közül a maximális.

Példák

• Bethe-rács
• A hernyó olyan fa, melynek az összes csúcsa egy központi úttól legfeljebb egy él távolságra található.

Alkalmazások

A számítástudományban széleskörűen használnak olyan, fába szervezett adatstruktúrákat, mint a bináris keresőfák, AVL-fák stb. A legtöbb fájlrendszer is faszerkezetű.

Hivatkozások

• Hajnal Péter: Gráfelmélet, Polygon, Szeged
• Szendrei Ágnes: Diszkrét matematika Logika, algebra, kombinatorika, Polygon, Szeged
• Andrásfai Béla: Gráfelmélet, Polygon, Szeged, 1994