Puu (graafiteooria): erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
P pisitoimetamine |
PResümee puudub |
||
1. rida:
[[Fail:Tree graph.svg|alt=Nummerdatud tippudega puu, millel on 6 tippu ja 5 serva.|pisi|Kuue
'''Puu''' on [[graafiteooria]]s [[Sidus graaf|sidus]] ja tsükliteta [[graaf]]. Olenevalt käsitlusest võidakse puuks lugeda ainult suunamata graafe, mis vastavad puu tingimusele. Paljud [[andmestruktuur]]id [[informaatika]]s põhinevad puul, aga üldiselt on nende puhul üks tipp valitud juureks, mille tulemusena saadakse juurega puu.
14. rida:
Kui graafil on ka lõplik arv ''n'' tippu, siis järgmised väited on samuti võrdväärsed ülaltoodutega:
* ta on sidus ja tal on ''n
* ta on tsükliteta ja tal on ''n
Kui käsitlusest olenevalt võivad [[suunatud graaf]]id 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 ===
Metsaks nimetatakse graafi, mille kõik sidusad komponendid on puud <ref name=":1" />. Võrdväärselt saab öelda, et mets on tsükliteta graaf <ref name=":0" />. Ka üksik puu ja tühigraaf (ilma servadeta graaf) on metsad. Kuna puude puhul kehtib tingimus ''V
=== Juurega puu ===
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.<ref name=":2">{{Netiviide|Autor=|URL=http://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf|Pealkiri=Graph Theory - Lecture 4: Trees|Väljaanne=|Aeg=|Kasutatud=30.11.2018}}</ref>
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
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.<ref>{{Raamatuviide|autor=Richard P. Stanley|pealkiri=Enumerative Combinatorics, Vol. I|aasta=2012|koht=|kirjastus=Cambridge University Press|lehekülg=}}</ref>
34. rida:
== Omadused ==
*Igal ''n-''tipulisel puul on ''n
*Iga puu on [[tasandiline graaf]].
* Iga puu on [[kahealuseline graaf]].<ref>{{Raamatuviide|autor=David Guichard|pealkiri=An Introduction to Combinatorics and Graph Theory|aasta=2018|koht=|kirjastus=|lehekülg=}}</ref>
| |||