Dokaz s Prüferjevo bijektivno konstrukcijo

Cayleyevo formulo lahko opišemo z bijekcijo med množico dreves redan in množico tako imenovanih Prüferjevih zaporedij.

Definicija 22. Zaporedje z n−2ˇcleni, oblike(a₁,a₂, . . . ,a_n−2), kjer je a_i∈ {1, 2, . . . ,n}, n≥3, in so ponovitve med a_idovoljene, imenujemoPrüferjevo zaporedjealiPrüferjeva koda.

Definicija 23. Preslikavo med množico dreves reda n in množico Prüferjevih zaporedij ime-nujemoPrüferjeva konstrukcijain jo opišemo z naslednjim algoritmom:

• Izberemo list z najmanjšo oznako.

• Vozlišˇce, ki je sosednje listu, izbranemu v prvem koraku, zapišemo v zaporedje.

• Iz drevesa odstranimo list, izbran v prvem koraku.

• Prve tri korake ponavljamo, dokler nam v drevesu ne ostaneta le dve vozlišˇci.

Oˇcitno je, da je rezultat Prüferjeve konstrukcije Prüferjevo zaporedjea, saj smo na vsa-kem odn−2 korakov v zaporedje dali eno odn oznak. Tako je vseh možnih Prüferjevih zaporedij enakonⁿ⁻².

Vsako vozlišˇcev se v Prüferjevem zaporedju pojavi deg(v)−1 krat, poslediˇcno listov v za-poredju ni.

V prvem koraku po odstranitvi lista z najnižjo oznako vi v drevesuΓ, je drevoΓ −vi brez listav_i še vedno drevo. Ustreza mu Prüferjevo zaporedje drevesaΓ brez prvega ˇclenaa₁. Zgled 15. Poglejmo si Prüferjevo konstrukcijo na konkretnem primeru. Zapišimo Prüfer-jevo zaporedje po zgoraj opisanem algoritmu za drevo na Sliki 18.

Slika 18: Drevo s Prüferjevim zaporedjem(2, 3, 3, 2, 6, 6)

Drevo ima osem vozlišˇc, torej bo Prüferjevo zaporedje vsebovalo šest ˇclenov. Prvi ˇclen zaporedja je sosednje vozlišˇce lista z najmanjšo oznako - list z najmanjšo oznako je vozlišˇce 1, njegov sosed je vozlišˇce 2. Prvi ˇclen zaporedja je torej 2. Sedaj si mislimo, kot da vozlišˇca 1 ni veˇc v drevesu. List z najmanjšo oznako je tedaj 4, njegov sosed pa 3. Naslednji ˇclen v zaporedju je 3. Postopek nadaljujemo in dobimo Prüferjevo zaporedje(2, 3, 3, 2, 6, 6).

30

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

Trditev 10. Naj bo Prüferjeva konstrukcija preslikava med množico vseh dreves reda n in Prüferjevimi zaporedji. Tedaj je ta preslikava dobro definirana in bijektivna.

Dokaz. Da je Prüferjeva konstrukcija res bijektivna, bomo posebej dokazali injektivnost in surjektivnost z indukcijo nan. Najprej bomo dokazali injektivnost, da se razliˇcni drevesi slikata v razliˇcni Prüferjevi zaporedji. Zan =3 bo v Prüferjevem zaporedju le oznaka vo-zlišˇca stopnje 2, katero je v razliˇcnih drevesih razliˇcno oznaˇceno. Naj bosta sedajΓ1inΓ2

razliˇcni drevesi z množico vozlišˇcV ={v₁,v₂, . . . ,v_n}. Lista z najnižjo oznako naj bostav_i in vj. Obravnavali bomo tri primere:

• Ce jeˇ v_i =v_j, njuna soseda pa razliˇcna, sta prva ˇclena v Prüferjevih zaporedjih raz-liˇcna.

