UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
JERA STOJKO
PREŠTEVANJE DREVES DIPLOMSKO DELO
LJUBLJANA, 2017
UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
DVOPREDMETNI U ˇ CITELJ: FIZIKA - MATEMATIKA
JERA STOJKO
Mentor: doc. dr. Boštjan Kuzman
PREŠTEVANJE DREVES DIPLOMSKO DELO
LJUBLJANA, 2017
POVZETEK
V teoriji grafov drevo pomeni kombinatoriˇcen objekt, ki ga obiˇcajno definiramo kot po- vezan graf brez ciklov. V nalogi je predstavljen problem preštevanja razliˇcnih dreves s po- danim številom vozlišˇc. Podani so štirje dokazi znamenitega Cayleyevega izreka za število oznaˇcenih dreves: dokaz s Prüferjevo bijektivno konstrukcijo, dokaz s preštevanjem zako- reninjenih dreves na dva naˇcina J. Pitmana, dokaz z rekurzivno formulo za število oznaˇce- nih gozdov in dokaz z uporabo Kirchhoffove zveze med determinantami matrik in vpetimi drevesi. V zadnjem delu je izpeljan novejši rezultat A. China in ostalih, o verjetnosti, da je nakljuˇcno izbrano drevo v polnem grafu vpeto drevo. Posebej je obravnavano obnašanje limitne vrednosti verjetnosti, ko število vozlišˇc polnega grafa raste ˇcez vse meje. Dobljeni rezultat je presenetljiv in lep.
Kljuˇcne besede:
Graf, polni graf, drevo, vpeto drevo, preštevanje, Cayleyev izrek, verjetnost.
ABSTRACT
In graph theory, trees are combinatorial objects usually defined as connected graphs without cycles. In this thesis, the problem of counting different trees with a given number of vertices is presented. Four proofs of a celebrated theorem on the number of labeled trees by A. Cayley are given: by using a bijective construction due to H. Prüfer, by double coun- ting of labeled rooted trees due to J. Pitman, by establishing a recursion on the number of labeled forests, and finally, by applying a relation between determinants and spanning trees due to H. Kirchhoff. In the final part, a recent result by A. Chin et al. is presented on the probability that a randomly picked tree in a complete graph is a spanning tree. In particular, the limit of this value as the number of vertices approaches infinity is observed.
The result obtained is both surprising and beautiful.
Key words:
Graph, complete graph, tree, spanning tree, enumerating, Cayley’s Theorem, probability.
Kazalo
1 Uvod 15
2 Osnovno o grafih 16
2.1 Graf in podgraf . . . 16
2.2 Nekaj družin grafov . . . 19
2.3 Drevesa . . . 20
2.4 Izomorfnost grafov . . . 24
3 Preštevanje dreves in Cayleyev izrek 25 3.1 Problem preštevanja neizomorfnih dreves . . . 25
3.2 Cayleyeva formula za število oznaˇcenih dreves . . . 28
3.2.1 Dokaz s Prüferjevo bijektivno konstrukcijo . . . 30
3.2.2 Dokaz z dvojnim preštevanjem zakoreninjenih dreves . . . 32
3.2.3 Rekurzivna formula za število oznaˇcenih gozdov . . . 33
3.2.4 Dokaz s Kirchhoffovo zvezo med matrikami in drevesi . . . 35
4 Verjetnost vpetih dreves v polnem grafu 39
Slike
1 Primer grafa reda 7 . . . 16
2 Primer 4-regularnega in kubiˇcnega grafa . . . 17
3 Dva podgrafa in primer grafa, ki ni podgraf grafa na Sliki 1 . . . 17
4 Primer nepovezanega grafa reda 8 . . . 19
5 Poti reda 2, 3, 4 in skica poti redan . . . 19
6 Cikel reda 7 . . . 19
7 Polni grafi do reda 6 . . . 20
8 Primer polnega dvodelnega grafa in zvezde . . . 20
9 Drevo reda 10 . . . 20
10 Primer gozda reda 15 . . . 22
11 Primer grafa reda 9 in dveh njegovih vpetih dreves . . . 24
12 Izomorfna grafa reda 4 . . . 24
13 Tri razliˇcna oznaˇcena drevesa reda 5 . . . 25
14 Neizomorfna drevesa reda 6 . . . 25
15 Neizomorfna drevesa do reda 5 . . . 26
16 Oznaˇcena drevesa reda 3 . . . 28
17 Oznaˇcena drevesa reda 4 . . . 28
18 Drevo s Prüferjevim zaporedjem(2, 3, 3, 2, 6, 6) . . . 30
19 Prüferjeva konstrukcija drevesa iz Prüferjevega zaporedja(2, 3, 3, 2, 6, 6) . . . 32
20 Primer zakoreninjenega drevesa . . . 32
21 Dodajanje povezave za zakoreninjeno drevo . . . 33
22 GozdF, v katerem je vozlišˇcev1povezano zi vozlišˇci . . . 34
23 Vsa razliˇcna oznaˇcena drevesa vK3 . . . 39
Tabele
1 Števila neizomorfnih dreves redan, (vir zaporedje A000055 v[11]) . . . 27
2 Število razliˇcnih oznaˇcenih dreves v polnem grafu od reda 3 do reda 6 . . . 39
3 Izraˇcunana verjetnost za vrednostin od 1 do 20 . . . 40
4 Verjetnost za veˇcje vrednostin, (vir[3]) . . . 40
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
1 Uvod
Pred vami je diplomsko delo, ki sodi v teorijo grafov. Grafe si najlažje predstavljamo kot vozlišˇca, ki jih med seboj povežemo. Teh vozlišˇc je lahko poljubno mnogo, lahko so ozna- ˇcena ali ne in so razliˇcno povezana. Spoznali se bomo z razliˇcnimi grafovskimi družinami, predvsem pomembna pa bodo za nas drevesa. Drevesa in grafi so objekti, ki nimajo po- mena le v matematiki. Najrazliˇcnejše probleme lahko prevedemo in obravnavamo v jeziku teorije grafov. Na primer, pri kemiji so molekule povezane v razne strukture, v družinskem drevesu povezava med dvema osebama pomeni sorodstveno vez, med šestimi ljudmi so zagotovo trije, ki se med seboj poznajo ali pa so trije, ki se med seboj ne poznajo.
Omenili bomo do sedaj še ne popolno rešen problem preštevanja neizomorfnih dre- ves. Presenetljivo je, da do danes poznamo natanˇcno število neizomorfnih dreves le za nekaj redov. Bolj se bomo posvetili preštevanju razliˇcnih dreves zn oznaˇcenimi vozlišˇci in znamenitemu Cayleyevemu izreku. Zanj obstaja veˇc razliˇcnih dokazov iz razliˇcnih mate- matiˇcnih smeri, v delu bomo predstavili le štiri najbolj znane in zanimive.
Kljuˇcen problem diplomskega dela je problem, ki so ga nedavno predstavili A. Chin in ostali v ˇclanku Pick a Tree - Any Tree. Med vsemi oznaˇcenimi drevesi v polnem grafu z n vozlišˇci bomo nakljuˇcno izbirali drevesa, nas pa bo zanimala verjetnost, da bo izbrano drevo vpeto drevo. Rešitev problema, torej limitna vrednost verjetnosti, ko število vozlišˇc v polnem grafu raste proti neskonˇcnosti, je presenetljivo lepa.
15
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
2 Osnovno o grafih
Za lažje branje v nadaljevanju bomo v tem razdelku zbrali nekaj osnovnih definicij o grafih.
Vse definicije, leme in trditve v tem poglavju so povzete iz[10]. V primeru, da katera ni, bo posebej navedeno.
2.1 Graf in podgraf
V nalogi bomo obravnavali grafe, ki jih definiramo na naslednji naˇcin.
Definicija 1. Neusmerjen enostaven grafΓ = (V,E)je urejeni par, ki ga sestavljata (i) poljubna neprazna množica vozlišˇc V ,
(ii) množica povezav E , katere elementi so neurejeni pari{u,v}paroma razliˇcnih vozlišˇc u,v∈V .
V teoriji grafov sicer obravnavamo tudi drugaˇcne grafe. Pri nekaterih dopušˇcamo zanke (povezave med dvema enakima vozlišˇcema), veˇckratne povezave med istim parom voz- lišˇc (multigrafi), ali pa so vse povezave usmerjene od enega vozlišˇca k drugemu (usmer- jeni grafialidigrafi). V naši nalogi bo beseda graf pomenila enostaven neusmerjen graf s konˇcno množico vozlišˇc, v drugih primerih bo to posebej poudarjeno.
Definicija 2. Naj bo e ∈ E povezava grafaΓ = (V,E). ˇCe je e ={u,v}, za neka u,v ∈ V , reˇcemo, da sta vozlišˇci u in v sosednji, kar zapišemo kot u ∼ v ali u v . Ker govorimo o neusmerjenih grafih, zapisa u v in v u pomenita enako. Reˇcemo tudi, da sta vozlišˇci u in v krajišˇcipovezave e .
Kadar bomo hkrati obravnavali veˇc grafov, bomo z imenom grafa dodatno oznaˇcili ustre- zne množice in relacije. Na primer, množica vozlišˇcV(Γ)in povezavau∼Γv v grafuΓ.
Grafi so abstraktni objekti, ki jih definiramo s pomoˇcjo množic. Vˇcasih jih upodobimo tudi na ravnini ali v prostoru. Pri tem vozlišˇca predstavimo s toˇckami, povezave pa s krivu- ljami, ki te toˇcke povezujejo. Sama oblika krivulj pri tem ni pomembna.
Slika 1: Primer grafa reda 7
Zgled 1. Na Sliki 1 je graf z množico vozlišˇcV = {a,b,c,d,e,f,g}in množico povezav E ={a b,a c,a d,b c,b d,c d,c e,e g,e f }. Pri tem omenimo, da preseˇcišˇce povezava c in b d ne predstavlja vozlišˇca. Povezavob d bi lahko s krivuljo narisali tako, da ne bi sekala povezavea c.
Definicija 3. Kardinalnosti množice vozlišˇc|V|grafaΓ = (V,E)reˇcemoredgrafa.
Graf na Sliki 1 ima sedem vozlišˇc, torej je reda 7.
16
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
Definicija 4. Naj boΓ= (V,E)graf in v ∈V neko vozlišˇce. Tedaj množici N(v) ={u∈V;v∼u}
pravimookolicavozlišˇca v , njeni kardinalnosti|N(v)|pastopnjavozlišˇca, kar oznaˇcimo z deg(v). Z oznako
δ(Γ) =min{deg(v);v∈V} oznaˇcimominimalno stopnjo, z oznako
∆(Γ) =max{deg(v);v∈V} pamaksimalno stopnjografa.
Oˇcitno je, da ima graf na Sliki 1 minimalno stopnjo ena in maksimalno stopnjo štiri.
Definicija 5. GrafΓ = (V,E) jeregularen, ko velja enakostδ(Γ) = ∆(Γ). To pomeni, da so vsa vozlišˇca v grafu enake stopnje. Ko jeδ(Γ) = ∆(Γ) = k , je grafk-regularen. Obiˇcajno 3-regularnemu grafu reˇcemokubiˇcen graf.
Slika 2: Primer 4-regularnega in kubiˇcnega grafa
Definicija 6. Naj boΓ = (V,E)neki graf. ˇCe jeΓ0= (V0,E0)tak graf, da je V0⊆V in E0⊆E , potem reˇcemo, da je grafΓ0podgrafgrafaΓ. ˇCe sta množici vozlišˇc V in V0enaki, jeΓ0vpeti podgrafgrafaΓ.
Slika 3: Dva podgrafa in primer grafa, ki ni podgraf grafa na Sliki 1
Zgled 2. Na Sliki 3 so prikazani trije grafi. Graf na levi je podgraf grafa na Sliki 1, vendar ni vpeti, ker ne vsebuje vseh vozlišˇc. Srednji graf ima vsa vozlišˇca kot graf na Sliki 1, zato je vpeti podgraf. Desni graf vsebuje povezavid f inb g, ki ju graf na Sliki 1 ne, zato ni njegov podgraf.
Definicija 7. Komplement grafaΓ= (V,E)je grafΓ= (V,E0)z isto množico vozlišˇc kot zaˇcetni graf, njegova množica povezav pa je
E0={{u,v};u,v∈V,{u,v}∈/E},
torej sta poljubni njegovi vozlišˇci sosednji natanko tedaj, ko v zaˇcetnem grafu nista.
17
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
Za konˇcne grafe velja preprosta zveza med stopnjami vozlišˇc in številom povezav. Opi- suje jo naslednja trditev.
Trditev 1(Lema o rokovanju). Naj bo Γ = (V,E) konˇcni graf. Tedaj je vsota stopenj vseh vozlišˇc enaka dvakratniku števila povezav,
X
v∈V
deg(v) =2|E|.
Dokaz. Za vozlišˇcev stopnja deg(v)pomeni število povezav, ki imajov za eno od krajišˇc.
Ce seštejemo stopnje vseh vozlišˇc, smo vsako povezavo prešteli natanko dvakrat, saj imaˇ vsaka povezava dve krajišˇci.
Posledica 1. Naj boΓ = (V,E)konˇcni graf. Število lihih vozlišˇc v grafuΓ je sodo.
Dokaz. Vsota stopenj vseh vozlišˇc v grafuΓ je po Lemi o rokovanju enaka sodemu številu.
Vsota sodih stopenj vozlišˇc bo soda ne glede na to, koliko bo takšnih vozlišˇc. Torej mora biti tudi vsota stopenj lihih vozlišˇc soda, to bo veljalo le v primeru, ko bo lihih vozlišˇc sodo mnogo.
Ko govorimo o lastnostih grafov, omenimo še nekaj o sprehodih, poteh in ciklih v grafih ter o povezanosti grafov.
Definicija 8. Naj boΓ graf. Zaporedje vozlišˇc(v0,v1,v2, . . . ,vn)je tedajsprehoddolžine n , ˇce za vsak i ,1≤i ≤n , velja vi−1∼vi. Posebej, sprehod(v0,v1,v2, . . . ,vn)v grafuΓ je:
(i) enostaven sprehod, ˇce so vse povezave v sprehodu paroma razliˇcne;
(ii) pot, ˇce so vozlišˇca paroma razliˇcna;
(iii) obhod, ˇce sta prvo in zadnje vozlišˇce enaki, v0=vn;
(iv) cikeldolžine n ali n -cikel, ˇce sta prvo in zadnje vozlišˇce enaki, v0=vn, ostala vozlišˇca pa so paroma razliˇcna.
Zgled 3. Ponovno si poglejmo graf na Sliki 1. Zaporedje vozlišˇc(g,e,c,b,d,c)je sprehod, vendar ni enostaven, saj se vozlišˇcec ponovi. Enostaven sprehod je na primer(f,e,c,a,d), kar je tudi pot. Za primer obhoda navedimo (b,a,d,c,e,c,b), za primer cikla, oziroma natanˇcneje 4-cikla, pa(a,b,c,d,a).
Definicija 9. Naj bosta u in v vozlišˇci grafaΓ. Tedaj je vozlišˇce udosegljivoiz vozlišˇca v , ˇce obstaja sprehod od u do v . Relacija dosegljivosti je ekvivalenˇcna relacija. Njeni ekvivalenˇcni razredi sokomponente povezanosti. ˇCe je v grafu samo ena komponenta povezanosti, je graf povezan.
Zgled 4. Graf na Sliki 1 je povezan, graf na Sliki 4 pa ima tri komponente povezanosti.
18
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
Slika 4: Primer nepovezanega grafa reda 8
2.2 Nekaj družin grafov
Poznamo številne družine grafov. Za nas bosta zanimivi predvsem dve družini in sicer polni grafi in drevesa, v tem razdelku bomo poleg njiju definirali še poti, cikle, polne dvodelne grafe in poseben primer le teh, grafe imenovane zvezde. Grafovske družine nimajo nujno praznega preseka. Bralec lahko sam premisli da je polni grafK2obenem tudi drevo z dvema vozlišˇcema in pot,K3je kar 3-cikel, zvezde in poti pa so podmnožica dreves.
Definicija 10. PotPn je graf reda n ≥2 z množico vozlišˇc V ={v1,v2, . . . ,vn}in množico povezav E ={{vi,vi+1};i =1, 2, . . .n−1}.
Zgled 5. Na Sliki 5 so potiP2,P3,P4in skica potiPn. Oˇcitno ima vsaka pot dve vozlišˇci stopnje 1, ostala vozlišˇca pa so stopnje 2. Število povezav je za eno manjše od števila vozlišˇc.
Slika 5: Poti reda 2, 3, 4 in skica poti redan
Definicija 11.CikelCnoziroma n -cikel je graf reda n≥3, z množico vozlišˇc V ={v1,v2, . . . ,vn} in množico povezav E={{vi,vi+1};i =1, 2, . . .n−1} ∪ {{v1,vn}}.
Zgled 6. Cikel je 2-regularen graf. Zanj velja enakost|V|=|E|.
Slika 6: Cikel reda 7
Definicija 12. Polni grafje graf, v katerem sta poljubni vozlišˇci med seboj povezani. Polni graf reda n oznaˇcimo s Kn.
Zgled 7. V polnem grafuKnje vsako izmedn vozlišˇc povezano s preostalimin−1 vozlišˇci, zato je(n−1)-regularen in ima natanko n2
=n(n−12 ) povezav.
Definicija 13. Komplementu polnega grafa Kn reˇcemoprazen graf.
19
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
Slika 7: Polni grafi do reda 6
Definicija 14. Polni dvodelni grafKn,m, kjer je n≤m , je graf z množico vozlišˇc V ={a1,a2, . . . ,an} ∪ {b1,b2, . . . ,bm}
in množico povezav E ={{ai,bj};i =1, 2, . . . ,n,j =1, 2, . . . ,m}. Dvodelnim polnim grafom oblike K1,npravimozvezdein jih oznaˇcimo z oznako Sn.
Zgled 8. GrafKn,mimanvozlišˇc stopnjeminmvozlišˇc stopnjen, torej skupajn+mvozlišˇc tern·m povezav.
Slika 8: Primer polnega dvodelnega grafa in zvezde
2.3 Drevesa
Naslednja družina ki jo bomo spoznali, so drevesa. Ta družina je za nas najpomembnejša.
Definicija 15. Drevoje povezan graf, v katerem ne nastopajo cikli.
Definicija 16. Vozlišˇce stopnje 1 v drevesu jelist. Ostala vozlišˇca sonotranjavozlišˇca.
Slika 9: Drevo reda 10
Zgled 9. Na Sliki 9 je prikazano drevo reda deset, s sedmimi listi in tremi notranjimi vozlišˇci.
Trditev 2. Naj boΓ konˇcno drevo reda n>1. Tedaj ima drevo vsaj dva lista.
20
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
Dokaz. Ker je grafΓ konˇcen, premore le konˇcno število poti in vse so konˇcne dolžine. Ker ima vsaj dve vozlišˇci, obstaja torej neka najdaljša pot dolžinek ≥1, recimo(v0,v1, . . . ,vk). Trdimo, da stav0invk lista. ˇCev0ni list, je stopnje vsaj 2. Obstaja torej vozlišˇceu 6=v1, ki je sosednje zv0. ˇCe veljau∈ {v2, . . . ,vk}, dobimo vΓ cikel, kar je protislovje. V nasprotnem primeru pa je(u,v0, . . . ,vk)pot, ki je daljša od prvotne, protislovje. Podobno bi dokazali, da je tudivk list.
Trditev 3. Naj boΓ = (V,E)konˇcno drevo. Tedaj je število njegovih povezav za eno manjše od števila vozlišˇc. Torej, velja|E|=|V| −1.
Dokaz. Trditev bomo dokazali z indukcijo na število vozlišˇc. Naj boΓ drevo zn vozlišˇci.
Drevo z enim vozlišˇcem nima povezave, torej zan=1 enakost velja.
Recimo, da trditev velja za vsa drevesa reda, ki je manjši ali enakn−1. ˇCe jeΓ drevo reda n ima po Trditvi 2 list, ki ga oznaˇcimo zv. PodgrafΓ −v brez vozlišˇcav je tedaj še vedno povezan in brez ciklov, torej drevo. Po indukcijski predpostavki ima
|E(Γ−v)|=|V(Γ−v)| −1=n−1−1=n−2
povezav. Ker smo z odstranitvijo vozlišˇca odstanili natanko eno povezavo, je imelo zaˇcetno drevon−1=|V(Γ)| −1 povezav.
Trditev 4. Drevo reda n , ki ima vsa notranja vozlišˇca stopnje k , ima natanko l = 2n−n k−21−k listov.
Dokaz. V drevesu jel listov, preostalihn−l vozlišˇc pa je stopnjek. Po Lemi o rokovanju velja enakost 2|E|=l + (n −l)k. Po Trditvi 3 pa velja|E|=|V| −1=n−1. ˇCe izenaˇcimo število povezav, dobimo
l+ (n−l)k
2 =n−1, iz tega sledil =2n−n k−21−k .
Naslednji izrek nam podaja nekaj enakovrednih definicij dreves, ki jih najdemo v raz- liˇcnih virih, na primer v[6]in[7].
Izrek 1(Karakterizacija dreves). Naj boΓ = (V,E)konˇcen graf reda n . Tedaj so naslednje trditve ekvivalentne.
(i) GrafΓ je drevo.
(ii) GrafΓ je povezan in ima n−1povezav.
(iii) GrafΓ ima n−1povezav in ne vsebuje ciklov.
(iv) Poljubni dve vozlišˇci sta povezani z natanko eno potjo.
(v) GrafΓ je povezan. ˇCe odstranimo katerokoli povezavo, postane nepovezan.
(vi) GrafΓ ne vsebuje ciklov. ˇCe dodamo novo povezavo e med nesosednjima vozlišˇcema, ima dobljeni graf natanko en cikel.
Dokaz. Izrek bomo dokazali krožno, z dokazovanjem posameznih implikacij.
• (i)⇒(ii)Izjava(ii)sledi direktno iz definicije drevesa in Trditve 3.
21
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
• (ii)⇒(iii)Opazimo, da ˇce povezanemu grafu, ki vsebuje cikel, odstranimo povezavo iz cikla, je graf še vedno povezan. Denimo, da ima naš grafΓ kakšen cikel. Potem mu lahko odstranimo povezavo in bo še vedno povezan. ˇCe ima novi graf še kakšen cikel, postopek ponavljamo. Ker je grafΓ konˇcen, bomo po konˇcnem številuk>0 korakov dobili povezan graf redanbrez ciklov, torej drevo. To drevo bo imelon−1−k povezav, kar je v protislovju s trditvijo(ii).
• (iii)⇒(iv)Ker graf ne vsebuje ciklov, bo med dvema vozlišˇcema najveˇc ena pot. Poka- zati moramo še, da je med njima natanko ena pot, torej, da jeΓ povezan. Recimo, da jeΓ sestavljen izk komponent povezanostiΓ1= (V1,E1),Γ2= (V2,E2), . . . ,Γk = (Vk,Ek), po upoštevanju Trditve 3 velja
|E|=|E1|+|E2|+. . .+|Ek|=|V1| −1+|V2| −1+. . .+|Vk| −1=n−k, kar po predpostavki velja le v primeru, ko jek =1. Torej jeΓ povezan.
• (iv)⇒(v)Ce grafuˇ Γ odstranimo povezavo{u,v}, potem medu inv ni veˇc poti, sicer bi bili v zaˇcetnem grafu dve poti, kar je v protislovju s predpostavko. Torej dobljeni graf ni povezan.
• (v)⇒(vi)Vemo, da je grafΓpovezan in da z odstranitvijo katerekoli povezave postane nepovezan. ˇCe imaΓ cikel, ni nujno, da z odstranitvijo poljubne povezave postane nepovezan, saj lahko odstranimo povezavo iz cikla. Torej grafΓ ne premore ciklov.
Med poljubnima nepovezanima vozlišˇcemauinvobstaja pot(v0,v1, . . . ,vk), kjerv0= uinvk =v. ˇCe vozlišˇciuinvpovežemo s povezavoe, vΓnastane cikel(u,v2, . . . ,v,u). Ce ta cikel ni edini, pomeni, da v novem grafu obstajata vsaj dva cikla, ki oba vsebujetaˇ povezavoe. Unija teh dveh ciklov brez povezavee je že cikel v zaˇcetnem grafu Γ, protislovje.
• (vi)⇒(i)GrafΓ ne vsebuje ciklov. Pokazati moramo še, da jeΓ povezan. Med poljub- nima vozlišˇcema moramo najti pot. ˇCe sta vozlišˇci sosednji, med njima obstaja pot.
Ce nista sosednji, ju povežemo s povezavo in po predpostavki z dodano povezavoˇ nastane cikel. Torej je morala pot med vozlišˇcema že obstajati.
Definicija 17. Naj boΓ = (V,E)graf brez ciklov. Tedaj jeΓ gozd, ko je vsaka njegova kompo- nenta povezanosti drevo.
Slika 10: Primer gozda reda 15
Ce poznamo red gozda in število dreves v njem, lahko hitro ugotovimo, koliko povezavˇ premore gozd. To nam pove naslednja trditev.
Trditev 5. Naj boΓ gozd reda n s k drevesi. Potem ima gozdΓ natanko n−k povezav.
22
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
Dokaz. Naj boΓ = (V,E)gozd redan sk drevesiΓ1= (V1,E2), . . . ,Γk = (Vk,Ek). Po Trditvi 3 velja|E|=|E1|+|E2|+. . .+|Ek|=|V1| −1+|V2| −1+. . .+|Vk| −1=|V| −k =n−k.
Zgled 10. Gozd na Sliki 10 je reda 15 in vsebuje 3 drevesa, katera skupaj premorejo 12 po- vezav.
Za vsa drevesa in poslediˇcno za gozdove velja še ena lepa lastnost.
Definicija 18. Naj boΓ= (V,E)graf. ˇCe lahko množico vozlišˇc V razbijemo na dve disjunk- tni neprazni podmnožici V1in V2tako, da ima vsaka povezava eno krajišˇce v V1in drugo v V2, je grafdvodelen.
Pogosto se za dvodelnost uporablja naslednja karakterizacija, iz katere oˇcitno sledi, da so drevesa in gozdovi dvodelni.
Trditev 6(Karakterizacija dvodelnosti). Naj boΓ = (V,E) graf. Tedaj so naslednje trditve ekvivalentne.
(i) Graf je dvodelen.
(ii) Vozlišˇca grafa lahko pobarvamo z dvema barvama tako, da nobeni dve sosednji vozlišˇci nista iste barve.
(iii) Graf ne premore cikla lihe dolžine.
Dokaz. Izrek bomo dokazali krožno.
• (i) ⇒(ii) Ker je graf dvodelen, obstaja razcep množice vozlišˇc V na dve neprazni disjunktni podmnožiciV1inV2, kjer nobeni sosednji vozlišˇci nista v istih množicah.
Lahko si mislimo, da vozlišˇca vV1 pobarvamo s ˇcrno barvo, vozlišˇca vV2 pa z belo, tako nobeni dve sosednji vozlišˇci nista iste barve.
• (ii)⇒(iii)Imejmo cikel(v1,v2, . . . ,v2k,v2k+1,v1), ki je lihe dolžine. Brez škode za splo- šnost lahko reˇcemo, da je vozlišˇcev1obarvano s ˇcrno barvo. Tako jev2bele barve,v3 spet ˇcrne, in tako naprej. Vozlišˇce v2k je bele barve,v2k+1pa ˇcrne. To vozlišˇce je po- vezano z vozlišˇcemv1, to bi po trditvi(ii)moralo biti belo, ampak po predpostavki je ˇcrno. Prišli smo do protislovja, tako dvodelen graf res ne premore cikla lihe dolžine.
• (iii)⇒(i)Ker je graf dvodelen natanko tedaj, ko je vsaka njegova komponenta dvo- delna, lahko brez škode za splošnost privzamemo, da jeΓpovezan. Vzemimo vozlišˇce v in ga dajmo v množicoV1, vse njegove sosede,N(v), pa vV2. ˇCe bi med vozlišˇci iz N(v)obstajala kakšna povezava, bi pomenilo, da je vΓ3-cikel, vendar ga po predpo- stavki ni. Sedaj damo vsako sosednje vozlišˇce vozlišˇc izV2vV1(razenv, ki je že vV1).
Med njimi ni povezav, saj bi potemΓ vseboval 3 - ali 5-cikel, kar po predpostavki ni res. Konstrukcijo tako nadaljujemo in vsehnvozlišˇc razporedimo v množiciV1inV2. Torej je graf dvodelen.
Definicija 19. Naj boΓ graf, grafΓ0pa njegov vpeti podgraf in hkrati drevo. Potem grafuΓ0 reˇcemovpeto drevo.
23
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
Slika 11: Primer grafa reda 9 in dveh njegovih vpetih dreves
2.4 Izomorfnost grafov
Definicija 20. Izomorfizem grafovje bijektivna preslikavaϕmed grafomaΓ1 = (V1,E1)in Γ2= (V2,E2), ki slika iz množice vozlišˇc V1v množico vozlišˇc V2, torejϕ:V1→V2, tako da za vsak par vozlišˇc u,v∈V1velja u∼Γ1v⇔ϕ(u)∼Γ2 ϕ(v), torejϕohranja sosednost.
Definicija 21. Ce med grafomaˇ Γ1inΓ2obstaja kak izomorfizem, sta grafaizomorfna. Izo- morfnost grafov oznaˇcimo zΓ1∼=Γ2.
Izomorfnost grafov je seveda ekvivalenˇcna relacija. Poenostavljeno lahko povemo, da sta grafa izomorfna, ko lahko en graf preoblikujemo v drugega zgolj z “elastiˇcnim” premi- kanjem obstojeˇcih vozlišˇc in povezav ter takim preimenovanjem vozlišˇc, da se ohranja so- sednost.
Zgled 11. Grafa na Sliki 12 sta izomorfna, saj med njima lahko najdemo izomorfizem, de- nimo preslikavoϕ, za katero jeϕ(1) =a,ϕ(2) =b,ϕ(3) =c inϕ(4) =d. Oˇcitno jeϕbijekcija, premisliti je treba, da ohranja sosednost. Vozlišˇce 1 je sosednje z vozlišˇcema 2 in 4, zato mora biti vozlišˇcea =ϕ(1)sosednje vozlišˇcemaϕ(2) = b inϕ(4) =d, kar velja. Podobno ugotovimo za ostala vozlišˇca.
Slika 12: Izomorfna grafa reda 4
Po drugi strani pa bijektivna preslikavaϕ0, za katero jeϕ0(1) =c,ϕ0(2) =a,ϕ0(3) =d in ϕ0(4) =b, ni izomorfizem, saj vozlišˇceϕ0(2) =a ni sosednje sϕ0(1) =c.
Izomorfna grafa imata enake vse “bistvene” lastnosti. Nekaj teh je naštetih v naslednji trditvi.
Trditev 7. Naj bostaΓ1= (V1,E1)inΓ2= (V2,E2)izomorfna grafa inϕ:Γ1→Γ2nek izomorfi- zem. Potem velja:
(i) Grafa imata enak red in število povezav:|V1|=|V2|in|E1|=|E2|.
(ii) GrafaΓ1inΓ2imata enako število komponent. Posebej, grafΓ1je povezan natanko tedaj, ko je povezan grafΓ2.
(iii) ϕohranja stopnjo vozlišˇc, torejϕ(deg(v)) =deg(v). Poslediˇcno, število vozlišˇc stopnje k je v obeh grafih enako za vsak k .
Ce se grafa v kateri od zgornjih lastnosti razlikujeta, gotovo nista izomorfna.ˇ 24
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
3 Preštevanje dreves in Cayleyev izrek
V tem poglavju bomo poskusili prešteti vsa drevesa z danim številom vozlišˇc. Pri tem bomo loˇcili dva primera in sicer, preštevanje razliˇcnih dreves z oznaˇcenimi vozlišˇci in preštevanje neizomorfnih dreves, pri katerih nam oznake vozlišˇc niso pomembne. Razliko med njima bomo ilustrirali z naslednjim zgledom.
Slika 13: Tri razliˇcna oznaˇcena drevesa reda 5
Zgled 12. Na Sliki 13 so tri razliˇcna oznaˇcena drevesa reda 5. Levo in srednje sta oˇcitno izomorfni. Nobeno od njiju pa ni izomorfno desnemu. Desno drevo namreˇc vsebuje vo- zlišˇce stopnje 4. ˇCe torej preštevamo neizomorfna drevesa, sta na Sliki 13 le dve razliˇcni (neoznaˇceni) drevesi.
3.1 Problem preštevanja neizomorfnih dreves
Problem preštevanja neizomorfnih dreves redan je zelo zahteven. Za obˇcutek zaˇcnimo z zgledom.
Zgled 13. Na Sliki 14 je šest neizomorfnih dreves reda 6. Ni težko videti, da so narisana drevesa neizomorfna. Drevoa)ima denimo vozlišˇce stopnje 5, ki ga ostala nimajo. Samo drevob)ima vozlišˇce stopnje 4, drevoe)je edino z dvema vozlišˇcema stopnje 3, drevo f) nima vozlišˇc stopnje vsaj tri. Drevesic) in d) pa se med seboj razlikujeta po tem, da je v drevesud)edino vozlišˇce stopnje tri sosednje z le enim vozlišˇcem stopnje 2. So to vsa neoznaˇcena drevesa reda 6? O tem se bomo prepriˇcali z naslednjo trditvijo.
Slika 14: Neizomorfna drevesa reda 6
Trditev 8. Naj bo n naravno število in t(n)število neizomorfnih dreves reda n . Tedaj velja t(1) =1, t(2) =1, t(3) =1, t(4) =2, t(5) =3in t(6) =6.
Dokaz. Ce imamo eno samo vozlišˇce, povezav ni, torej je eno samo možno drevo. Medˇ dvema vozlišˇcema je možna zgolj ena povezava, torej je tudi tukaj drevo eno samo. Za drevo s tremi vozlišˇci vemo, da ima dve povezavi. Tako je edina možnost, da je to drevo kar potP3. To so prva tri drevesa na Sliki 15.
25
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
Slika 15: Neizomorfna drevesa do reda 5
Drevo reda štiri ima maksimalno stopnjo ∆ = 3, ˇce obstaja vozlišˇce, ki je sosednje z vsemi ostalimi vozlišˇci. V tem primeru dobimo eno drevo,K1,3, na Sliki 15b). ˇCe je v dre- vesu∆=2, so vsa vozlišˇca stopnje 2 ali 1. Po Posledici Leme o rokovanju vemo, da je listov sodo mnogo. V tem primeru imamo lahko 0, 2 ali 4 liste. Niˇc listov ne smemo imeti, saj po Trditvi 2 v drevesu obstajata vsaj dva lista. Drevo reda 4 ne premore niti štirih listov, saj v tem primeru drevo ni povezano. Tako vemo, da sta lista dva, ostali dve vozlišˇci pa sta sto- pnje 2. Drugo drevo reda 4 je potP4, na Sliki 15a).
Preštejmo drevesa reda 5. Najveˇcja možna maksimalna stopnja v drevesu reda 5 je enaka∆=4. Naj velja ∆=4, in naj bo vozlišˇcev stopnje 4. Potem je to vozlišˇce pove- zano z ostalimi štirimi vozlišˇci in dobimo drevo izomorfno zvezdiK1,4, na Sliki 15d). Naj bo sedaj∆=3 inv vozlišˇce, za katerega velja deg(v) =3. Vozlišˇcev je povezano s tremi vozlišˇci, do drevesa reda 5 nam preostane še eno vozlišˇce in ena povezava. To vozlišˇce ne sme biti vN(v), tako da ga z eno povezavo lahko povežemo na katero koli vozlišˇce izN(v). Dobimo drugo drevo reda 5, drevo na Sliki 15e). V tretjem primeru naj velja∆=2. V ta- kšnem drevesu je vsako vozlišˇce stopnje 1 ali 2. Po podobnem razmisleku kot prin=4, sta v drevesu lahko le dva lista, ostala tri vozlišˇca pa so stopnje 2. Dobimo še tretji graf reda 5, potP5, na Sliki 15c).
V zadnjem koraku doloˇcimo še vsa drevesa reda 6. Drevo reda 6 ima 5 povezav, najveˇcja možna maksimalna stopnja∆pa je enaka 5. Vozlišˇca niso oznaˇcena, zato ni pomembno, katero vozlišˇce bo na primer stopnje 5. Naj bo sedaj∆=5. V tem primeru je vozlišˇcev, deg(v) =5, povezano s preostalimi petimi vozlišˇci. Dobimo prvi graf reda 6, grafK1,5, na Sliki 14a). V primeru, da je∆=4, je vozlišˇcev, deg(v) =4, povezano s štirimi vozlišˇci. Šesto vozlišˇce, naj bou∈/N(v), ki je lahko povezano s katerim koli vozlišˇcem izN(v). Dobili smo drugo drevo reda 6, na Sliki 14b). Naj bo sedaj∆=3. Vozlišˇcev, deg(v) =3, je povezano s tremi vozlišˇci. Tu loˇcimo tri primere, kako povežemo dve vozlišˇciu inw, ki nista vN(v). V prvem primeru lahko vsako vozlišˇceuinvpovežemo s svojim vozlišˇcem izN(v)in dobimo graf na Sliki 14 c). V drugem primeru lahko na primer u povežemo z enim vozlišˇcem iz N(v),w pa povežemo zu. Dobimo graf na Sliki 14d). V tretjem primeru pa obe vozlišˇci u inw povežemo na isto vozlišˇce izN(v)in dobimo graf na Sliki 14e). Ko imamo∆=2, so vsa vozlišˇca stopnje 2 ali 1. Spet vemo, da ima drevo lahko 0, 2, 4 ali 6 listov. Možnosti z 0 ali 6 listi odpadeta po podobnem razmisleku kot prin =4. ˇCe želimo izpolniti pogoja, da je∆=2 in da so v drevesu 4 listi, dobimo nepovezan graf, torej tudi ta možnost odpade.
Ostane nam še primer, ko sta v drevesu reda 6 dva lista. Ostala štiri vozlišˇca so tako stopnje 2 in dobimo potP6, na Sliki 14 f).
26
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
n t(n) n t(n) n t(n)
1 1 13 1301 25 104636890
2 1 14 3159 26 279793450
3 1 15 7741 27 751065460
4 2 16 19320 28 2023443032
5 3 17 48629 29 5469566585
6 6 18 123867 30 14830871802
7 11 19 317955 31 40330829030
8 23 20 823065 32 109972410221
9 47 21 2144505 33 300628862480
10 106 22 5623756 34 823779631721 11 235 23 14828074 35 2262366343746 12 551 24 39299897 36 6226306037178
Tabela 1: Števila neizomorfnih dreves redan, (vir zaporedje A000055 v[11])
Prvi se je s problemom preštevanja dreves ukvarjal angleški matematik Arthur Cayley (1821-1895), ki je s pomoˇcjo rodovnih funkcij preštel tako imenovana zakoreninjena dre- vesa in na ta naˇcin doloˇcil števila neizomorfnih dreves vse do reda 13. Presenetljivo je, da so še do danes znana toˇcna števila neizomorfnih dreves le do reda 36. Veˇcino teh števil so doloˇcili v 20. stoletju s pomoˇcjo raznih rekurzivnih zvez in s pomoˇcjo raˇcunalnikov. Znane vrednosti so zapisane v spletni enciklopediji z znanimi zaporedji celih števil[11]. Eksplici- tna formula, ki bi nam podala rešitev tega problema kot funkcijo številan, pa za enkrat ni znana.
27
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
3.2 Cayleyeva formula za število oznaˇcenih dreves
V tem razdelku se bomo ukvarjali s preštevanjem razliˇcnih oznaˇcenih dreves redan. Pro- blem je precej lažji od prejšnjega. Lahko ga izenaˇcimo s problemom iskanja vseh vpetih dreves v polnem grafuKn, kjer vozlišˇca oznaˇcimo od 1 don. V tem primeru vsako drevo redan predstavlja eno vpeto drevo v polnem grafu.
Tudi tega problema se je prvi lotil Cayley med raziskovanjem ogljikovodikovih molekul. Po njem se danes imenuje tudi ustrezna formula, ki jo je v kontekstu determinant leta 1860 odkril Carl Wilhelm Borchardt, prvi pa jo je leta 1918 dokazal Prüfer.
Zgled 14. Na Slikah 16 in 17 so prikazana vsa razliˇcna oznaˇcena drevesa reda 3 in 4. V nadaljevanju bomo natanˇcneje razložili, kako doloˇcimo njihovo število.
Slika 16: Oznaˇcena drevesa reda 3
Slika 17: Oznaˇcena drevesa reda 4
Trditev 9. Naj bo n naravno število in T(n)število oznaˇcenih dreves reda n . Potem velja T(1) =1, T(2) =1, T(3) =3, T(4) =16, T(5) =125in T(6) =1296.
Dokaz. Po Trditvi 8 poznamo število neizomorfnih (neoznaˇcenih) dreves reda 1 do 6. V dokazu bomo prešteli razliˇcna oznaˇcena drevesa do vkljuˇcno reda 6. Zan=1 edino drevo nima povezave, zan =2 pa je povezava samo ena, zato je v teh dveh primerih oznaˇceno drevo eno samo.
Zan =3 vemo, da obstaja (do izomorfizma) natanko eno drevo, v katerem sta dva lista in eno vozlišˇce stopnje dve. ˇCe takšnemu drevesu oznaˇcimo vozlišˇca z oznakami{1, 2, 3}, lahko na 31
=3 naˇcine izberemo, katero oznako bo imelo vozlišˇce stopnje dve. S tem smo 28
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
doloˇcili tudi vse povezave. Torej, dobili smo tri razliˇcna oznaˇcena drevesa. Prikazana so na Sliki 16.
Prin=4 vemo, da imamo dve neizomorfni drevesi. Eno drevo ima tri liste in eno vozli- šˇce stopnje tri. V tem primeru izmed štirih oznak izberemo eno, ki bo oznaˇcevala vozlišˇce stopnje 3, za to imamo 41
=4 možnosti, torej 4 razliˇcna drevesa. Prikazana so na Sliki 17 v prvi vrstici. V drugem primeru ima drevo dve vozlišˇci stopnje dve in dva lista. Vsak list je povezan z enim vozlišˇcem stopnje dve. V tem drevesu izberemo oznaki za vozlišˇci stopnje 2 na 42
=6 naˇcinov. Izbrati pa moramo še, z listom s katero oznako bo povezano vozlišˇce stopnje dve, torej imamo 21
=2 možnosti. Vseh teh 2·6=12 dreves je prikazanih na Sliki 17 v spodnjih treh vrsticah. Vseh razliˇcnih oznaˇcenih dreves reda 4 je tako 12+4=16.
Imamo tri neoznaˇcena drevesa reda 5, katerih vozlišˇca želimo oznaˇciti z{1, 2, 3, 4, 5}. Prvo drevo (P5) ima dva lista in tri notranja vozlišˇca stopnje dve. Središˇce poti lahko ozna- ˇcimo na 51
=5 naˇcinov. Njegova soseda na 42
=6 naˇcinov, preostala lista pa na 2 naˇcina.
Dobimo 5·6·2=60 razliˇcnih dreves. Drugo drevo (K1,4) ima štiri liste in eno notranje vo- zlišˇce stopnje štiri, ki ga lahko oznaˇcimo na 5 naˇcinov, liste oznaˇcimo s preostalimi ozna- kami. Dobimo 5 razliˇcnih dreves. Tretje drevo ima tri liste, eno vozlišˇce stopnje 2 in eno vozlišˇce stopnje 3. Najprej bomo izbrali oznako za vozlišˇce stopnje 3, možnosti je 5. Potem izberemo oznako za vozlišˇce stopnje 2, na 4 naˇcine. Na koncu izberemo še oznako za list, soseden vozlišˇcu stopnje dve. Zanj imamo 3 možnosti. Za ostala dva lista ni pomembno, s katero oznako je kateri oznaˇcen. ˇCe sedaj to zmnožimo in seštejemo, dobimo da je ozna- ˇcenih dreves reda 5 enako 60+5+ (5·4·3) =125.
Preostala so nam še drevesa reda 6. Neoznaˇcenih dreves reda 6 je 6. Najprej oznaˇcimo tistega, ki ima dva lista, notranja vozlišˇca pa so stopnje 2 (Slika 14 f). Najbolj notranji vo- zlišˇci lahko oznaˇcimo na 62
=15 naˇcinov. Sosednje vozlišˇce enemu izmed teh dveh lahko oznaˇcimo na 4 naˇcine, njemu sosednji list pa na 3 naˇcine. Za preostali vozlišˇci sta 2 mo- žnosti. Skupaj 62
·4·3·2=360 razliˇcnih dreves. Naslednje drevo ima eno vozlišˇce stopnje 3, sosednje z dvema listoma, dve notranji vozlišˇci stopnje dve in še en list (Slika 14d). Najprej oznaˇcimo vozlišˇce stopnje 3, na 6 možnih naˇcinov, nato njemu sosedna lista na 52
=10 na- ˇcinov. Za ostala vozlišˇca je 3·2=6 možnosti, skupaj torej 360 razliˇcnih dreves. Naslednje drevo (Slika 14c) ima vozlišˇce stopnje 3, ki je sosednje enemu listu. V drevesu sta še dve no- tranji vozlišˇci stopnje 2 in dva lista. To drevo lahko oznaˇcimo na 360=6· 52
·3·2 naˇcinov - 6 (vozlišˇce stopnje 3), 52
(vozlišˇca stopnje 2), 3 (en list), 2 (drugi list), 1 (tretji list). Naslednje drevo (Slika 14b) lahko oznaˇcimo na 120 =6·5·4 razliˇcnih naˇcinov. In sicer 6 možnosti za vozlišˇce stopnje 4, 5 za vozlišˇce stopnje 2 in 4 za list, ki ni soseden vozlišˇcu stopnje 3.
Za drevo z dvema notranjima vozlišˇcema stopnje 3 (Slika 14e) in s štirimi listi pa imamo 90= 62
· 42
možnosti. Za notranji vozlišˇci 62
možnosti, 42
pa za dva lista. Ostala dva lista sta doloˇcena s preostankom oznak. Ostane nam še drevo, izomorfno zvezdi (Slika 14a), katerega lahko oznaˇcimo na 6 možnih naˇcinov, glede na to, s katero oznako oznaˇcimo voz- lišˇce stopnje 5. Skupaj imamo torej 360+360+360+120+90+6=1296 razliˇcnih oznaˇcenih dreves reda 6.
Pozorni bralec bo morda opazil, da je število dreves reda 3 enako 31, dreves reda 4 enako 42, dreves reda 5 enako 53in dreves reda 6 enako 64. Znameniti Cayleyev izrek nam pove, da ta isti vzorec velja za vsako naravno številon.
29
Jera Stojko Univerza v Ljubljani, Pedagoška fakulteta
Izrek 2(Cayleyev izrek). Število razliˇcnih dreves na oznaˇcenih n vozlišˇcih je enako T(n) =nn−2.
Kot smo že omenili, je prvi pravi dokaz Cayleyevega izreka podal Prüfer. Kasneje pa so razliˇcni avtorji odkrili razliˇcne dokaze, ki uporabljajo orodja razliˇcnih vej matematike.
Nekaj najlepših ali najbolj zanimivih od teh dokazov bomo prikazali v nadaljevanju.
3.2.1 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(a1,a2, . . . ,an−2), kjer je ai∈ {1, 2, . . . ,n}, n≥3, in so ponovitve med aidovoljene, 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 enakonn−2.
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 listavi še vedno drevo. Ustreza mu Prüferjevo zaporedje drevesaΓ brez prvega ˇclenaa1. 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 ={v1,v2, . . . ,vn}. Lista z najnižjo oznako naj bostavi in vj. Obravnavali bomo tri primere:
• Ce jeˇ vi =vj, 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ˇ vi = vj in sta tudi njuna soseda enaka, po odstranitvi listov v prvem koraku dobimo manjši, a razliˇcni drevesiΓ10inΓ20(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, . . . ,an−2)Prüferjevo zaporedje na abecedi {v1,v2, . . . ,vn}in vi list z najmanjšo oznako, ki ne nastopa va. Po predpostavki vemo, da Prüferjevo zaporedjea0 = (a2, . . . ,an−2)na abecedi{v1,v2, ...,vn} \ {vi}, ustreza drevesu Γ0. Ce sedaj v drevoˇ Γ0dodamo 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 moramo 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) =nn−1(n−1)!.
Ko izenaˇcimo število zaporedijN(T), dobimo
n T(n)(n−1)!=nn−1(n−1)!.
Iz tega sledi, da je število razliˇcnih oznaˇcenih dreves redan enako T(n) =nn−2.
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 nn−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) =nn−2. 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šˇcav1izmed vozlišˇcvk+1,vk+2, . . . ,vn, torej na n−ki naˇcinov;
(iii) odstranimo vozlišˇcev1;
(iv) izberemo oznaˇceni gozd sk−1+i drevesi nan−1 vozlišˇcih, kar lahko naFn−1,k−1+i naˇcinov.
Slika 22: GozdF, v katerem je vozlišˇcev1povezano zi vozlišˇci Od tod sledi rekurzivna zveza
Fn,k=
n−kX
i=0
n−k i
Fn−1,k−1+i.
V zvezi uporabimo indukcijsko predpostavko zan−1 ink−1+i, ter zapišimo Fn,k=
n−kX
i=0
n−k i
(k−1+i)(n−1)n−k−i−1.
Ker velja
n−kX
i=0
f(i) = Xn−k
i=0
f(n−k−i), namestoi vstavimon−k−i in dobimo
Fn,k =
n−kX
i=0
n−k i
((n−1)−i)(n−1)i−1=
=
n−kX
i=0
n−k i
(n−1)i−i Xn−k
i=1
n−k i
(n−1)i−1,
34
Univerza v Ljubljani, Pedagoška fakulteta Jera Stojko
kjer smo prvo vrstico razstavili na dva ˇclena. V naslednjem koraku bomo uporabili binom- ski izrek
(x+y)a =
a
X
b=0
a b
xaya−b, v drugi ˇclen pa bomo vstavili
n−k i
= (n−k)(n−k−1)!
i(i−1)!(n−k−1−1+1)!=n−k i
n−k−1 i−1
. Po upoštevanju zgornjih enakosti dobimo
Fk,n=
n−kX
i=0
n−k i
(n−1)i1n−k−i−i(n−k) i
n−kX
i=1
n−k−1 i −1
(n−1)i−11n−k−i=
= (n−1+1)n−k−(n−k)
n−k−1
X
i=0
n−k−1 i
(n−1)i−11n−k−i=
=nn−k−(n−k)(n−1+1)n−k−1=
=nn−k−(n−k)nn−k−1=
=nn−k(1−n−k n ) =
=nn−k(n−n+k
n ) =
=k nn−k−1.
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~1,e~2, . . . ,e~m}. Incidenˇcna matrikagrafa~Γ je matrika D velikosti n×m , kjer je element di,j enak
di,j =
1; vi zaˇceteke~j
−1; vi konece~j 0; sicer.
Definicija 27. Naj bo grafΓ = (V,E)z množico vozlišˇc V ={v1,v2, . . . ,vn}in množico povezav E ={e1,e2, . . . ,em}. Tedaj jeLaplaceova matrikaQ grafaΓ matrika velikosti n×n kjer je element qi j enak
qi,j =
deg(vi); i =j 1; vi∼vj
0; sicer.
Dogovorimo se, da bo matrikaAi joznaˇ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) =detQi i(Kn) =nn−2.
Dokaz. Za dokaz Posledice 3 najprej zapišimo Laplaceovo matrikoQ(Kn)polnega grafaKn, 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
Q(Kn) =
n-1 -1 -1 -1 . . . -1 -1 n-1 -1 -1 . . . -1 -1 -1 n-1 -1 . . . -1 -1 -1 -1 n-1 . . . -1 ... ... ... ... ... ... -1 -1 -1 -1 . . . n-1
.
Število vpetih dreves bomo dobili, ko bomo izraˇcunali determinanto matrikeQi i(Kn), zai bomo vzeli 1. MatrikaQ11(Kn), velikosti(n−1)×(n−1)je
Q11(Kn) =
n-1 -1 -1 . . . -1 -1 n-1 -1 . . . -1 -1 -1 n-1 . . . -1 ... ... ... ... ... -1 -1 -1 . . . n-1
.
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
det(Q11(Kn)) =det
n-1 -1 -1 . . . -1 -n n 0 . . . 0 -n 0 n . . . 0 ... ... ... ... ...
-n 0 0 . . . n
=det
1 -1 -1 . . . -1 0 n 0 . . . 0 0 0 n . . . 0 ... ... ... ... ...
0 0 0 . . . n
=det
1 0 0 . . . 0 0 n 0 . . . 0 0 0 n . . . 0 ... ... ... ... ...
0 0 0 . . . n
=nn−2
Determinanta matrikeQ11(Kn)je enaka
det(Q11(Kn)) =T(n) =nn−2.
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
