Wikipedija

Drevo (teorija grafov): Razlika med redakcijama

Stran Pogovor

Drevo (teorija grafov) (uredi)

Redakcija: 02:02, 25. avgust 2010

dodanih 71 zlogov ,  pred 11 leti
m
dp+/+p
m (dp+/+p)
[[Slika:Bethe lattice.PNG|thumb|right|200px|[[Bethejeva rešetka]] je vrsta drevesa]]
 
'''Drevo''' je v [[matematika|matematiki]] ([[teorija grafov|teoriji grafov]]) [[graf (matematika)|graf]] v katerem sta poljubni dve [[točka (teorija grafov)|točki]] povezani zs natankotočno eno enostavno [[pot (teorija grafov)|pot]]jo. Po enakovredni opredelitvi je drevo vsak [[povezan graf]] brez [[cikel (teorija grafov)|ciklov]]. '''Gozd''' je nepovezana [[unija množic|unija]] dreves.
 
Različne vrste dreves, ki se uporabljajo kot [[podatkovna struktura|podatkovne strukture]] v [[računalništvo|računalništvu]], v tem smislu niso drevesa, ampak bolj vrsta urejenih usmerjenih dreves.
 
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]].
* ''T'' nima ciklov in, če dodamo katerokoli povezavo, nastane natankotočno en enostavni cikel.
* ''T'' je povezan in, če odstranimo katerokoli povezavo ([[most (teorija grafov)|most]]), postane [[nepovezani graf|nepovezan]].
* ''T'' je povezan in [[polni graf]] na treh točkah ''K''<sub>3</sub> ni njegov [[minor (teorija grafov)|minor]].
* Dve poljubni točki v ''T'' sta povezani zs natankotočno eno enostavno [[pot (teorija grafov)|pot]]jo.
 
Če ima ''T'' končno mnogo točk, recimo ''n'', veljata še naslednji dve enakovredni definiciji:
Vzpostavljeno iz »https://sl.wikipedia.org/wiki/Posebno:MobileDiff/2454486«