Matematika | Felsőoktatás » Bozó Brigitta - Címkézett és címkézetlen fák leszámlálása

http://www.doksihu Eötvös Loránd Tudományegyetem Természettudományi Kar Címkézett és címkézetlen fák leszámlálása Szakdolgozat Bozó Brigitta Matematika B.Sc, matematikai elemző Témavezető: Vesztergombi Katalin, egyetemi docens Számítógéptudományi Tanszék Budapest 2010 http://www.doksihu "Egy matematikai elméletet - mint egyébként minden más dolgot könnyebb felfogni, mint elmagyarázni a szépségét." Arthur Cayley http://www.doksihu Tartalomjegyzék 1. Alapfogalmak 5 1.1 Gráfokra vonatkozó definíciók, tételek 5 1.2 Fákra vonatkozó definíciók, tételek 8 2. Fák növesztése 13 2.1 Hogyan növesszünk fákat? 13 3. Fák tárolási módjai 15 3.1 Szomszédsági mátrix 15 3.2 Éllistával történő tárolás 17 3.3 Apakód 17 3.4 Prüfer kód

18 3.41 A Prüfer-kód megkonstruálása 18 3.42 Példa 19 3.43 Prüfer-kód összefoglalása 21 4. Címkézett fák száma 22 4.1 Cayley tétele 22 4.11 1 Bizonyítás indukcióval 22 4.12 2 Bizonyítás Prüfer kód segítségével 24 4.13 3 Bizonyítás lineáris algebrai módszerekkel 25 4.2 Példák címkézett fákra 27 4.21 Néhány szó Arthur Cayleyről 31 5. Címkézetlen fák 32 5.1 Közelítő képletek 32 5.11 Planáris kód 33 2 http://www.doksihu 5.12 Példák planáris kóddal történő kódolásra 35 6. Összefoglalás 37 7. Mellékletek 38 7.1 Arthur Cayley: Theorem on trees 38 3 http://www.doksihu Bevezetés Szakdolgozatom témája a címkézett és címkézetlen fák

leszámlálása. A témaválasztás során elsődleges célom volt, hogy a matematika szerteágazó és izgalmas témakörei közül olyan témában mélyedjek el, amelyet más tudományok is alkalmaznak A fákat a - teljesség igénye nélkül - használjuk különböző struktúrák tárolására, ezen adatok sorrendbe rendezésére, adathalmazban való keresésre. A döntéselmélet tudománya is előszeretettel használja az általuk döntési fáknak nevezett struktúrákat A fizika területén a Kirchoff-törvény bevezetésénél találkozhatunk a címkézett fák leszámlálásához szükséges képlettel, míg a biokémia tudománya kristályszerkezetek, valamint dns-molekulák szerkezetét szemlélteti ezen címkéző eljárással. Kristályszerkezeteknél egy-egy kristály szimmetriái számának meghatározására használják Szakdolgozatom célja a címkézett és címkézetlen fák összeszámlálására vonatkozó képletek levezetése, a tételek többféle

bizonyítása, példákon szemléltetve alkalmazásukat. A dolgozatban bemutatásra kerül Arthur Cayley : Theorem on trees 1889-ben megjelent cikke, szakaszaiban fordítással. A cikkel, valamint a fordítással szemlélteni szeretném, mennyire más volt még a matematikai nyelv, mikor Cayley megalkotta teóriáját. 4 http://www.doksihu 1. fejezet Alapfogalmak 1.1 Gráfokra vonatkozó definíciók, tételek A gráf definíciója többféleképpen megközelíthető és megfogalmazható attól függően, hogy az élet mely területén szeretnénk használni. A következő definíciók és tételek szó szerint megjelennek a dolgozat végén feltüntetett szakirodalmakban. 1.11 Definíció Adott egy A halmaz, és egy rajta értelmezett ρ ⊆ A × A bináris (kétváltozós) reláció. Ekkor a G = (A, ρ) párt, vagyis az A halmaz feletti egyrelációs struktúrát az A halmaz feletti gráfnak nevezzük. 1.12 Definíció Egy gráf két halmazból áll Az egyik elemeit a gráf

csúcsainak vagy pontjainak nevezzük, amelyek közül némelyeket (nem feltétlenül az összeset) élek kötnek össze, ezek az élek alkotják a gráfot megadó másik halmazt. A G gráf pontjainak halmazát V , éleinek halmazát E jelöli. Tehát G = (V, E) jelentése: G gráf pontjai a V , élei pedig az E halmaz elemei. 1.13 Definíció Legyen V egy véges halmaz, E pedig V -beli rendezetlen elempárok véges rendszere Ekkor a G = (V, E) párt gráfnak nevezzük V elemei a gráf csúcsai, E elemei a gráf élei. Ha e = (v1 , v2 ) egy él, akkor azt mondjuk, hogy az e él a v1 és a v2 csúcsokat köti össze. Rendezetlen elempáron azt értjük, hogy nem teszünk különbséget a (v1 , v2 ) és a (v2 , v1 ) pár között, a rendszer pedig abban különbözik a halmaztól, hogy egy elem többször is szerepelhet benne. 5 http://www.doksihu 1.14 Megjegyzés A fenti három definíció ekvivalens Ebben a dolgozatban a második definíció nyelvezete, valamint felépítése lesz

használatos. A harmadik definíciót leginkább a szociológia területén használják így. 1.15 Definíció A hurokél olyan él, amelynek két végpontja azonos 1.16 Definíció Párhuzamos élről beszélhetünk, ha két pont között több él fut 1. ábra: Példa hurokélre, valamint párhuzamos élre 1.17 Definíció G egyszerű gráf, ha nincs benne hurokél, vagy párhuzamos él 1.18 Megjegyzés Ha egy gráfban párhuzamos élek is lehetnek, akkor azt gyakran a multigráf elnevezéssel illetjük. 1.19 Definíció Egy él két végpontját a gráf szomszédos pontjainak nevezzük 1.110 Definíció Egy gráf valamely pontjából kiinduló élek számát az illető pont fokszámainak nevezzük. Jelölés: v pont fokszáma d(v) 1.111 Állítás X d(v) = 2 · |E|. v∈V 1.112 Tétel Ha egy gráf pontjainak száma páratlan, akkor van legalább egy páros fokszámú pontja. 1.113 Tétel Ha egy gráf pontjainak száma páros, úgy páros fokszámú pontjainak száma is az. 6

http://www.doksihu 1.114 Definíció Az egymáshoz csatlakozó ismétlés nélküli élek sorozatát útnak nevezzük. Formálisan: Legyen G gráf, melynek pontjait jelöljük vi -vel, élei legyenek ei -k. Ebben az esetben az út a vi1 , ei1 , vi2 , ei2 , . , vik , eik , vik+1 formulával írható le, ahol minden pont és él különböző. Ekkor a fenti formula egy k élű, k + 1 pontú utat határoz meg. 1.115 Definíció Egy G gráf összefüggő, ha bármely két pontjához található a két pontot összekötő út G-ben. 1.116 Definíció A kör élek egymáshoz csatlakozó sorozata, ami záródik, tehát az utolsó és az első élnek van közös végpontja, és nincs más ismétlődő csúcs. 2. ábra: A piros vonallal jelzett élek egy kört alkotnak a gráfon belül 1.117 Definíció Az üres gráf olyan gráf, amelyben nincs él (a teljes gráf komplementere) 1.118 Definíció Az olyan egyszerű gráfot, melyben minden pontpár össze van kötve éllel, teljes

