Fa (gráfelmélet)
irányítatlan, összefüggő, körmentes gráf
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.
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 |
Tulajdonságok
szerkesztés- 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.[1]
- 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ő csillagkromatikus száma a fakomponensek közül a legnagyobb sugár+1, illetve 3, amelyik ezek közül a maximális.[2]
Példák
szerkesztés- 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
szerkesztésA 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ű.
Jegyzetek
szerkesztés- ↑ Ennek az állításnak a végtelen gráfokra való igazolása felhasználja a kiválasztási axiómát.
- ↑ Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029
Hivatkozások
szerkesztés- 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