• Ce jeˇ vi6=vj, njuna soseda pa enaka, po 1<k ≤n−2 korakih zagotovo pride do tega, da sta soseda listov z najnižjo oznako vk-tem koraku razliˇcna, tako sta tudi Prüferjevi zaporedji razliˇcni.

• Ce jeˇ v_i = v_j in sta tudi njuna soseda enaka, po odstranitvi listov v prvem koraku dobimo manjši, a razliˇcni drevesiΓ₁⁰inΓ₂⁰(ker staΓ1inΓ2razliˇcni).

Injektivnost je s tem dokazana. Dokazati moramo še surjektivnost, da vsako Prüferjevo za-poredje dobimo iz nekega drevesa. Najprej dokažimo zan =3. V Prüferjevem zaporedju nastopa oznaka za notranje vozlišˇce, preostali dve oznaki oznaˇcujeta lista, ki sta povezana z notranjim vozlišˇcem. Naj bo sedaja = (a1,a2, . . . ,a_n−2)Prüferjevo zaporedje na abecedi {v₁,v₂, . . . ,v_n}in v_i list z najmanjšo oznako, ki ne nastopa va. Po predpostavki vemo, da Prüferjevo zaporedjea⁰ = (a2, . . . ,a_n−2)na abecedi{v₁,v₂, ...,v_n} \ {v_i}, ustreza drevesu Γ⁰. Ce sedaj v drevoˇ Γ⁰dodamo povezavovi ∼a1, dobimo drevo, ki mu ustreza Prüferjevo za-poredjea. Ker smo iz drevesa dobili Prüferjevo zaporedje, je s tem dokazana tudi surjek-tivnost.

Iz dokaza za surjektivnost lahko razberemo algoritem za Prüferjevo konstrukcijo dre-vesa iz danega Prüferjevega zaporedja. Drevo skonstruiramo po naslednjih korakih:

• Narišemon vozlišˇc in jih oznaˇcimo od 1 don. V nadaljevanju bo to naš tako imeno-van seznam.

• Poišˇcemo vozlišˇce z najmanjšo oznako v seznamu, ki ga ni v zaporedju, in prvo število v zaporedju. Ti dve vozlišˇci povežemo s povezavo.

• Iz seznama odstranimo vozlišˇce z najmanjšo oznako, ki ga ni v zaporedju in iz zapo-redja odstranimo prvi ˇclen. S tem se nam zmanjša seznam in skrajša zaporedje.

• Drugi in tretji korak ponovimo tolikokrat, dokler v seznamu ne ostaneta dve oznaˇceni vozlišˇci. Ti dve vozlišˇci povežemo med seboj in dobimo drevo.

Dokaz je povzet po[5], koraki Prüferjeve konstrukcije pa po[12].

Zgled 16. Iz Prüferjevega zaporedja (2, 3, 3, 2, 6, 6) skonstruirajmo drevo. Zaporedje ima šest ˇclenov, torej bo imelo drevo osem vozlišˇc. Narišimo seznam osmih vozlišˇc. Vozlišˇce z najmanjšo oznako, ki ga ni v zaporedju je 1, prvi ˇclen zaporedja je 2, torej ti dve vozlišˇci povežemo. Mislimo si, da vozlišˇca 1 ni veˇc na seznamu, v zaporedju pa ni veˇc prvega ˇclena 2. Sedaj je vozlišˇce z najmanjšo oznako, ki ni v zaporedju, vozlišˇce 4, povežemo ga z drugim ˇclenom v zaporedju, s 3. Korake ponavljamo. Ko nam v zaporedju zmanjka ˇclenov, nam v seznamu ostaneta še vozlišˇci 6 in 8, ki ju povežemo med seboj. Na Sliki 19 so prikazani posamezni koraki konstrukcije.

31

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Slika 19: Prüferjeva konstrukcija drevesa iz Prüferjevega zaporedja(2, 3, 3, 2, 6, 6) 3.2.2 Dokaz z dvojnim preštevanjem zakoreninjenih dreves