gráfnak nevezzük. 3. ábra: Öt pontú teljes gráf 7 http://www.doksihu 1.119 Definíció Tetszőleges G gráf egyértelműen meghatároz egy G gráfot, amelyben két pont pontosan akkor van összekötve, ha G-ben nincs A G gráfot a G komplementerének nevezzük. 4. ábra: Az első gráf komplementere a második 1.120 Definíció Ha tekintjük V (G) egy V (H) részhalmazát, valamint bizonyos, a V (H)-beli pontokat összekötő élek egy E(H) ⊆ E(G) részhalmazát, akkor a (V (H), E(H)) pár G egy H részgráfját alkotja. Ha minden olyan E(G)-beli élt beveszünk E(H)-ba, amelyek végpontjai V (H)-beliek, akkor H-t feszített részgráfnak nevezzük. 1.2 Fákra vonatkozó definíciók, tételek 1.21 Definíció A G = (V, E) gráfot fának nevezzük, ha összefüggő, és nincsen benne kör. 1.22 Megjegyzés Az egyetlen pontból álló gráf is fa 1.23 Tétel Egy G gráf akkor és csak akkor fa, ha bármely két pontja között pontosan egy út vezet. 8

http://www.doksihu 1.24 Bizonyítás Tegyük fel, hogy G egy fa Akkor G összefüggő, ezért bármely két különböző pontja között van út. Több út nem lehet, mert akkor G-ben lenne kör, ami ellentmondás. Fordítva, tegyük fel, hogy G-ben bármely két különböző pont között pontosan egy út vezet. Akkor G összefüggő (mert van út) és körmentes (mert csak egy út van), tehát G fa. 5. ábra: Példák különböző fákra A második fát speciálisan csillagnak nevezzük, a harmadik pedig egy út. 1.25 Tétel Legyen G egy egyszerű gráf Ekkor a következő állítások ekvivalensek: 1.) G fa 2.) G összefüggő, de ha bármely élét töröljük, akkor már nem marad az 3.) G körmentes, de bármely új élt hozzávéve a keletkező gráf már tartalmaz kört 1.26 Bizonyítás 1 ⇒ 2 Tegyük fel, hogy G gráf fa Ekkor definíció szerint összefüggő. Tegyük fel, hogy a gráfból az ab élt törölve a gráf összefüggő marad Az így kapott részgráf

összefüggősége miatt van a és b pontok között út. Ha most visszarajzoljuk a gráfba az ab élt, akkor azzal bezárjuk a kört. Így a G gráf biztosan tartalmaz kört, ami fák esetén nem lehetséges. 2. ⇒ 1 Tegyük fel, hogy G összefüggő, de ha bármely élét töröljük, akkor már nem marad az. Ekkor G összefüggősége miatt azt kell megmutatni, hogy G körmentes 9 http://www.doksihu Indirekt tegyük fel, hogy G-ben van kör (C). Ekkor a kör egy ab élét elhagyva szintén összefüggő gráfot kapunk. (Hiszen, ha x és y pontok közötti út tartalmazta az ab élt, akkor az útba az említett él helyett vegyük be a C kör megmaradt éleit). Ez pedig ellentmond a feltevésünknek. 1. ⇒ 3 Tegyük fel, hogy G gráf fa Ekkor definíció szerint körmentes Tegyük fel, hogy a gráfhoz hozzávéve az ab élt a gráf körmentes marad. Mivel az eredeti gráf összefüggő volt, ezért volt benne a és b közötti út (ami nem lehetett az ab él, hiszen akkor nem

vehettük volna a gráfhoz), amit az ab él behúzásával körré zártunk volna. Ellentmondásra jutottunk, aminek csak a hibás indirekt feltevés lehetett az oka. 3. ⇒ 1 Tegyük fel, hogy G körmentes, de bármely új élt hozzávéve a keletkező gráf tartalmaz kört. Ekkor azt szeretnénk megmutatni, hogy a G gráf összefüggő Indirekt tegyük fel, hogy a gráfban a és b pontok között nincs út (azaz a gráf nem összefüggő). Ekkor az ab élt a gráfhoz hozzávéve szintén körmentes gráfot kapunk, ami ellentmond a feltételnek. 1.27 Megjegyzés A fenti 4 rész-bizonyításból a tétel állításai következnek 1.28 Definíció Egy fát gyökeres fának nevezünk, ha címkézése során ki van jelölve egy pontja, az úgynevezett gyökérpont. 1.29 Definíció Egy fát abban az esetben nevezünk végesnek, ha nincsen benne végtelen út. 1.210 Tétel Minden legalább kétpontú fában van legalább két 1 fokszámú pont 1.211 Bizonyítás Végezzünk teljes

indukciót: • Induljunk ki egy kétpontú fából. Ebben az esetben ugyebár 2 darab 1 fokszámú pont van. • Tegyük fel, hogy n pontú fára is igaz, amennyiben n ≥ 2. • Ha az állítás igaz n pontra, vegyünk fel még egy pontot úgy, hogy a fa-szerkezet ne sérüljön. Ekkor a fa egyik leveléhez - melynek eddig 1 volt a fokszáma felveszünk még egy élet, ezáltal annak fokszáma 1-gyel nő, viszont az újonnan felvett pont fokszáma 1, így az új pont berajzolása után sem sérült az állítás. 10 http://www.doksihu 1.212 Tétel Minden n pontú fának n − 1 éle van 1.213 Bizonyítás Kezdetben a pontok száma 1, amely valóban 1-gyel nagyobb, mint az éleké, és az újabb élek berajzolásakor pedig mind a pontok, mind az élek száma 1-gyel nő, a különbség tehát nem változik. 1.214 Definíció Az olyan speciális n-pontú fát, melyben n − 1 elsőfokú és egy n−1-edfokú csúcs van csillagnak nevezzük. Az 5 ábra második alakzata egy csillag

1.215 Definíció Egy gráf erdő, ha komponensei fák Legyen a G gráf gyökérpontja r. r-ből a gráf tetszőleges r-től különböző v pontjába pontosan egy út vezet Ezen az úton a v-hez legközelebbi pontot v apjának, a többi v-vel szomszédos pontot pedig v fiainak nevezzük. Az r gyökérpontnak nincs apja, neki pedig valamennyi fia a szomszédja. 1.216 Definíció A levelek olyan, az r gyökérponttól különböző pontok, amelyeknek a fokszáma 1 1.217 Definíció A G gráf minden olyan részgráfját, amely fa, pontjainak halmaza pedig egyenlő G pontjaival, a G gráf feszítőfájának nevezzük Most bevezetjük a dolgozat alappiléreként szolgáló két definíciót. A következő definíciók általánosan igazak a gráfokra, nem csak fa-gráfokra. 1.218 Definíció Egy fát abban az esetben nevezünk címkézettnek, ha a fa-gráf pontjainak halmaza rögzítve van, azaz a csúcsai meg vannak számozva. 1.219 Definíció Nem adunk neveket a pontoknak, és két fát

azonosnak tekintünk, ha az egyik fa pontjainak átrendezésével megkaphatjuk a másik fát Ebben az esetben a fa címkézetlen fa. 1.220 Definíció Két fa-gráf azonos (izomorf), ha megadható olyan kölcsönösen egyértelmű (bijektív) megfeleltetés a két fa-gráf pontjai között, hogy az egyik fa bármelyik két pontja pontosan akkor van összekötve, ha a másik fában a hozzájuk rendelt pontok is össze vannak kötve. 11 http://www.doksihu Tehát amikor az izomorf fa-gráfokat nem különböztetjük meg egymástól, akkor beszélhetünk címkézetlen fákról. A 6 ábra két fáját izomorfnak tekintjük, ha nem vesszük figyelembe a csúcsok számozását. Ha ezt figyelembe vesszük, akkor a két fa különbözőnek tekintendő. 6. ábra 12 http://www.doksihu 2. fejezet Fák növesztése 2.1 Hogyan növesszünk fákat? Az igazi fákon folyamatosan nőnek újabb és újabb ágak. Ahogyan az erdőben növekszenek a fák évről-évre, ilyen módon gráfelméleti

