Fa (gráfelmélet)
A Wikipédiából, a szabad enciklopédiából
(Erdő (gráfelmélet) szócikkből átirányítva)
| 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 |
A gráfelméletben a 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 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ő össze nem függő fák uniója, vagy ami ezzel ekvivalens az erdők körmentes gráfok.
Tartalomjegyzék |
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, illetve 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 egy csúcspontja, van legalább egy levele, azaz van legalább egy olyan csúcsa, amelynek a fokszáma 1.
Példák [szerkesztés]
Alkalmazások [szerkesztés]
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.
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.
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
 |
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