Aigner in Ziegler sta v[1]podala štiri razliˇcne dokaze Cayleyeve formule. Med njimi je do-kaz, ki ga je J. Pitman[4]oznaˇcil za najlepšega med vsemi dokazi Cayleyeve formule. Dokaz ne vsebuje nikakršne bijekcije ali rekurzije, le preštevanje tako imenovanih zakoreninjenih dreves na dva razliˇcna naˇcina.

Definicija 24. Zakoreninjeno drevoje usmerjeno drevo z oznaˇcenim vozlišˇcem, imenova-nimkoren. Vsaka povezava je usmerjena izven korena.

Definicija 25. Zakoreninjeni gozdje gozd, v katerem v vsaki od komponent izberemo koren.

Definiciji sta zapisani po[6].

Zgled 17. Na Sliki 20 je usmerjeno drevoT = (V,E)z množico vozlišˇcV ={1, 2, 3, 4, 5, 6, 7} in množico povezavE ={{2, 1},{2, 3},{3, 4},{5, 2},{5, 6},{6, 7}}. ˇCe vozlišˇce 5 izberemo za koren, je(T, 5)zakoreninjeno drevo. Koren je oznaˇcen z odebeljeno toˇcko, pušˇcice pa ozna-ˇcujejo smer povezav.

Slika 20: Primer zakoreninjenega drevesa

Prešteli bomo število razliˇcnih zaporedij usmerjenih povezav, ki jih lahko dodamo pra-znemu grafu zn vozlišˇci, da dobimo zakoreninjeno drevo, in obratno. Število takšnih za-poredij oznaˇcimo z oznakoN(T).

Dokaz. Število zaporedij N(T) bomo najprej prešteli tako, da bomo iz zakoreninjenega drevesa zn razliˇcnimi vozlišˇci z odstranjevanjem povezav dobili prazen graf. Pri tem mo-ramo omeniti, da vrstni red odstranjevanja povezav ni pomemben. Najprej momo-ramo izbrati enega izmed dreves redan, na izbiro jih imamoT(n), in ga zakoreniniti, kar lahko storimo

32

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

nan naˇcinov. V prvem koraku lahko odstranimo eno izmedn−1 povezav, v drugem eno izmed preostalihn−2 povezav in tako naprej do zadnje povezave. Dobimo, da je število takšnih zaporedij enako

N(T) =n T(n)(n−1)!.

V drugem naˇcinu pa bomo število zaporedijN(T)prešteli z dodajanjem povezav v pra-zni graf zn razliˇcnimi vozlišˇci. Prvo povezavo dobimo, ko eno izmedn vozlišˇc povežemo z vozlišˇcem, ki predstavlja koren in ga izberemo nan−1 naˇcinov. Za drugo povezavo izbe-remo neko vozlišˇce izmed vsehnvozlišˇc in ga povežemo z novim korenom, ki ga izberemo nan−2 naˇcinov. Na Sliki 21 je prikazana dodana povezava med katerim koli vozlišˇcem (ki je lahko tudi koren, izbran v prejšnjem koraku) in novim izbranim korenom.

Slika 21: Dodajanje povezave za zakoreninjeno drevo

Po n −1 korakih dodamo ustrezno število povezav, da dobimo zakoreninjeno drevo.

Takšnih možnih zaporedij je tako

N(T) =nⁿ⁻¹(n−1)!.

Ko izenaˇcimo število zaporedijN(T), dobimo

n T(n)(n−1)!=nⁿ⁻¹(n−1)!.

Iz tega sledi, da je število razliˇcnih oznaˇcenih dreves redan enako T(n) =nⁿ⁻².

3.2.3 Rekurzivna formula za število oznaˇcenih gozdov

Pri kombinatoriki in preštevanju je pogosta metoda dokazovanja dokazovanje z rekurzivno formulo. Za število oznaˇcenih gozdov je dokaz z rekurzijo opisan v[1].