értelemben vett fákat is tudunk növeszteni. A következő tétel a fák egyik legfontosabb tulajdonságát mondja ki: 2.11 Tétel A következő eljárással "növesztett" gráfok mindegyike fa, és minden fa megkapható ilyen módon. Az eljárás: • Kezdjük egyetlen ponttal • Ismételjük meg a következőt: ha egy G gráfot kaptunk, vegyünk fel egy új pontot, és kössük össze G valamelyik pontjával. 2.12 Bizonyítás Vizsgáljunk egy gráfot, amelyet a fenti eljárás alapján kaptunk meg. Mivel a kiinduló gráf fa, ezért elég belátni, hogy az eljárás során sohasem kapunk olyan gráfot, amelyik nem fa Legyen G a korábbi gráf, és G̃ az a gráf, melyet úgy kapunk, hogy egy új v pontot összekötünk G egy u pontjával, akkor G̃ is fa. G̃ összefüggő, mivel bármelyik két már korábban növesztett pontja között halad él, a v pont pedig akármelyik w ponttal összeköthető a vu él és az u-ból w-be vezető út összekapcsolásával.

Valamint G̃-ben nem lehet kör: mivel a v pont fokszáma 1, így rajta nem haladhat át kör. Egy olyan kör viszont, amelyik nem érinti v-t, csak 13 http://www.doksihu a G gráfban haladhat, arról pedig feltettük, hogy fa. A bizonyítás második felében megmutatjuk, hogy az eljárással minden fa megkonstruálható. Végezzünk a fa pontjai szerint indukciót • Ha a fának egy pontja van, akkor a fa a fenti eljárással keletkezett, az első lépésben. • Tegyük fel, hogy G-nek legalább két pontja van. Ekkor a 1210 tétel szerint G-nek van 1 fokszámú pontja, legyen v ilyen. Hagyjuk el G-ből a v pontot azzal az éllel együtt, amelynek ő az egyik végpontja; jelöljük az így kapott gráfot G̃-vel. • Be kell látnunk, hogy G̃ fa. G̃ összefüggő, mivel bármelyik két pontja összeköthető egy G-beli úttal, amely - mivel az 1 fokszámú pont nem illeszkedik rá teljes egészében G̃-ben halad • G̃-ben nem lehet kör, mert egy ilyen kör G-ben is kör

lenne. • Az indukciós feltevés szerint minden G-nél kevesebb pontot számláló gráf megkapható a fanövesztő eljárással, így G̃ is. A G gráfot éppen az eljárás második lépése szerint kaphatjuk meg G̃-ből. Ezzel a tételt bebizonyítottuk. 14 http://www.doksihu 3. fejezet Fák tárolási módjai Mielőtt elkezdenénk a címkézett fák tárolásának tárgyalását, szeretnék egy apró (vagy nem is olyan apró) megjegyzést tenni. Véges matematika tanulmányaim során egy n pontú fa címkézését 0-tól n−1-ig végeztük, valamint a szakirodalmak túlnyomó része is eképpen címkézi ezeket a speciális gráfokat. A dolgozatban megjelenő fák 1-től n-ig vanak számozva, ahol n a gyökér címkéje. Tanári tapasztalatok alapján ez a változtatás sokat segít a hallgatóknak az eljárások elsajátításában. A célunk az, hogy egy fát a számítógépen a lehető legkisebb memóriát igénybe véve tároljuk. 3.1 Szomszédsági mátrix A fák

számítógépen való tárolásának egyik módja a fa szomszédsági mátrixával való tárolás. Lényege, hogy a mátrixnak n oszlopa és n sora van Írjunk 1-est az i-edik sor j-edik helyére, ha az i és j pontok össze vannak kötve, és írjunk 0-t, ha nem. Tekintsük az ábrán látható fát 15 http://www.doksihu 7. ábra: 10 pontú címkézett fa A 7. ábrán lévő fa szomszédsági mátrixa:  0  0   0  0   0  0   0   1  0  1  0 0 0 0 0 0 1 0 1  0 0 0 0 0 1 0 0 0   0 0 0 1 0 0 0 0 0  0 0 0 0 0 1 0 0 0   0 1 0 0 0 0 0 0 1  0 0 0 0 0 0 0 0 1   1 0 1 0 0 0 0 0 1   0 0 0 0 0 0 0 1 0  0 0 0 0 0 0 1 0 0  0 0 0 1 1 1 0 0 0 3.11 Megjegyzés Ha a fa élei súlyozottak, akkor a szomszédsági mátrixban 1esek helyett a súlyok szerepelnek (értelemszerűen súlyozott esetben is a 0-k 0-k maradnak, mivel ha súlyozott gráf esetén két pont

nincs összekötve, akkor a köztük "futó" él súlya 0). 16 http://www.doksihu 3.12 Megjegyzés A mátrix főátlójában csak 0-k szerepelnek, mivel kikötöttük, hogy a fa egyszerű, így nincsen benne hurokél. 3.13 Megjegyzés Mivel a mátrix a főátlójára szimmetrikus, ezért elég csak a felét tárolni, de ez a módszer fák esetében még így is meglehetősen pazarló, (n2 −n) 2 bit tárhelyet foglal. 3.2 Éllistával történő tárolás Egy másik módszer az éllistával való megadása a fának. Célszerű, ha olyan listát készítünk, amelynek oszlopai a fa éleinek felelnek meg. A fenti ábrán látható gráf éllistás megadása: " 1 7 7 5 10 1 9 10 5 6 8 8 7 # 2 4 3 10 10 Ennek a módszernek a tárolásához szükséges tárhely 2 · n · log2 n nagyságrendű, ez sokkal kisebb, mint 3.3 (n2 −n) , 2 nagy n-ekre különösen. Apakód A következőkben bemutatásra kerül egy olyan tárolási mód, amely már csak (n

− 1) · dlog2 (n)e bit tárhelyet foglal, ez a "kódolás" az apakód. Tekintsük jelen esetben a példa alapján a 10 címkéjű pontot ezután kitüntetett pontnak, legyen ez a fa gyökérpontja. Egy élt úgy adhatunk meg, hogy előbb a gyökértől távolabbi, majd a gyökérhez közelebbi végpontját írjuk le, az éleket pedig rendezzük az első végpontjuk szerint növekvő sorrendbe. 3.31 Megjegyzés 1-től n-ig történő címkézésnél n a gyökérpont A 7. ábrán látható fa táblázata: " 1 2 3 4 5 6 7 8 9 10 7 5 7 10 10 10 1 8 17 # http://www.doksihu A táblázat első sorában a számok növekvő sorrendben vannak, hiszen kikötöttük, hogy az éleket az első végpontjuk szerint rendezzük. A 10 azért nem szerepel, mert az egyetlen másik pontnak sem fia. Ha egy fa n pontból áll, akkor a fa táblázatában az első sor mindig az 1, 2, . , n − 1 számokból áll 3.32 Megjegyzés Az apakód messze nem optimális Könnyen találhatunk

olyan példát, melyben meg van adva egy kétsoros táblázat, ahol az első sorban 1-től n − 1ig szerepelnek számok, az alsó sorban pedig tetszőlegesen szerepelnek 1-től n-ig, a kódolás viszont nem egy fa-gráfot fog vissza adni. Például: " # 1 2 3 2 3 1 Itt már a kódból látszik, hogy ez nem egy fát fog adni. A kódból le- olvasható, hogy van benne kör az " # " # " # 1 2 3 oszlopok miatt. Ezáltal a tet2 3 1 szőlegesen konstruált kétsoros táblázat nem minden esetben definiál fát. A fa kódja tetszőlegesen folytatódhat, a lényeg, hogy tartalmazza a fenti 3 oszlopot, vagy olyan oszlopokat, melyek kört definiálnak. 3.4 Prüfer kód A Prüfer kód a fák tárolásának elméletileg egyik leghatékonyabb módszere. A Prüfer-kód az előbb bemutatott módszer egy finomítása, amelynek segítségével egy n pontú címkézett fát n − 2 tagú sorozattal adhatunk meg, amelynek tagjai 1 és n közötti számok. n pontú fa esetében

