2. Fák tulajdonságai
Becslés összefüggő gráf, illetve körmentes gráf éleinek számára. Fa fogalma, fák egyszerű tulajdonságai. Feszítőfa fogalma, annak létezése. Szélességi bejárás (BFS), annak lépésszáma, BFS-fa.
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!
Élszám-becslések és a fokozatos élhozzáadás
Legyen $G$ egy $n$ csúcsú, $m$ élű gráf. Ekkor:
(i) ha $G$ összefüggő, akkor $m \geq n - 1$;
(ii) ha $G$ körmentes, akkor $m \leq n - 1$;
(iii) ha $G$ fa, akkor $m = n - 1$.
Bizonyítás: Tekintsük a folyamatot, ahol fokozatosan adunk hozzá éleket az $n$ csúcsú üres (élmentes) gráfból kiindulva. Minden egyes új él felvételekor pontosan két eset lehetséges:
- (a) eset: Az új él két különböző komponenst köt össze $\rightarrow$ a komponensszám pontosan eggyel csökken.
- (b) eset: A két végpont már azonos komponensben van $\rightarrow$ a komponensszám nem változik, de egy új kör keletkezik.
(i) Ahhoz, hogy a gráf összefüggővé váljon (azaz a kezdeti $n$ darab komponensből $1$ darab maradjon), pontosan $n-1$ darab komponensszám-csökkentés szükséges, amihez legalább $n-1$ darab $(a)$ típusú él kell. Mivel emellett tetszőleges számú $(b)$ típusú él is bekerülhetett, így: $m \geq n - 1$.
(ii) Ha a gráf körmentes, akkor a $(b)$ eset a felépítés során egyszer sem fordulhat elő (hiszen az azonnal kört hozna létre). Így kizárólag $(a)$ típusú lépéseink lehetnek. Mivel a komponensek száma nem csökkenhet $1$ alá, legfeljebb $n-1$ darab élt adhatunk hozzá, azaz: $m \leq n - 1$.
(iii) Mivel a fa definíció szerint egyszerre összefüggő és körmentes, az (i) és (ii) egyenlőtlenségek egyidejű fennállásának közvetlen következményeként adódik, hogy: $m = n - 1$.
∎
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.
Szélességi bejárás (BFS)
Az algoritmus leírása
A szélességi bejárás (Breadth-First Search) egy $G = (V, E)$ gráfban egy kijelölt $s \in V$ forráscsúcsból kiindulva, rétegenként (éltávolság szerint növekvő sorrendben) haladva térképezi fel a csúcsokat. Az algoritmus egy FIFO (First-In-First-Out) sort használ a soron következő elemek kezelésére.
// BFS ALGORITMUS
Bemenet: G = (V, E) gráf, s ∈ V forráscsúcs.
Nyilvántartás: táv(v) = s-től való (él)távolság; előző(v) = megelőző csúcs a legrövidebb úton; L = FIFO sor.
1. L ← (s); táv(s) ← 0; minden v ≠ s-re: táv(v) ← ∞
2. ciklus: amíg L nem üres
a. aktív ← L első eleme; törlés L-ből
b. ciklus: v végigfut aktív minden szomszédján
ha táv(v) == ∞:
v → L végére;
táv(v) ← táv(aktív) + 1;
előző(v) ← aktív
Az $előző(v)$ mutatók által meghatározott $\{előző(v), v\}$ élek ($v \neq s$) egy BFS-fát alkotnak, amely $G$ összefüggősége esetén feszítőfája $G$-nek.
Az $F$-beli, $s$-et $v$-vel összekötő út a legrövidebb $s-v$ utak egyike.
A bejárás időigénye alapvetően meghatározza a választott adatszerkezet:
$O(n + m)$
Mivel minden csúcsot legfeljebb egyszer teszünk be a sorba, és a lépés során csak az adott csúcs él-listáját olvassuk át, a futásidő lineáris az élek és csúcsok számában.
$O(n^2)$
Minden egyes sorból kivett aktív csúcs szomszédainak felderítéséhez a mátrix teljes sorát (azaz $n$ darab elemet) végig kell vizsgálni, függetlenül a valós élszámtól.
Ö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.