Število oznaˇcenih gozdov redan sk drevesi, kjer jek≤n, bomo oznaˇcili z oznakoFn,k. Koliko je vseh takšnih gozdov, nam pove naslednja trditev.

Trditev 11. Število oznaˇcenih gozdov reda n s k drevesi, kjer velja1≤k ≤n , je enako Fn,k=k n^n−k−1.

Posledica 2. Število oznaˇcenih gozdov reda n z enim drevesom, je enako številu razliˇcnih dreves na n oznaˇcenih vozlišˇcih in velja

Fn,1=T(n) =nⁿ⁻². 33

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Podali bomo pomožno lemo, ki je ne bomo dokazali, nam bo pa prišla v pomoˇc pri dokazu Trditve 11.

Lema 1. Ce v drevesuˇ Γ = (V,E)odstranimo vozlišˇce v ∈V , kjer veljadeg(v) =i , dobimo i dreves.

Sedaj lahko dokažemo Trditev 11.

Dokaz. Naj bo oznaˇceni gozdF z množico vozlišˇcV ={v1,v2, . . . ,vk,vk+1, . . . ,vn}in sk dre-vesi. Vsakega od možnih oznaˇcenih gozdov redansk drevesi, dobimo tako, da

(i) izberemoi, 0≤i≤n−k;

(ii) za izbraniiizberemoisosedov vozlišˇcav₁izmed vozlišˇcv_k+1,v_k+2, . . . ,v_n, torej na ^n−k_i naˇcinov;

(iii) odstranimo vozlišˇcev1;

(iv) izberemo oznaˇceni gozd sk−1+i drevesi nan−1 vozlišˇcih, kar lahko naF_{n−1,k−1+i} naˇcinov.

Slika 22: GozdF, v katerem je vozlišˇcev₁povezano zi vozlišˇci Od tod sledi rekurzivna zveza

V zvezi uporabimo indukcijsko predpostavko zan−1 ink−1+i, ter zapišimo F_n,k=

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

kjer smo prvo vrstico razstavili na dva ˇclena. V naslednjem koraku bomo uporabili binom-ski izrek v drugi ˇclen pa bomo vstavili

n−k

3.2.4 Dokaz s Kirchhoffovo zvezo med matrikami in drevesi

Naslednji dokaz, povzet po[1]in[8], temelji na linearni algebri in prikazuje kombinatoriˇcen pomen determinant. Preden bomo spoznali tako imenovani Kirchhoffov izrek, ki podaja presenetljivo zvezo med determinantami matrik in drevesi, si poglejmo še nekaj definicij, povzetih po[2], ki jih bomo potrebovali.

Definicija 26. Naj bo~Γ = (V,E~)usmerjen graf z množico vozlišˇc V ={v1,v2, . . . ,vn}in mno-žico povezavE~={e~₁,e~₂, . . . ,e~_m}. Incidenˇcna matrikagrafa~Γ je matrika D velikosti n×m , kjer je element d_i,j enak

d_i,j =

Dogovorimo se, da bo matrikaA_{i j}oznaˇcevala matrikoA, ki smo ji odstranilii-to vrstico inj-ti stolpec. Konˇcno lahko podamo tudi za dokaz Cayleyeve formule kljuˇcen Kirchhoffov izrek.

35

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Izrek 3(Kirchhoffov izrek). Za vsak grafΓ reda n je število oznaˇcenih vpetih dreves T(n) enako

T(n) =detQi i,

kjer je matrika Qi iLaplaceova matrika grafaΓ, brez i -te vrstice in i -tega stolpca.

Posledica 3. Poseben primer Kirchhoffovega izreka je število oznaˇcenih vpetih dreves v pol-nem grafu Kn. Velja naslednja enakost

T(n) =detQ_{i i}(K_n) =nⁿ⁻².

Dokaz. Za dokaz Posledice 3 najprej zapišimo Laplaceovo matrikoQ(K_n)polnega grafaK_n, velikosti n ×n. Na diagonali bodo vsi elementi enaki n−1, saj so vsa vozlišˇca tolikšne stopnje. Ostali elementi bodo enaki−1, ker je vsako vozlišˇce sosednje s vsakim vozlišˇcem.