jelölje n a fa gyökerét, valamint az éleket úgy rendezzük, hogy mindig a fiú legyen előbb. 3.41 A Prüfer-kód megkonstruálása Készítsünk táblázatot, ahol az oszlopok az éleknek felelnek meg, és mindig az n-től távolabbi pont szerepel a felső, a pont apja az alsó sorban. A szabály, amely szerint rendezzük az éleket, a következő: • Keressük meg az 1 fokszámú pontok közül a legkisebb címkéjűt, a táblázatban pedig rögzítsük azt az élt, amelyiknek ez a pont az egyik végpontja. Ha 18 http://www.doksihu továbbra is a 7. ábrát tekintjük, a táblázat első oszlopa " # 2 7 lesz. • Töröljük a pontot, az eljárást pedig ismételjük a megmaradt fával, azaz ismét megkeressük a legkisebb címkéjű 1 fokszámú pontot, és beírjuk " # a táblázatba 3 azt az élt, amelyre illeszkedik; példánk alapján a 2. oszlop lesz. 5 • Az eljárást addig folytatjuk, amíg minden él sorra nem kerül. Az így kapott táblázat a

fa bővített Prüfer-kódja. A bővített jelző arra vonatkozik, hogy a Prüfer-kód a táblázatnak csak egy részéből áll. Az ábránkon látható fa bővített Prüfer-kódja: " 2 3 4 5 6 7 9 8 1 # 7 5 7 10 10 10 8 1 10 A "valódi" Prüfer-kód ennek csak egy része lesz. A bővített Prüfer-kód második sorának utolsó tagja mindig n lesz (jelen esetben 10), ez ugyanis az utolsónak figyelembe vett él egyik végpontja A 10 csak az utolsónak figyelembe vett élre illeszkedhet, mivel a 10 mindvégig nagyobb, mint amit elhagytunk. Mivel az apakód esetében elhagyhattuk az első sort, itt is meg kellene tennünk ezt a lépést, ha kevesebb tárhelyet foglaló kódolást szeretnénk, mint az előző eljárásnál. A Prüferkód esetében viszont nem nyilvánvaló ránézésre, hogy mi lehet az első sor, itt ugyanis - mint a példában is látható - nem növekvő sorrendben találhatók a számok. A 341 következmény fogja eloszlatni kétségeinket. 3.41

Következmény Elegendő, ha a bővitett Prüfer-kód utolsó sorát tároljuk, és még ebből is elhagyhatjuk az utolsó elemet, hiszen erről tudjuk, hogy az mindig n. 3.42 Definíció Egy bővített Prüfer-kód második sorának első n−2 tagját nevezzük a fa Prüfer-kódjának 3.42 Példa Tekintsük a következő karakter-sorozatot: 554316. A 341 következmény alapján feltehetjük, hogy ez a 6 darab szám egy fa Prüfer-kódja. 19 http://www.doksihu • Mivel tudjuk, hogy a Prüfer-kód n − 2 tagú sorozat, így a karakter-sorozat végére írjunk 8-at. • Kezdjük el megkonstruálni az első sort; Keressük meg azt a legkisebb számot 1 és 8 között, amelyik nem szerepel az 554316 között. Ez ugyebár a 2 " # 2 5 5 4 3 1 6 8 • Most nézzük a következőt: Takarjuk le - az egyszerűbb áttekinthetőség kedvéért - a második sorban található első 5-öst, és tekintsük a két sorban lévő számokat aszerint, hogy melyik az a legkisebb 1 és 8

közötti szám, mely nem szerepel így a két sorban. Ekkor ugyebár a 7 a következő tag az első sorban • A következő lépésnél azokat a számokat kell figyelembe venni, melyek pirossal vannak jelölve: " # 2 7 5 5 4 3 1 6 8 Így tehát a következő beírandó tag az első sorban az 5. • Az eljárást folytatva a következő két sort kapjuk: " # 2 7 5 4 3 1 6 5 5 4 3 1 6 8 A fenti Prüfer-kóddal tárolt fa: 8. ábra: az 554316 kóddal tárolt fa 20 http://www.doksihu A legegyszerűb ellenőrzési mód, mellyel megállapíthatjuk, hogy eljárásunk helyes volt-e, ha a 8. ábra Prüfer-kódját meghatározzuk Ha ez megegyezik az eredeti 6 tagból álló karakter-sorozatunkkal, akkor az eljárást helyesen végeztük. • Az első elhagyható pont a 2, így feljegyezzük a szomszédját, azaz az 5-öt. • A következő a 7, feljegyezzük az 5-öt. • Elhagyhatjuk az 5-öt, ⇒ 554. • A következőkben 554 ⇒ 5543 ⇒ 55431 ⇒ 554316 ⇒ 5543168. •

A 8-at elhagyhatjuk ⇒ Így az ellenőrzés sikeres volt, megkaptuk a Prüferkódot. 3.43 Megjegyzés Az előzőekben bemutatott eljárás általánosításának bizonyítása a dolgozat 4. fejezetében található 3.43 Prüfer-kód összefoglalása Mire is használhatjuk a Prüfer-kódot? • A következő fejezetben látni fogjuk, hogy egy nagy jelentőséggel bíró formula, a Cayley tétel bizonyítására. • A fák tárolásának elméletileg leghatékonyabb módja. Minden n pontú címkézett fának megfeleltethetünk egy karaktersorozatot, mely számokból áll Ezt a számot a kettes számrendszerben felírva d(n − 2) · log2 ne hosszúságú 01 sorozatot kapunk. • Tegyük fel, hogy n pontú fákat generálunk oly módon, hogy minden fa ugyanolyan valószínűséggel jelenhessen meg a kimeneten. A Prüfer kód eljárásának ismeretében elegendő, ha generálunk n−2 darab véletlen számot 1 és n között, majd visszakeressük, hogy ez végülis melyik fának a

kódja. 3.44 Megjegyzés Paul Ernst Heinz Prüfer ( 1896 november 10 - 1934 április 7.) német matematikus , aki elsősorban algebrával és csoportelmélettel foglalkozott Wilhelmshaven-ben született, a Berlini Egyetemen végezte tanulmányait, Abel-csoportok témakörben írta doktori disszertációját. A nevéhez fűződő Prüferkódot 1918-ban alkotta meg 21 http://www.doksihu 4. fejezet Címkézett fák száma Az, hogy a fákat megcímkézzük vagy sem, a fák összeszámlálása során lényeges. Ebben a fejezetben megismerkedünk a címkézett fák számára vonatkozó Cayley tétellel. A tételnek több bravúros bizonyítása is létezik A teljesség igénye nélkül bemutatásra kerül ezek közül három. Valamint Arthur Cayley: Theorem on trees című cikke, amelyben először publikálta 1889-ben a címkézett fák számára vonatkozó tételét a Quarterly Journal of Pure and applied Mathematics folyóiratban. A dolgozatom mellékletében megtalálható az

