Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m →Viri |
m dp+/+p |
||
| Vrstica 14: | Vrstica 14: | ||
[[Slika:Bethe lattice.PNG|thumb|right|200px|[[Bethejeva rešetka]] je vrsta drevesa]] |
[[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|točki]] povezani |
'''Drevo''' je v [[matematika|matematiki]] ([[teorija grafov|teoriji grafov]]) [[graf (matematika)|graf]] v katerem sta poljubni dve [[točka (teorija grafov)|točki]] povezani s toč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. |
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. |
||
| Vrstica 23: | Vrstica 23: | ||
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]]. |
* ''T'' je [[povezani graf|povezan]] in brez [[cikel (teorija grafov)|ciklov]]. |
||
* ''T'' nima ciklov in, če dodamo katerokoli povezavo, nastane |
* ''T'' nima ciklov in, če dodamo katerokoli povezavo, nastane točno en enostavni cikel. |
||
* ''T'' je povezan in, če odstranimo katerokoli povezavo, postane nepovezan. |
* ''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]]. |
* ''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 |
* Dve poljubni točki v ''T'' sta povezani s točno eno enostavno [[pot (teorija grafov)|pot]]jo. |
||
Če ima ''T'' končno mnogo točk, recimo ''n'', veljata še naslednji dve enakovredni definiciji: |
Če ima ''T'' končno mnogo točk, recimo ''n'', veljata še naslednji dve enakovredni definiciji: |
||
Redakcija: 02:02, 25. avgust 2010
| 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
- Dragoš, Cvetković (1990). Teorija grafova (3. dop. izd. izd.). Beograd: Naučna knjiga. COBISS 3149573.
- Wilson, Robin James (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č)