Laplaceova matrika je tako

Število vpetih dreves bomo dobili, ko bomo izraˇcunali determinanto matrikeQ_{i i}(K_n), zai bomo vzeli 1. MatrikaQ11(Kn), velikosti(n−1)×(n−1)je

Najenostavneje nam bo, ˇce matriko preoblikujemo tako, da bodo le na diagonali neni-ˇcelni elementi. V prvem koraku od vseh vrstic odštejemo prvo. V drugem koraku prvemu stolpcu prištejemo ostale stolpce, v tretjem koraku pa prvi stolpec prištejemo vsem ostalim stolpcem. Zapišimo

Determinanta matrikeQ₁₁(K_n)je enaka

det(Q₁₁(K_n)) =T(n) =nⁿ⁻².

Preden bomo dokazali Kirchhoffov izrek, si poglejmo še dve pomožni lemi in Binet-Cauchyjev izrek. Kljub temu, da nam Kirchhoffov izrek poda rezultat neodvisen od usme-ritve grafa, bomo za vmesne korake potrebovali usmerjeni graf.

36

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

Lema 2. Naj bo usmerjeni graf~Γ = (V,E~)z množico vozlišˇc V ={v₁,v₂, . . . ,v_n}in množico povezavE~={e~₁,e~₂, . . . ,e~_m}. Naj bodo matrike Q Laplaceova matrika, matrika Q_{i i} Laplace-ova matrika brez i -te vrstice in i -tega stolpca, matrika D incidenˇcna matrika in matrika Di

incidenˇcna matrika brez i -te vrstice, usmerjenega grafa~Γ. Tedaj veljata enakosti D D^T =Q in D_iD_i^T =Q_{i i}.

Dokaz. Incidenˇcna matrikaD dimenzijen×m usmerjenega grafa~Γ ima v vsakem odm stolpcev natanko eno 1 in eno -1, ostali elementi so enaki 0. V vsaki vrsticii pa ima toliko neniˇcelnih elementov, kolikor je stopnja vozlišˇcavi. Po definiciji množenja matrik je ele-mentq_{i j} v produktuD D^T enakPm

k=1d_{i k}d_{j k}. Zai = j je produktd_{i k}d_{j k} =d_{i k}² enak 1 ali 0, vsota teh produktov pa enaka stopnji vozlišˇcavi. Na diagonali matrike tako dobimo sto-pnje vozlišˇc. V primeru, dai in j nista enaka, je produkt neniˇcelen le v primeru, ko stavi

inv_j krajišˇca povezave oziroma sta si sosednja, to se zgodi v najveˇc enem izmed produktov di kdi j, ker ima vsaka povezava le dve krajišˇci, oznaˇceni z 1 in−1. Vsota produktov in s tem elementqi j je tako enak 0 ali−1. Produkt matrikD inD^T je res enak Laplaceovi matriki Q - matrika je velikostin×n, v njej pa nastopajo elementiq_{i j} =−1, ˇce sta vozlišˇciv_i inv_j sosednji, sicer so enakiqi j =0, ter stopnje vozlišˇc po diagonali,qi i=deg(vi).

Pri drugi enakosti do elementovq⁰v produktu D_iD_i^T pridemo po definiciji produkta matrik in podobnem razmisleku kot zgoraj. Premisliti moramo le, zakaj je produkt enak matrikiQi i. Da dobimo matrikoDi, matrikiD odstranimoi-to vrstico, ki nam pove, katerih povezav je vozlišˇcev_ikrajišˇce in poslediˇcno kolikšne stopnje je. Pri produktuD_iD_i^T tako ni elementaq_{i i}⁰ =Pm

k=1di kdk i, ki je enak stopnji vozlišˇcavi, in ni elementovq_{i j}⁰ =Pm

