2. Fák tulajdonságai
Fa fogalma, fák egyszerű tulajdonságai. Feszítőfa fogalma, annak létezése. Minimális összsúlyú feszítőfa, Kruskal algoritmusa.
A fa definíciója
Levelek létezése fákban
Ha $F$ legalább két csúcsú fa, akkor $F$ tartalmaz legalább két olyan csúcsot, amiknek a foka egy.
Válasszunk $F$-ben egy $P$ **leghosszabb utat** – vagyis egy olyat, aminél hosszabb út már nincs $F$-ben. Mivel $F$ legalább két csúcsú és így tartalmaz élt, ezért $P$ pozitív hosszúságú, így két különböző végpontja van. Azt állítjuk, hogy ezeknek a foka egy.
Legyen $v$ a $P$ egyik végpontja, szomszédja a $P$ mentén $u$. Tegyük fel **indirekt**, hogy $v$-nek van egy $u$-tól különböző $x$ szomszédja is. Ekkor két eset lehetséges:
-
1
Ha $x$ nincs rajta $P$-n: akkor $P$-t megtoldhatjuk a $\{v,x\}$ éllel és az $x$ csúccsal; mivel így egy $P$-nél hosszabb utat kapunk, ez $P$ választása miatt **ellentmondás**.
-
2
Ha viszont $x$ rajta van $P$-n: akkor $P$-nek a $v$-től $x$-ig tartó szakasza a $\{v,x\}$ éllel együtt **kört alkotna** $F$-ben, ami szintén ellentmondás (mivel $F$ fa).
Mivel $P$ két végpontjának csak egy-egy szomszédja van, ezért ezzel a tételt beláttuk.
Vizuális ellentmondás-detektor
Próbálj meg egy új szomszédot ($x$) adni a végponthoz!
Húzd az egeret a gombok fölé a szemléltetéshez!
Csúcsok és élek kapcsolata
Legyen $G$ egy $n$ csúcsú és $m$ élű gráf. Ekkor:
- ha $G$ összefüggő, akkor $m \geq n - 1$;
- ha $G$ körmentes, akkor $m \leq n - 1$;
- ha $G$ fa, akkor $m = n - 1$.
Bizonyítás (Építési eljárás)
Képzeljük el, hogy $G$-t az $n$ csúcsú üres (él nélküli) gráfból építjük fel úgy, hogy egymás után adjuk hozzá az éleket, és figyeljük a **komponensek** számát. Kezdetben $n$ komponensünk van (minden csúcs külön).
Az él hozzáadása nem változtat az elérhetőségen, így a komponensek száma nem változik. Viszont egy kör keletkezik.
A két komponens egyesül egyetlen új komponenssé, így a komponensek száma pontosan eggyel csökken.
(i) Ha $G$ összefüggő: Kezdetben $n$ komponens volt, a végén pedig csak 1. Mivel egy él legfeljebb eggyel tudja csökkenteni a komponensek számát, legalább $n-1$ élre volt szükség.
(ii) Ha $G$ körmentes: Az 1. eset (kör bezárása) sosem fordulhat elő. Tehát minden él pontosan eggyel csökkenti a komponensek számát. Mivel a számuk nem mehet 1 alá, legfeljebb $n-1$ élt húzhattunk be.
Komponens-építő Labor
Adj hozzá éleket és figyeld, hogyan csökken a komponensek száma!
Kidolgozott feladat: Fa keresése fokszámok alapján
Feladat
Egy $F$ fa csúcsainak fokszámai között pontosan kétféle érték fordul elő és mindkettő pontosan ugyanannyiszor. Adjuk meg $F$-et.
Megoldás levezetése
Mivel a kétféle fokszám ugyanannyiszor fordul elő, ezért $F$ csúcsainak száma páros. Legyen a csúcsok száma $n = 2k$. Mivel minden fának van levele, az egyik fokszám biztosan az 1, a másikat jelölje $d$.
Egyenletek felírása
$\sum d(v) = k \cdot d + k \cdot 1 = k(d + 1)$
A csúcsok fokszámösszege
$2m = 2(n - 1) = 2(2k - 1) = 4k - 2$
Az élszám kétszerese a fa tulajdonsága ($m = n - 1$) alapján
Ezeket egyenlővé téve: $k(d + 1) = 4k - 2$. Ezt $d$-re rendezve:
Mivel $d$ és $k$ is pozitív egész, ezért csak a $k = 1$ vagy $k = 2$ eset lehetséges:
$d = 3 - 2 = 1$ adódna, de ekkor nem volna kétféle fokszám.
Ekkor $d = 3 - 1 = 2$, ami egy érvényes megoldás.
Konklúzió
A keresett $F$ fa tehát $n = 4$ csúcsú, két darab elsőfokú és két darab másodfokú csúccsal rendelkezik. Ez egyedül a **három hosszúságú út** ($P_4$).
A végeredmény: $P_4$
A fokszámok listája: (1, 2, 2, 1) — mindkét érték pontosan kétszer szerepel.
Feszítőfa
Feszítőfa-építő labor
Kattints az élekre, hogy kiválaszd őket az $F$ részgráfba!
Feszítőfa létezése
A $G$ gráfnak akkor és csak akkor létezik feszítőfája, ha $G$ összefüggő.
($\Rightarrow$) irány Ha $G$-nek létezik egy $F$ feszítőfája, akkor (mivel $F$ fa és így összefüggő) bármely $x,y \in V(G) = V(F)$ csúcsok között létezik $F$-béli út, ami egyben $G$-béli út is. Így $G$ definíció szerint összefüggő.
($\Leftarrow$) irány Legyen $G$ egy összefüggő gráf. Az üres élhalmaztól indulva fokozatosan építjük fel a feszítőfa éleit. Mindig egy olyan élt választunk, amely az aktuális részgráf **különböző komponenseit** köti össze.
Ezzel az eljárással sosem hozunk létre kört (mivel csak komponensek közé húzunk élt), és a komponensek száma minden lépésben pontosan eggyel csökken. Amint eléri az 1-et, feszítőfát kaptunk.
Be kell látnunk, hogy ha a részgráfnak még legalább két komponense van, mindig van "híd" közöttük $G$-ben.
Mivel $G$ összefüggő, létezik út egy $x \in K_x$ és $y \in K_y$ csúcs között. Az úton haladva az első olyan $\{u,v\}$ él, ahol $u \in K_x$ de $v \notin K_x$, éppen egy ilyen, két különböző komponenst összekötő él lesz.
Algoritmus-szemléltető
Építs feszítőfát: adj hozzá olyan éleket, amelyek különböző komponenseket kötnek össze!
Kidolgozott feladat: Kritikus csúcsok vizsgálata
Feladat
Létezik-e olyan (legalább két csúcsú) összefüggő gráf, aminek bármelyik csúcsát törölve (az éleivel együtt) a kapott gráf már nem összefüggő?
Megoldás levezetése
Megmutatjuk, hogy ilyen gráf nem létezik: minden összefüggő $G$ gráfból törölhető egy alkalmasan választott $v$ csúcs úgy, hogy az összefüggőség megmaradjon.
Vegyünk ugyanis egy $F$ feszítőfát $G$-ben. A korábbiakban bizonyítottuk, hogy egy legalább két csúcsú fának van legalább két **levele** (1 fokú csúcsa). Legyen $v$ egy ilyen levél.
Ekkor a $v$ törlése után maradó $G'$ gráf összefüggő marad, mert bármely $x$ és $y$ csúcs között még az $F$-ből megmaradó (szintén összefüggő) részgráfban is létezik út.
Vizuális bizonyítás segédlet
Ha egy „levelet” törölsz, a gráf egyben marad. Ha egy belső csúcsot, a gráf széteshet. A feszítőfa létezése garantálja, hogy bármely összefüggő gráfban van legalább két „biztonságos” pont.
A levél nem „tart össze” más pontokat.
A központi „csuklópont” törlése szétválasztja a gráfot.
Minimális feszítőfa és a mohó algoritmus
Ha a $G$ összefüggő gráf $F_{mohó}$ feszítőfáját úgy készítjük el, hogy az üres halmaztól indulva mindig az aktuális részgráf különböző komponenseit összekötő, **legkisebb súlyú** élek egyikével bővítjük az élhalmazt, akkor $F_{mohó}$ **minimális összsúlyú** feszítőfa $G$-ben.
Bizonyítás (Indirekt módon)
Számozzuk meg $G$ éleit $e_1, e_2, \dots, e_m$ sorrendben a súlyuk szerint: $w(e_1) \leq w(e_2) \leq \dots \leq w(e_m)$.
Vizsgáljuk meg az első eltérést az $e_k = \{u,v\}$ élnél:
-
1
$e_k \notin F_{mohó}$ de $e_k \in F_{opt}$: Ez csak akkor történhetett, ha a mohó algoritmus azért utasította el $e_k$-t, mert az a korábban beválasztott (és $F_{opt}$-tal közös) élekkel **kört alkotott** volna. Ez ellentmond $F_{opt}$ körmentességének.
-
2
$e_k \in F_{mohó}$ de $e_k \notin F_{opt}$: Mivel $F_{opt}$ feszítőfa, létezik benne egy $u-v$ út. Ebben kell lennie egy $e_\ell$ élnek, ami nincs benne $F_{mohó}$-ban. $e_k$ bevétele és $e_\ell$ kivétele egy új, optimális feszítőfát ad, ami több élben egyezik a mohóval — ez ellentmondás.
A Mohó Stratégia Működése
Az algoritmus "vak" bizalma a legolcsóbb élben kifizetődő: a lokális döntések sorozata garantáltan a globális minimumhoz vezet.
Kruskal algoritmusa
Bemenet: Egy $n$ csúcsú és $m$ élű $G = (V,E)$ összefüggő gráf és egy $w: E \to \mathbb{R}$ súlyfüggvény.
RENDEZZÜK AZ ÉLEKET a $w(e)$ súlyok szerinti növekvő sorrendbe: $w(e_1) \leq w(e_2) \leq \dots \leq w(e_m)$
$k \leftarrow 0$; $j \leftarrow 1$; $E(F) \leftarrow \emptyset$
ciklus: amíg $k < n - 1$
VIZSGÁLJUK MEG, HOGY $e_j$ VÉGPONTJAI KÜLÖNBÖZŐ KOMPONENSBEN VANNAK-E
ha igen, akkor:
$E(F) \leftarrow E(F) \cup \{e_j\}$ // Él beválogatása
$k \leftarrow k + 1$
$j \leftarrow j + 1$
ciklus vége
Leállási feltétel
Az algoritmus pontosan $n-1$ él beválogatása után áll meg. Mivel egy $n$ csúcsú fa élszáma mindig ennyi (lásd a korábbi **2.3-as tételt**), ekkorra garantáltan egy összefüggő feszítőfát kapunk.
Komponens vizsgálat
A 4. lépés a „lelke” a körmentességnek: ha két pont már azonos komponensben van, egy új él kört zárna be közöttük. Ezt elkerülve az algoritmus végig erdő struktúrát tart fenn.
Kruskal-algoritmus: Interaktív szimuláció
Gráfépítő vászon
Kattints a vászonra csúcsokhoz, kösd össze őket az élekért!
Algoritmus lépései
Összefoglaló Kvíz
Mennyire vágod a fák elméletét?
Vidd fölé az egeret vagy kattints a válasz felfedéséhez!
#01 Fa definíciója
Melyik az a két kritérium, aminek egy gráfnak meg kell felelnie, hogy fa legyen?
#02 Élszám számítás
Ha egy fa 20 csúccsal rendelkezik, pontosan hány éle van?
#03 Levelek
Minimum hány levél (elsőfokú csúcs) található egy legalább két csúcsú fában?
#04 Kruskal-elv
Melyik élt utasítja el a Kruskal-algoritmus a válogatás során?
Tudtad-e?
Cayley bűvös száma
Tudtad, hogy pontosan $n^{n-2}$ különböző, címkézett fát lehet rajzolni $n$ darab csúccsal? Ez a Cayley-formula. Ha csak 10 csúcsunk van, már **100 000 000** különböző fát alkothatunk!
Algoritmus a sötétség ellen
A minimális feszítőfát először Otakar Borůvka kereste 1926-ban. Célja nem matematikai bravúr volt: Morvaország elektromos hálózatát akarta a lehető legolcsóbban kiépíteni.
Miért fér el a zenéd a mobilodon?
Az adatömörítés (mint a .zip vagy az .mp3) lelke gyakran egy fa. A Huffman-kódolás során a leggyakoribb karakterek a fa „tetején” rövid utat kapnak, így spórolva a tárhellyel.
Az élet fája
A biológusok a fajok evolúcióját filogenetikai fákkal modellezik. A levelek a mai fajok, az elágazások pedig a közös ősök, ahol az evolúció útja kettévált.