eredeti cikk digitalizált változata, valamint a cikk néhány érdekesebb részének fordítása is. 4.1 Cayley tétele 4.11 Tétel Az n pontú címkézett fák száma nn−2 4.11 1. Bizonyítás indukcióval Cayley tételének első bizonyításához először egy segédállítást kell kimondanunk, valamint bebizonyítanunk. 4.12 Állítás Legyenek v1 , , vn adott pontok és d1 , , dn adott egészek, melyekre P teljesül, hogy di = 2 · n − 2, di ≥ 1. Bizonyítandó, hogy azon fák száma a {v1 , . , vn } halmazon, melyekben a vi foka di (i = 1, , n), a következő: (n − 2)! . (d1 − 1)! · · · · · (dn − 1)! 22 http://www.doksihu 4.13 Bizonyítás Végezzünk n szerinti indukciót P P n = 1-re: di = 2 · n − 2-ből következik, hogy di = 2 · 1 − 2 = 0. P n = 2-re: di = 2 · n − 2 => 2 · 2 − 2 = 2. Mivel k X di = 2 · n − 2 < 2n, i=0 van olyan di , amelyik 1-gyel egyenlő. Feltehetjük, hogy dn = 1 Hagyjuk el a vn pontot.

Bármelyik fát is tekintjük, vn össze van kötve valamelyik vj ponttal, amely n > 2 esetén nem levél, tehát dj > 1. 1 ≤ j ≤ n − 1, és vn elhagyásával egy olyan fához jutunk, a {v1 , . , vn−1 } pontokon, melynek fokszámai d1 , , dj−1 , dj − 1, dj+1 , . , dn−1 Megfordítva, ha adott egy fa a {v1 , . , vn } pontokon, és a d1 , . , dj−1 , dj − 1, dj+1 , , dn−1 fokokkal, akkor vj -t a vn -nel összekötve, egy fát kapunk a {v1 , . , vn } pontokon, a d1 , . , dn fokokkal A {v1 , . , vn−1 } pontokon d1 , , dj−1 , dj −1, dj+1 , , dn−1 fokokkal a fák száma: (n − 3)! = (d1 − 1)! . (dj−1 − 1)! · (dj − 2)! · (dj+1 − 1)! (dn−1 − 1)! = (dj − 1) · (n − 3)! . (d1 − 1)! . (dn − 1)! dj = 1-re is teljesül, mivel akkor ez is 0. Így a fák száma a {v1 , , vn−1 } pontokon a d1 , . , dn fokszámokkal: n−1 X (dj − 1) · (n − 3)! = (d1 − 1)! . (dn − 1)! i=1 n−1 X j=1 ! (dj

− 1) · (n − 3)! (n − 2) · (n − 3)! = , (d1 − 1)! . (dn − 1)! (d1 − 1)! . (dn − 1)! Ezzel az állítást bebizonyítottuk. Tehát Cayley tételének bizonyítása: n ponton a fák száma: 23 http://www.doksihu X d1 ,.,dn ≥1 d1 +···+dn =2·n−2 = (n − 2)! = (d1 − 1)! . (dn − 1)! X k1 ,.,kn ≥0, k1 +.kn =n−2 (n − 2)! = k1 ! . kn ! = (1 + · · · + 1) n−2 = nn−2 . | {z } n A fenti bizonyítás megtalálható Lovász László: Kombinatorikai problémák és feladatok című könyvében. 4.12 2. Bizonyítás Prüfer kód segítségével A Cayley tétel egyik legismertebb bizonyítási módja a Prüfer-kód segítségével történő bizonyítás. A Prüfer-kóddal kapcsolatos megállapítások megtalálhatóak a dolgozat 3. fejezetében A következőkben bemutatásra kerül, hogy miért is alkalmazható a Prüfer-kód a Cayley-tétel bizonyításaként 4.14 Állítás A Prüfer-kód optimális, azaz minden n − 2 tagú sorozat,

amelynek tagjai 1 és n közötti számok, egy n pontú fa Prüfer-kódja. 4.15 Bizonyítás Nyilvánvaló, hogy minden fához egyértelműen tartozik egy Prüfer-kód Azt kell még belátni, hogy minden Prüfer-kódhoz (legyen ez v1 , v2 , , vn−2 ) is egyértelműen létezik egy fa, amit leír. Abból, hogy hány számból áll a kód azonnal kapjuk n értékét, hiszen a sorozat n − 2 hosszú. Legyen wk az a pont, amelynek elhagyásakor vk -t feljegyeztük. Tehát ha meghatározzuk wk -t minden k-ra, akkor már egyértelműen rekonstruálható a fa, hiszen élei pontosan a {wk , vk } párok. A wk -k pedig könnyen meghatározhatók, hiszen w1 a legkisebb olyan szám, ami nem fordul elő v1 , v2 , . , vn−1 között, általánosan pedig wk az a szám, ami nem fordul elő w1 , w2 , . , wk−1 , vk , , vn−1 számok között Ilyen szám mindig létezik, hiszen ha mind különböző lenne, akkor is csak n−1 -et zártunk ki az n-ből. Megkaptuk tehát a {v1 , w1 }, {v2 ,

w2 }, . {vn−1 , wn−1 } éleket Be kell látnunk, hogy ezek fát határoznak 24 http://www.doksihu meg (tehát körmentes gráfot), és ekkor a gráf Prüfer-kódja éppen v1 , v2 , . , vn−1 Tegyük fel indirekt módon, hogy van a gráfban kör. A Prüfer-kód "visszafejtése" során minden egyes újabb wi felírásakor egy újabb pontot, és egy újabb élet kapunk meg. Kell lennie egy olyan lépésnek, amikor a kör utolsó élét húzzuk be, de ekkor egy olyan wi -t kellene felírnunk, amely már korábban szerepelt, ez azonban a fenti eljárásban nem lehetséges. Tehát minden n − 1 elemű sorozathoz, amelyben az első n − 2 elem mindegyike lehet {1, 2, . , n} és az utolsó elem n, tartozik egy fa, és különböző sorozatokhoz különböző fa tartozik. A bizonyítás forrása: http://hu.wikipediaorg/wiki/Cayley-formula 4.13 3. Bizonyítás lineáris algebrai módszerekkel Legyen Tn az n pontú címkézett fák száma. Gondolhatunk Tn -re úgy,

mint a Kn teljes gráfban lévő feszítőfák számára. Most pedig vizsgáljunk egy tetszőleges összefüggő egyszerű gráfot a V = {1, 2, . , n} csúcshalmazon, ahol t(G)-vel jelöljük a feszítőfák számát, azaz Tn = t(Kn ). Az alábbi nevezetes eredmény Kirchoff mátrixfa tétele Tekintsük a B = (bij ) mátrixot, G incidenciamátrixát, melynek sorait V , oszlopait E elemei indexelik, és bie = 1 vagy 0 aszerint, hogy i ∈ e vagy i ∈ / e. Vegyük észre, hogy |E| ≥ n − 1, mivel G összefüggő. Minden oszlopban az egyik 1-est −1-re cseréljük tetszőlegesen (ez G irányításának felel meg), és az új mátrixot C-nek nevezzük. Ekkor M = C · C T szimmetrikus n × n-es mátrix, melynek főátlóbeli elemei a d1 , . dn fokszámok 4.16 Állítás Minden i = 1, , n-re t(G) = detMii , ahol Mii úgy keletkezik M ből, hogy kitöröljük az i-edik sort és az i-edik oszlopot 4.17 Bizonyítás A bizonyítás kulcsa a Binet-Cauchy-tétel: Ha P (r×s)-es, Q(s×

r)-es mátrix (r ≤ s), akkor det(P ·Q) megegyezik a megfelelő (r ×r)-es részmátrixok determinánsainak szorzatainak összegével, ahol a "megfelelő" szó azt jelenti, hogy P -ből és Q-ból ugyanazt az r oszlopot és r sort vesszük. Ez Mii -re nézve azt jelenti, hogy detMii = X detN · detN T = N X N 25 (detN )2 , http://www.doksihu ahol N a C{az i-edik sor } összes (n − 1) × (n − 1)-es részmátrixán fut végig. N n − 1 oszlopa G egy n − 1 élű, n csúcsú részgráfjának felel meg, most már csak azt kell megmutatni, hogy detN = ± 1, ha ezek az élek fát feszítenek ki, egyébként 0. Tegyük fel, hogy n − 1 él nem feszít ki fát. Ekkor van olyan komponens, amely nem tartalmazza i-t. Az ennek a komponensnek megfelelő sorok összege 0, következésképpen ezek a sorok lineárisan függetlenek, vagyis detN = 0. Most pedig tegyük fel, hogy N oszlopai kifeszítenek egy fát. Ekkor van olyan j1 6= i csúcs, melynek foka 1; legyen az

