Puu (graafiteooria)
Puu on graafiteoorias sidus ja tsükliteta graaf. Olenevalt käsitlusest võidakse puuks lugeda ainult suunamata graafe, mis vastavad puu tingimusele. Paljud andmestruktuurid informaatikas põhinevad puul, aga üldiselt on nende puhul üks tipp valitud juureks, mille tulemusena saadakse juurega puu.
Definitsioonid[muuda | muuda lähteteksti]
Puu[muuda | muuda lähteteksti]
Iga suunatud graaf on puu, kui ta rahuldab järgmisi võrdväärseid tingimusi:
- ta on sidus ja tsükliteta;[1]
- ükskõik millise serva lisamisel tekib tsükkel;[2]
- ta muutub ükskõik millise serva eemaldamisel mittesidusaks;[1]
- iga tema kahte tippu ühendab täpselt üks tee.[1]
Kui graafil on ka lõplik arv n tippu, siis järgmised väited on samuti võrdväärsed ülaltoodutega:
Kui käsitlusest olenevalt võivad suunatud graafid ka puud olla, siis on nad seda juhul, kui nende alusgraaf on puu. Samuti võidakse sõltuvalt käsitlusest puuks lugeda ainult juurega puid. Graafi, millel pole ühtegi tippu, ei loeta üldjuhul puuks, nagu ei loetaga teda ka graafiks.
Mets[muuda | muuda lähteteksti]
Metsaks nimetatakse graafi, mille kõik sidusad komponendid on puud [2]. Võrdväärselt saab öelda, et mets on tsükliteta graaf [1]. Ka üksik puu ja tühigraaf (ilma servadeta graaf) on metsad. Kuna puude puhul kehtib tingimus V – E = 1, kus V on graafi tippude arv ja E graafi servade arv, siis saame metsas olevate puude arvu, kui lahutame metsa kõigi tippude arvust TV, metsa kõigi servade arvu TE, seega saame TV – TE = puude arv metsas.
Juurega puu[muuda | muuda lähteteksti]
Juurega puu on puu, milles ühte tippu nimetatakse juureks või juurtipuks. Kui juurega puu on suunatud, suunavad üldjuhul kõik kaared (suunatud servad) kas juurest eemale või juure poole. Tipu ülemtipuks nimetatakse naabertippu, mis jääb teele tipust juureni. Igal tipul peale juure on üks ülemtipp. Tipu alamtipuks nimetatakse tippu, mille jaoks on antud tipp ülemtipp. Leht on tipp, millel pole alamtippe. Iga tipp, mis ei ole ei juur ega leht, on vahetipp.[4]
Juurega puu tipu kõrgus on kõige pikema lehtedesuunalise tee pikkus. Puu kõrgus on puu juure kõrgus. Tipu sügavus on tee pikkus sellest tipust juureni. Juure sügavus on null, lehtede kõrgus on null ja nii ühest tipust koosneva puu kõrgus kui ka sügavus on null. Kui graafi ilma ühegi tiputa loetakse korrektseks puuks, siis tavaliselt arvestatakse selle kõrguseks ja sügavuseks miinus üks. Tippude sügavus on oluline puude tasakaalustamisel, mida on tihti tarvis otsimispuude, näiteks AVL-puu puhul.[4]
Juurega puud on üks olulisim andmestruktuur informaatikas. Praktikas on kasutuses tihti järjestatud puud. Järjestatud puu on juurega puu, milles iga tipu alamtippudele on määratud kindel järjestus.[5]
Kahendpuu[muuda | muuda lähteteksti]
Kahendpuu on juurega puu, mille igal tipul on maksimaalselt kaks alamtippu, mida nimetatakse vasakuks ja paremaks alamtipuks või alluvaks. Rekursiivse definitsiooni kohaselt on kahendpuu puu, mis on kas tühi või millel on täpselt kaks haru, mis on mõlemad samuti kahendpuud. Informaatikas on kahendpuud olulised andmestruktuurid, mida kasutatakse tihti otsimisalgoritmide puhul [6].
Omadused[muuda | muuda lähteteksti]
- Igal n-tipulisel puul on n – 1 serva.[7]
- Iga puu on tasandiline graaf.
- Iga puu on kahealuseline graaf.[8]
- Iga kolme puu tipu puhul on nendevahelistel teedel täpselt üks ühine tipp.
Viited[muuda | muuda lähteteksti]
- ↑ 1,0 1,1 1,2 1,3 J. A. Bondy, U. S. R. Murty (1976). Graph theory with applications. Suurbritannia: The Macmillan Press Ltd.
- ↑ 2,0 2,1 2,2 Reinhard Diestel (1997). Graph Theory. Heidelberg: Springer-Verlag.
- ↑ Keijo Ruohonen (2013). Graph Theory.
- ↑ 4,0 4,1 "Graph Theory - Lecture 4: Trees" (PDF). Vaadatud 30.11.2018.
- ↑ Richard P. Stanley (2012). Enumerative Combinatorics, Vol. I. Cambridge University Press.
- ↑ Granville Barnett, Luca Del Tongo (2008). Data Structures and Algorithms: Annotated Reference with Examples.
- ↑ Reimo Palm (2003). Diskreetse matemaatika elemendid. Tartu: Tartu Ülikooli Kirjastus. Lk 64.
- ↑ David Guichard (2018). An Introduction to Combinatorics and Graph Theory.