Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m dp |
m dp |
||
Vrstica 2: | Vrstica 2: | ||
| name = Drevesa |
| name = Drevesa |
||
| image = [[Slika:Tree graph.svg|180px]] |
| image = [[Slika:Tree graph.svg|180px]] |
||
| image_caption = Označeno drevo s 6 točkami in 5 povezavami |
| image_caption = Označeno neusmerjeno drevo s 6 točkami in 5 povezavami |
||
| vertices = ''v'' |
| vertices = ''v'' |
||
| edges = ''v'' - 1 |
| edges = ''v'' - 1 |
||
Vrstica 20: | Vrstica 20: | ||
== Definicije == |
== Definicije == |
||
Za drevo |
Za drevo ''T'', ki je neusmerjeni [[enostavni graf]], veljajo naslednje enakovredne definicije: |
||
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]]. |
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]]. |
Redakcija: 07:29, 20. avgust 2010
Drevesa | |
---|---|
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 z natanko 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 natanko en enostavni cikel.
- T je povezan in, če odstranimo katerokoli povezavo, postane nepovezan.
- T je povezan in polni graf na treh točkah K3 ni njegov minor.
- Dve poljubni točki v T sta povezani z natanko 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
- Dragoš, Cvetković (1990). Teorija grafova (3. dop. izd. izd.). Beograd: Naučna knjiga. COBISS 3149573.
- Wilson, Robin J. (1997). Uvod v teorijo grafov (Knjižnica Sigma - 63 izd.). Ljubljana: DFMA Slovenije. COBISS 72250368. ISBN 961-212-081-1.
{{navedi knjigo}}
: Prezrt neznani parameter|coauthors=
(predlagano je|author=
) (pomoč)