erre illeszkedő él ei . Kitörölve j1 -et és e1 -et egy n − 2 csúcsú fát kapunk. Ebben is van olyan j2 6= i 1-fokú csúcs, melyre az e2 él illeszkedik. Folytassuk ezt az eljárást amíg j1 , j2 , jn−1 -et és e1 , e2 , en−1 -et (ji ∈ ei ) meghatároztuk. Ezután permutáljuk a sorokat és oszlopokat úgy, hogy jk a k-adik oszlopba kerüljön. Mivel a konstrulciónk miatt k < l-re jk ∈ / el , ezért az új N 0 mátrix alsóháromszög-mátrix, melynek főátlójában minden elem 1 vagy −1. Vagyis detN = ±detN 0 = ±1, és készen is vagyunk. A G = Kn speciális esetben nyilvánvalóan Mii megegyezik a következő mátrixszal:   n − 1 −1 . −1     −1 n − 1 −1    . .  .  . .    −1 −1 . n − 1 Már csak az Mii mátrix determinánsát kell meghatároznunk. Ugyebár Mii mérete (n − 1) × (n − 1). Adjuk hozzá az első sorhoz a többi sort Ekkor az első sor első eleme: (n − 1) + (−1) · (n

− 2), azaz 1. Az első sorban minden elem 1 lesz Most adjuk hozzá az első sort az összes többihez. Ekkor a következő mátrixot kapjuk:   1 0 . 0   0 n 0   .  . . .   .   0 0 . n Ebben az esetben a determináns a főátlóbeli elemek szorzata: nn−2 . A bizonyítás Martin Aigner - Günter M. Ziegler: Bizonyítások a Könyvből című könyvból származik. 26 http://www.doksihu 4.2 Példák címkézett fákra • 2 pontú fának 1 féle címkézése létezik. • 3 pontú fának 3 féle címkézése lehet. • A 4 pontú fák esete egy kissé már összetettebb. A formula alapján 44−2 , azaz 16 féle címkézés létezik. Négy pontú fából kétféle létezik; a csillag, valamint az út. Két cimkézett csillag pontosan akkor izomorf, ha gráfok (n − 1)-edfokú pontjaira azonos címke került. Így éppen annyi címkézett csillag készíthető, ahány féleképpen a "középpont" kiválasztható, ez pedig

n-féleképpen tehető meg. Jelen esetben n = 4 9. ábra: A 4 pontú csillag címkézései Mivel a formula alapján 16 különböző címkézés van, már kizárásos alapon is 12 féleképp számozhatjuk meg a 4 pontú utat, de ez természetesen leszámlálással is megkapható. Valójában 4 pont permutációinak számát keressük. A 4 pontot 4 · 3 · 2, azaz 24 féleképpen számozhatjuk, de ebből ki kell vonnunk azokat az eseteket, amikor a két "végpont" páronként megegyezik, így valójában csak az számít, hogy a 27 http://www.doksihu belső 2 pontot hogyan számozom. Így 4 · 3, azaz 12 féle címkézése van ezeknek a speciális fáknak. Meg is kereshetjük a címkézéseket. Tekintsük az 1, 2, 3, 4 pontok sorrendjét A permutációk száma 4!, azaz 24. A lehetséges sorrendek: – 1234; 1243; 1324; 1342; 1423; 1432; – 2134; 2143; 2341; 2314; 2431; 2413; – 3124 ; 3142 ; 3241 ; 3214 ; 3412; 3421; – 4123; 4132 ; 4231 ; 4213; 4312; 4321; Csak a

pirossal kiemelt számnégyeseket vesszük figyelembe, mivel a többiek olyan számok által megcímkézett fákat adnak ki, melyek már szerepelnek. Így könnyen látható, hogy 12 + 4, azaz 16 féleképpen tudunk 4 pontú fákat megcímkézni, a következőképpen: 10. ábra 28 http://www.doksihu • 5 pontú különböző fából 3 féle van. A csillag, az út, valamint az olyan csillag, ahol az alakzat egyik úgynevezett karjára még egy pont illeszkedik A következő ábrán megtalálható a 3 féle 5 pontú fa. 11. ábra Cayley tétele szerint ugyebár az 5 pontú fáknak 53 = 125 féle címkézése létezik. A 11. ábra első alakzata - a csillag - 5 féleképpen számozható, mivel 1-től 5-ig tudjuk a csillag közepébe beírni a számokat. A második alakzat ugyanezen az ábrán 5 · 4 · 3 féleképp címkézhető hasonló gondolatmenettel, mint ahogyan a 4 pontú fáknál. A harmadik fa 5! 2 = 60 féleképpen címkézhető, így összesen 60 + 60 + 5 = 125 féle

számozás van. • 6 pontú fák esetében 64 =1296 címkézés létezik. A következő ábrák szemléltetik a 6 pontú fák különböző alakzatait. 29 http://www.doksihu 12. ábra Az első alakzat - a csillag - 6 féleképpen számozható, hiszen csak az számít, hogy a csillag középpontjában, azaz a gyökérpontban milyen szám szerepel. A második fánál, az útnál a figyelembe veendő pontok a négy közbülső pont, így 6 · 5 · 4 · 3, azaz 360 darab létezik. A harmadik gráf esetében szintén számozás van. 13. ábra 30 6! 2 http://www.doksihu A 4-essel megjelölt ábra 6 · 5 · 4, azaz 120 féleképp címkézhető, az ötödik 6 · 5 · 4 · 3 = 360, az utolsó ábra pedig 90 féleképpen. 4.21 Néhány szó Arthur Cayleyről Arthur Cayley (Richmond, 1821. augusztus 16 - Cambridge, 1895 január 26.), brit matematikus Már gyermekként is örömét lelte összetett matematikai problémák megoldásában. Már korán nagy érdeklődést mutatott a

számok iránt. 14 évesen a King’s College diákja lett, ahol a tanárai felfedezték rajta a matematikai zsenialitás jeleit, s azt tanácsolták szüleinek, hogy ennek megfelelően taníttassák. Fiatalon, 17 évesen kezdte meg tanulmányait a cambridge-i Trinity College-ban, s a Cambridge Mathematical Journal-ba már 20 évesen 3 cikket publikált, melyeknek témáit Lagrange és Laplace munkássága ihlette. Egyetemista éveit a senior wrangler cím és az első Smith-díj elnyerésével koronázta meg. Ezt követően megszerezte az MA diplomát, és elnyert egy ösztöndíjat. Ezután még az egyetemen maradt 4 évig, mely idő alatt oktatott pár diákot, de fő tevékenysége a Mathematical Journal-be írandó 28 tanulmányának előkészítésére szorítkozott. 42 évesen elnyerte a Cambridge-i Egyetem Lady Sadler-ről elnevezett professzori székét, melyet még a Lady hozatott létre saját vagyonából az elméleti, tiszta matematika fejlesztésének céljára. 1876-ban