k=1di kdj k, ki bi nam “povedali” ali je vozlišˇcevi sosednje z vozlišˇcemvj.

Naslednja lema povezuje vpeta drevesa in determinante matrik.

Lema 3. Naj bo grafΓ= (V,E)in T = (V⁰,E⁰)njegov podgraf z množico vozlišˇc V⁰={v₁,v₂, . . . ,v_n} in množico povezav E⁰={e1,e2, . . . ,e_n−1}. Z oznakoT oznaˇcimo poljubno usmeritev grafa~ T . Za grafT naj bo matrika C incidenˇcna matrika, matrika C pa incidenˇcna matrika brez~ prve vrstice. Potem velja

det(C) ={−1, 0, 1}

in jedet(C)neniˇcelna natanko tedaj, ko je T vpeto drevo grafaΓ. Dokaz. Lemo bomo dokazali z indukcijo nan.

Najprej vzemimon =2. DrevoT~ima eno povezavo, matrika C pa en sam element, ki je enak 1 ali−1, odvisno od smeri povezave. Determinanta detC je tako enaka 1 ali−1,T pa je res vpeto drevo na dveh vozlišˇcih.

Naj bo sedajn >2. Tu bomo loˇcili dva primera glede na to, katero od vozlišˇcv₂, . . . ,v_n vT je stopnje 1. Brez škode za splošnost privzemimo, da je vozlišˇcev_n stopnje 1. To voz-lišˇce pripada eni sami povezavie~k. Iz tega sledi, da ima matrikaC v zadnji vrstici vk-tem stolpcu le en neniˇcelni element. ˇCe izraˇcunamo determinanto matrikeC po(n−1)-vrstici ink-tem stolpcu, dobimo|detC|=|detC_n−1,k|. Naj bo sedaj usmerjeni grafT~⁰grafT~brez vozlišˇcavn in povezavee~k. MatrikaC⁰ je njegova incidenˇcna matrika,C⁰ pa matrika, ko incidenˇcni matriki odstranimo vrstico. Ta je kar enaka matrikiC_n−1,k. Po indukcijski pred-postavki vemo, da je|detC⁰|enaka 1 ali 0 glede na to, ali jeT⁰vpeto drevo ali ne. Ker smo izT odstranili vozlišˇce stopnje 1, jeT drevo samo ˇce jeT⁰vpeto drevo.

37

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Ce nobeno od vozlišˇcˇ v₂, v₃, . . . ,v_n ni stopnje 1, mora imetiT izolirano vozlišˇce, da bi veljali Lema o rokovanju in Trditev 3. To pomeni, da je eno vozlišˇce stopnje 0 in takoT ni povezan. Tedaj bi morala biti determinantaC enaka 0. V matriki sta na mestu tega vozlišˇca nek stolpec in neka vrstica s samimi niˇcelnimi elementi. ˇCe izraˇcunamo determinanto ma-trike po tem stolpcu in tej vrstici, je detC =0. Lahko bi bilo na primer vozlišˇcev₁stopnje 1, ostala vozlišˇca pa vsaj stopnje 2, vendar v tem primeru ne bi veljala Lema o rokovanju, P

v∈Vdeg(v) =1+2(n−1)6=2(n−1)=2|E|.

Dve lemi, ki nam bosta koristili pri dokazu, smo že spoznali in dokazali. ˇCaka nas še Binet-Cauchyjev izrek in posledica izreka.

Izrek 4(Binet-Cauchyjev izrek). Naj bo matrika A velikosti n×m , kjer je n ≤m . Potem lahko z odstranitvijo m−n stolpcev izmed m možnih, dobimo kvadratno matriko. Naj mno-žica S predstavlja vse možne naˇcine, da izmed m možnih stolpcev izberemo m−n stolpcev (torej na ^m_n

naˇcinov), in za vsak s ∈S naj bo As ustrezna podmatrika matrike A, v kateri te stolpce odstranimo. Matrika B naj bo matrika velikosti m×n , kjer m ≥n , matrika B_s pa ustrezna podmatrika matrike B , v kateri namesto stolpcev odstranimo ustrezne vrstice.

