Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m dp |
dp+/definicije,viri |
||
Vrstica 4:
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.
== Definicije ==
Za drevo ''T'', ki je neusmerjeni [[enostavni graf]], veljajo naslednje enakovredne definicije:
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]].
* ''T'' nima ciklov in, če dodamo katerokoli povezavo, nastane natanko en enostavni cikel.
* ''T'' je povezan in, če odstranimo katerokoli povezavo, postane 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 z natanko eno enostavno [[pot (teorija grafov)|pot]]jo.
Če ima ''T'' končno mnogo točk, recimo ''n'', veljata še naslednji dve enakovredni definiciji:
* ''T'' je povezan in ima ''n'' - 1 povezav.
* ''T'' nima ciklov in ima ''n'' - 1 povezav.
== Viri ==
* {{navedi knjigo|first=Cvetković|last=Dragoš|title=Teorija grafova|year=1990|edition=3. dop. izd.|publisher=[[Naučna knjiga]]|location=Beograd|cobiss=3149573}}
* {{navedi knjigo|first=Wilson|last=Robin J.|coauthors=Watkins, John J.|title=Uvod v teorijo grafov|year=1997|publisher=[[Društvo matematikov, fizikov in astronomov Slovenije|DMFA]]|location=Ljubljana|cobiss=72250368}}
{{math-stub}}
| |||