publikálta egyetlen könyvét, Elliptic Functions címmel. 1872-ben a Trinity College címzetes tagja, 1875-től pedig rendes tagja. Cayley híressé vált arról is, hogy számos módon próbálta elősegíteni a nők egyetemi tanulmányait, mind oktatás terén, mind a Newnham College - Cambridge nők számára alapított intézménye - bizottsági tagjaként. 31 http://www.doksihu 5. fejezet Címkézetlen fák Tekintsük most a számozatlan fákat. Ezeket úgy definiálhatjuk, mint számozott fák ekvivalencia-osztályait, ahol két számozott fát ekvivalensnek tekintünk, ha izomorfak, vagyis alkalmas átszámozással ugyanaz a számozott fa válik belőlük. Feltesszük, hogy egy-egy ilyen ekvivalencia-osztályt egy elemével, vagyis egy számozott fával adunk meg (hogy konkrétan melyikkel, az most nem lényeges). Mivel minden számozatlan fa legfeljebb n! féleképpen címkézhető (számozásai nem biztos, hogy mind különbözok, mint számozott fák! ), ezért a

számozatlan fák száma legalább nn−2 n! Jelöljük az n pontú címkézetlen fák számát Tn -nel. Tn -re nem ismerünk olyan képletet, mint amely a Cayley-tételben szerepel, csak közelítő értékeket tudunk megadni. 5.1 Közelítő képletek Egy n pontú címkézetlen fa pontjai legfeljebb n! féleképpen címkézhetők meg. Azt tudjuk, hogy n pontú címkézett fák száma nn−2 , így a számozatlanoké legalább nn−2 . n! Ahhoz, hogy ezt pontosabban meghatározzuk, ki kell mondanunk egy tételt. 5.11 Tétel (Stirling formula) n
n √ 2 · π · n, e ahol ≈ a következő képpen küszöbölhető ki: n! ≈ 32 http://www.doksihu n! √ n n ) e A Stirling formula alapján 2πn nn−2 n! 1 (n ∞) hozzávetőlegesen en . √ 5 n 2 2πn Ez egy alsó korlát. Célunk, hogy valamilyen módon felső korlátot adjunk meg A fő kérdés az, hogy van-e gazdaságosabb tárolási módja a számítógépen annál a címkézetlen fáknak, mint hogy

megcímkézzük őket, és címkézett faként tároljuk? De hogyan is tároljunk egy fát, ha csak a formájára vagyunk "kíváncsiak", és lényegtelen számunkra azon információ, hogy a fa csúcsait milyen címkékkel láttuk el. 5.11 Planáris kód Tekintsünk egy címkézetlen fát, amely úgy van ábrázolva, hogy egyetlen éle sem metsz másikat (általában a fákat így ábrázoljuk, ez az ábrázolási mód minden fa esetében alkalmazható), valamint jelöljünk ki egy elsőfokú pontot, mely ezentúl gyökérpont lesz. • Képzeljük el a fa éleit úgy, mintha falak lennének, melyeket körbe tudunk sétálni. • Induljunk a gyökértől. • Képzeletben sétáljunk körbe az élek mentén úgy, hogy a képzeletbeli fal mindvégig a jobb kezünk felől legyen, valamint egy lépés legyen a képzeletbeli körút egy élre eső szakasza. • Jegyezzünk fel egy 1-est, amennyiben távolodunk séta közben a gyökértől, és jegyezzünk fel 0-t, ha

közeledünk a gyökér felé. A fa-szerkezet miatt ez mindig egyértelmű, hiszen nincs benne kör. • Ezen eljárást mindaddig folytatva, amíg vissza nem érünk a gyökérbe 2·(n−1) hosszúságú 01 sorozatot kapunk. Ezen 01 sorozatot nevezzük a címkézetlen fa planáris kódjának. 33 http://www.doksihu 5.12 Állítás Bármelyik címkézetlen fát egyértelműen meghatározza a planáris kódja. 5.13 Bizonyítás Képzeljük el, hogy a fát hó lepte el, és mi pedig csupán a kódját ismerjük. Megkérünk valakit, hogy verje le a fáról a havat, közben mi a kódot követjük. Tapasztalat: Amikor 1-est látunk, a segítőkész partnerünk egy lépéssel távolabb kerül a gyökérponttól, és lesöpri az élt, melyen haladt. Ebben az esetben egy "új" él bukkan elő. Amikor pedig a kódban 0 következik, segédünk egy már megtisztított ág mentén a gyökér irányába lép egyet. Térjünk vissza a fa megkonstruálására rajzolással; csak sorra

kell venni a planáris kódot elemenként úgy, hogy folytonosan haladunk az ágak mentén, megszakítás nélkül. Amikor 1-es következik, egy új ponthoz húzunk egy élt, amikor pedig 0 következik, akkor a vonal visszafelé halad a gyökér irányába. Így tehát a planáris kód meghatározza a fát. Az előbbi állítás bizonyításának ötlete Lovász-Pelikán-Vesztergombi: Diszkrét matematika című könyvből származik. 5.14 Megjegyzés n pontból álló planáris kódok száma 22(n−1) = 4n−1 , így az n pontú címkézetlen fák számának ez egy felső korlátja. 5.15 Tétel Az n pontú címkézetlen fák Tn száma kielégíti a következő egyenlőtlenséget: nn−2 ≤ Tn ≤ 4n−1 . n! 5.16 Megjegyzés • Ha n > 30, akkor a képlet egyszerűbbé válik; 2n ≤ Tn ≤ 4n . • Egy címkézetlen fát a gyökér választásától függően több planáris kóddal is megadhatunk. • Nem minden 2 · (n − 1) hosszúságú sorozat planáris kód: A sorozatnak

1-gyel kell kezdődnie (mivel minden esetben távolodunk a gyökértől), valamint 0-val kell végződnie (értelem szerűen). 34 http://www.doksihu • Planáris kód esetében a fát kódoló karakter-sorozatban ugyanannyi 1-esnek és 0-nak kell szerepelnie, hoszen amennyit távolodunk a gyökértől, ugyanannyi lépéssel tudunk oda visszatérni. • Egy n pontú fa tárolásához 2 · n karakterre van szükség, ezáltal a planáris kód kifejezetten gazdaságos tárolási módja a címkézetlen fáknak. • A gyökérpont megválasztása során ügyeljünk arra,hogy elsőfokú pontból induljunk. – Ha elsőfokúból indulunk és korábban megállunk, amikor még nem értünk végig minden élen, szükségképpen több 1-esnek kell lennie a kódban, mind 0-nak. 5.17 Megjegyzés Ha nem elsőfokú pontot jelölünk ki gyökérnek és valahol megállunk, az 1-esek száma ≥ 0-k száma egyenlőtlenségnek kell teljesülnie Valamint ha magasabb fokú pontot jelölünk ki

gyökérpontnak, nem minden esetben lesz egyértelmű, hogy merre járjuk körbe a fát. Vegyünk példaképp egy csillagot Ha a középpontból kezdjük a körbejárást, folyamatosan vissza fogunk jutni a gyökérbe, és ilyenkor felmerül a kérdés, hogy merre menjünk tovább. Ez a probléma fennáll olyan esetekben is, mikor a fának több úgynevezett ága van, mint például a 13. ábra 6-os sorszámmal megjelölt fája (természetesen a csillag is egy ilyen típusú fa-gráf). Összefoglalva tehát a legkézenfekvőbb megoldás, ha elsőfokú pontot jelölünk ki gyökérnek, és onnan kezdjük el "kódolni" a planáris kódot. 5.12 Példák planáris kóddal történő kódolásra Nézzünk néhány példát planáris kódra: • A csillag planáris kódja: 1101010100, amennyiben a csillag 6 pontból áll • Az út (egyik lehetséges) planáris kódja 6 pontú fa esetén: 1111100000 • A 12. ábra 3-massal jelzett gráfjának kódja: 1101110000 • A 13. ábra