Potem velja zveza

det(AB) =X

s∈S

detAsdetBs.

Posledica 4. Naj bo A poljubna matrika, definirana kot v Binet-Cauchyjevem izreku, ma-trika A^T pa njena transponiranka, potem velja zveza

det(AA^T) =X

Binet-Cauchyjevega izreka in njegove posledice ne bomo dokazali, bralec si dokaz lahko ogleda v[8]. Konˇcno pa si lahko pogledamo dokaz Kirchhoffovega izreka.

Dokaz. Po predpostavki je

T(n) =detQ_{i i}.

V to enakost vstavimoQ_{i i}=D_iD_i^T, kar velja po Lemi 2. Dobimo T_n=detD_iD_i^T.

Vpeto drevo v grafu ima morda kakšno povezavo manj kot sam graf, zato ima incidenˇcna matrika drevesa, matrika D_s, ustrezno število stolpcev manj. Binet-Cauchyjev izrek nas pripelje do rešitve

T(n) =X

s∈S

det(D_s)²,

kjer je vsota kvadratov determinant po razliˇcnihs∈S,Sje množica vseh možnih naˇcinov da odstranimosstolpcev, enaka številu razliˇcnih vpetih dreves, saj je po Lemi 3 determinanta enaka det(D_s) ={−1, 0, 1}in je neniˇcelna le v primeru, ko je drevo vpeto drevo.

38

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

4 Verjetnost vpetih dreves v polnem grafu

Prišli smo do kljuˇcnega problema diplomskega dela. Denimo, da imamo poln grafK_n in v njem izbiramo drevesa nak vozlišˇcih, kjer je 1≤k≤n. Zanima nas, kolikšna je verjetnost, da izberemo vpeto drevo. Pri tem predpostavimo, da je verjetnost, da izberemo katero koli drevo, enaka za vsa drevesa. Problem spada med mlajše probleme v matematiki, v ˇclanku [3]iz leta 2015 so ga predstavili A. Chin in ostali.

Za izraˇcun verjetnosti bomo potrebovali število vseh oznaˇcenih dreves v polnem grafu in ne le vpetih, katerih število že poznamo. O številu vseh razliˇcnih dreves nam pove nasle-dnja trditev.

Trditev 12. Naj bo K_n polni graf na n oznaˇcenih vozlišˇcih. Vseh razliˇcnih dreves v grafu K_n je enako vsemi oznaˇcenimin vozlišˇci, kar lahko storimo na ⁿ_k

razliˇcnih naˇcinov. Za vsakk je na oznaˇcenihk vozlišˇcih po Cayleyevem izrekuk^k−2razliˇcnih dreves. Od tod sledi, da je vseh oznaˇcenih dreves v polnem grafu enakoPn

k=1 n k

k^k−2. Nekaj teh števil poglejmo v naslednjem zgledu.

Zgled 18. V polnem grafuK2za vrednostk lahko izberemok =1 ali k =2. ˇCe je k =1, dobimo dve razliˇcni drevesi. V primeru, ko jek =2, pa dobimo eno drevo. Skupaj torej 3 razliˇcna drevesa. Za polni grafK₃so vsa razliˇcna oznaˇcena drevesa prikazana na Sliki 23, za vrednosti odn = 3 don = 6 pa so števila razliˇcnih oznaˇcenih dreves v polnem grafu zapisana v Tabeli 2.

Slika 23: Vsa razliˇcna oznaˇcena drevesa vK₃

n k Pn

Tabela 2: Število razliˇcnih oznaˇcenih dreves v polnem grafu od reda 3 do reda 6 39

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Verjetnost, da v polnem grafu izberemo vpeti graf, izraˇcunamo kot razmerje med šte-vilom vpetih dreves v oznaˇcenem polnem grafu in štešte-vilom vseh dreves v polnem grafu. V splošnem je pri vsaki vrednostin verjetnost razliˇcna.

