Fa (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
Fa
Tree graph.svg
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


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[szerkesztés | forrásszöveg szerkesztése]

  • 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.

Példák[szerkesztés | forrásszöveg szerkesztése]

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

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ű.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Ennek az állításnak a végtelen gráfokra való igazolása felhasználja a kiválasztási axiómát.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • 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