4-essel megjelölt fa kódja: 1101011000 Tekintsük az eljárást visszafelé. Tegyük fel, hogy meg van adva egy 2n hosszú, 0-kból és 1-esekből álló karakter-sorozat, jelen esetben 1100101100. Ez lehet-e egy 35 http://www.doksihu fa-gráf planáris kódja? Nos, ugyebár az a feltétel teljesül, hogy a kódban ugyanannyi 1-es, valamint 0 van. A kód 1-essel kezdődik, és 0-val végződik, tehát ennek a kikötésnek is megfelel kódunk. Az 513 bizonyításban megjelenő eljárás segítségével rekonstruáljuk a fát. • Rajzoljunk le egy pontot; ez legyen a gyökérpont. Húzzunk be 2 élt, mivel a kód 2 darab 1-essel kezdődik. • Majd írószerszámunkkal térjünk vissza a gyökérbe, hiszen a karakter-sorozat 3. és 4 tagja 0 • Ismét egy élt indítsunk a gyökérből, majd térjünk vissza a gyökérbe. • Rajzoljunk be ismét azt a 2 élt, melyet planáris kódunk meghatároz. Ha megkonstruáltuk a fát, a 13. ábra 5-össel jelzett fáját kellett, hogy

kapjuk 5.18 Megjegyzés Pólya György bebizonyította, hogy az n pontú címkézetlen fák száma n növekedtével a · n −5 2 bn -hez közelít, ahol a = 0, 5349 . és b = 2, 9557 bonyolult módon definiált valós számok. 36 http://www.doksihu 6. fejezet Összefoglalás Foglaljuk össze, mit is tudunk a címkézett, valamint címkézetlen fák számáról. Fa-gráfok tárolására alkalmas technikák: • Szomszédsági mátrix, a tárolásához szükséges tárhely (n2 −n) . 2 • Éllistával történő tárolás, szükséges bitek száma 2 · n · log2 n. • Apakód segítségével, szükséges tárhely (n − 1) · dlog2 (n)e bit. • Prüfer kóddal való tárolás, a felhasznált bitek száma d(n − 2) · log2 ne. Kétféle fa létezik a szakdolgozat témájának szemszögéből: címkézett és címkézetlen. • Címkézett fák száma Cayley tétele szerint n pontra nn−2 • A címkézett fák számára csak közelítő képletünk van, n pontú fára

nn−2 ≤ Tn ≤ 4n−1 . n! A következő táblázat n pontú címkézett és címkézetlen fák számát tartalmazza: n 1 2 3 4 5 6 7 8 címkézett fák száma 1 1 3 16 125 1296 16807 262144 címkézetlen fák száma 1 1 1 2 3 6 11 23 37 http://www.doksihu 7. fejezet Mellékletek 7.1 Arthur Cayley: Theorem on trees Cayley cikke: 38 http://www.doksihu 39 http://www.doksihu 40 http://www.doksihu A tétel fordítása: Arthur Cayley: Theorem on trees (Quarterly Journal of Pure and applied Mathematics 23. kötet (1889) , 376-378 oldal) A címkézett fák száma, melyeknek n-1 csúcsa van, jelölje ezeket α, β, γ, . =nn−2 . Például n = 3 esetén a fák száma 4, csúcsai legyenek α, β, γ, δ, ami 42 = 16, ahogyan az 1. alak mutatja az ábrán α, β, γ, δ 12 különböző módon elrendezhető (tekintsük αβγδ-t ekvivalensnek δγβα-val),és a 2. alak is 4 pontból áll, legyen az α helye foglalt:az egész számosság így 12 + 4 =

16.() A tisztánlátás kedvéért legyen n egy nagyobb érték, mondjuk n = 5. Állítom, hogy a tétel pontos esete a következő: A fák száma legyen (α, β, γ, δ, , ζ)=, a kifejezések száma : ((α + β + γ + δ +  + ζ)4 ), αβγδζ, = 64 = 1296, és itt azonnal látszani fog, hogy ez fogja adni a pontos megoldást bármilyen n értékre. Több fához használom a következő jelölésrendszert: Például az 1. alak a mutatott ábrán, az ágak αβ,βγ,γδ; és a fáról elmondható, hogy αβ 2 γ 2 δ ( azaz az α és β pontok csak csak egyszer, míg a γ és δ pontok kétszer szerepelnek ; Hasonlóan az ágak αβ, βγ,γδ, és a fáról elmondható, hogy α3 βγδ ( azaz az α pont 3-szor, a β, γ, δ pontok csak egyszer szerepelnek.)() 41 http://www.doksihu Tehát ebben az esetben: Ez létezik így, írom: (α + β + γ + δ +  + ζ)4 αβγδζ = 1 α4 6 6 + 4 α3 β 30 + 6 α2 β 2 15 =⇒αβγδζ; 2 120 90 + 12 α βγ 60 720 + 24

αβγδ 15 360 Ahol a számok a bal oldali oszlopban a polinom együtthatói, amelyek negyed fokúak, és a jobboldali oszlop számai az egyes típusok kifejezéseinek számai, 6 kifejezés α4 , 30 kifejezés α3 β, 15 kifejezés α2 β 2 , satöbbi.: a megfelelő kifejezések termékei a második oszlopban adják a külső oszlopot 6, 120, 90, satöbbi; és ezen számok összege természetesen 64 , = 1296. A tétel egy megfogalmazása a következő: Legyen (α, β, γ, , . ), jelölés mint fent, a fáknak legyenek adottak a csomópontjai λ, α, β, , ; (λ + µ, α, β, γ, ), a fák párjai legyenek a megadott csomópontokkal λ, µ, α, β, γ, , a λ, µ csomópontokhoz tartozó különböző fák: (λ + µ + ν, λ, β, γ . ), a hármas fák a megadott csomópontokkal (λ, µ, ν, α, β, γ, ) , a csomópontok λ, µ, ν . mindig különböző fákhoz tartoznak, és így tovább Azután ha i + 1 lesz a csomók száma, és n a csomók száma, α, β, γ,

. a fák, vagy párok, vagy hármasok száma, satöbbi. A fák = (i + 1)(i + n + 1)n − 1 Pontosan, ha i = 0, akkor létezik n száma a csomóknak α, β, γ, . , és ennek következtében n + 1 a csomópontok egész számossága λ, α, β, γ, . , a fák száma nn−2 , mint korábban (.) 7.11 Megjegyzés A fenti rövid fordításból is jól látszik, hogy az elmúlt 121 év a matematika nyelvezetét is jelentősen átformálta. A cikkben találni lehet olyan kifejezéseket, amelyeket manapság már teljesen másképp használunk, valamint egyegy kifejezést már egyáltalán nem. Ez a megállapítás nem meglepő, hiszen már például egy 1950-es években íródótt magyar nyelvű matematikai szöveg jelentős része is nehezen érthető a mai olvasó számára. 42 http://www.doksihu Köszönetnyilvánítás Hálás köszönettel tartozom Témavezetőmnek, Vesztergombi Katalinnak odaadó segítségéért, ötleteiért. 43 http://www.doksihu Irodalomjegyzék •

Lovász László - Pelikán József - Vesztergombi Katalin: Diszkrét matematika Typotex, 2006 • Rónyai Lajos - Ivanyos Gábor - Szabó Réka: Algoritmusok Typotex, 2005 • Martin Aigner - Günter M. Ziegler: Bizonyítások a Könyvből Typotex, 2004 • Lovász László: Kombinatorikai problémák és feladatok Typotex, 1999 • Quarterly Journal of Pure and applied Mathematics 23. kötet • Lovász László: Algoritmusok bonyolultsága, Egyetemi jegyzet • de.wikipediaorg/wiki/Heinz Prufer • www.ttkptehu/matek/numanal/ttk elemei/msc/grafpdf • http://hu.wikipediaorg/wiki/Cayley-formula • http://home.fazekashu/ lsuranyi/Grafok/ • http://hu.wikipediaorg/wiki/Gráf 44