Zgled 19. Poglejmo si nekaj izraˇcunanih vrednosti verjetnosti, kjer so v Tabeli 3 izraˇcunane za vrednostin od 1 do 20, v Tabeli 4 pa za veˇcje vrednostin.

Tabela 3: Izraˇcunana verjetnost za vrednostin od 1 do 20

n p_n

O tem, kaj se dogaja z verjetnostjop_n, ko gre število oznaˇcenih vozlišˇc ˇcez vse meje, nam pove naslednji izrek.

Izrek 5(Chin, A., Gordon, G., MacPhee, K., Vincent, C. (2015)). Denimo, da med vsemi dre-vesi v polnem grafu reda n izberemo nakljuˇcno drevo, pri ˇcemer so vse izbire enako verjetne.

Potem je limitna vrednost verjetnosti, da je izbrano drevo vpeto, ko gre vrednost n proti ne-skonˇcno, enaka

n→∞lim p_n= (1 e)^e1. Dokaz. Verjetnostpn izraˇcunamo kot

pn= nⁿ⁻²

Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko

V nadaljevanju bomo obravnavali imenovalec ulomka, najprej pa si poglejmo razmerje med dvema zaporednima ˇclenoma v vsoti v imenovalcu,

T(k+1)

Po uporabi definicije binomskega simbola in po okrajšanju ˇclenov dobimo T(k+1)

T(k) = (n−k)(k+1 k )^k−2.

Ko gren proti neskonˇcno in se muk približuje, ocenimo da jen−k ≈1. Lahko zapišemo približek

T(k+1)

T(k) ≈(k+1 k )^k−2 in si pogledamo limito, ko grek proti neskonˇcno,

klim→∞(k+1

Za dovolj velikk ink<n, je razmerje dveh zaporednih ˇclenov približno T(k+1) Sedaj lahko zapišemo vsotoPn

k=1T(k), ki nastopa v imenovalcu, kot

Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta

Iz tega sledi, da je

n

X

k=1

T(k)≈T(n)(1+1

e +. . .+ 1

k!e^k +. . .+ 1

(n−1)!eⁿ⁻¹)≈T(n) Xn−1

k=0

1 k!e^k.

Na tem mestu nam bo koristilaTaylorjeva vrsta. To je potenˇcna vrsta neskonˇcno od-vedljive funkcije. ˇCe funkcijoe^xodvajamo okoli toˇckex=0, dobimo Taylorjevo vrsto

e^x = X∞ n=0

xⁿ n!. Ce v Taylorjevi vrsti zaˇ x vzamemo ¹_e, dobimo

e^1e = X∞ n=0

1 n!eⁿ.

Vrnimo se nazaj na verjetnost. ˇCe ponovno zapišemopn, dobimo pn≈ T(n)

T(n)e^e1 = 1 e^e1 = (1

e)^e1.

Kljuˇcno vprašanje, ki smo si ga zastavili, smo razrešili. Problem bi si lahko zastavili dru-gaˇce in si ga otežili. Namesto, da je verjetnost, da izberemo nakljuˇcno drevo, enaka za vsa drevesa, bi bila lahko odvisna od števila povezav, ki jih premore izbrano drevo. Tega pro-blema ne bomo obravnavali, bralec pa se v[3]lahko prepriˇca, da je rešitev oteženega

Kljuˇcno vprašanje, ki smo si ga zastavili, smo razrešili. Problem bi si lahko zastavili dru-gaˇce in si ga otežili. Namesto, da je verjetnost, da izberemo nakljuˇcno drevo, enaka za vsa drevesa, bi bila lahko odvisna od števila povezav, ki jih premore izbrano drevo. Tega pro-blema ne bomo obravnavali, bralec pa se v[3]lahko prepriˇca, da je rešitev oteženega

In document JERA STOJKO (Strani 30-0)