Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m →Viri |
m →Viri |
||
| Vrstica 35: | Vrstica 35: | ||
== Viri == |
== Viri == |
||
* {{ |
* {{citat|last1= Cvetković|first1= Dragoš|authorlink1= Dragoš Cvetković|title= Teorija grafova|date= 1990|edition= 3. dop.|publisher= [[Naučna knjiga]]|location= Beograd|isbn= |cobiss= 3149573|ref= harv}} |
||
* {{ |
* {{citat|last1= Wilson|first1= Robin James|authorlink1= Robin James Wilson|last2= Watkins|first2= John Jaeger|authorlink2= John Jaeger Watkins|title= Uvod v teorijo grafov|trans-title= Graphs : an introductory approach|publisher= [[Društvo matematikov, fizikov in astronomov Slovenije|DFMA Slovenije]]|edition= Knjižnica Sigma - 63|location= Ljubljana|date= 1997|isbn= 961-212-081-1|cobiss= 72250368|ref= harv}} |
||
{{math-stub}} |
{{math-stub}} |
||
Redakcija: 00:24, 8. julij 2016
| Drevesa | |
|---|---|
 Označeno neusmerjeno drevo s 6 točkami in 5 povezavami | |
| Točke | v |
| Povezave | v - 1 |
| Kromatično število | 2 |
Drevo je v matematiki (teoriji grafov) graf v katerem sta poljubni dve točki povezani s točno eno enostavno potjo. Po enakovredni opredelitvi je drevo vsak povezan graf brez ciklov. Gozd je nepovezana unija dreves.
Različne vrste dreves, ki se uporabljajo kot podatkovne strukture v 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 povezan in brez ciklov.
- T nima ciklov in, če dodamo katerokoli povezavo, nastane točno en enostavni cikel.
- T je povezan in, če odstranimo katerokoli povezavo (most), postane nepovezan.
- T je povezan in polni graf na treh točkah K3 ni njegov minor.
- Dve poljubni točki v T sta povezani s točno eno enostavno potjo.
Č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
- Cvetković, Dragoš (1990), Teorija grafova (3. dop. izd.), Beograd: Naučna knjiga, COBISS 3149573
{{citation}}: Neveljaven|ref=harv(pomoč) - Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1
{{citation}}: Neveljaven|ref=harv(pomoč)
