Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m dp |
dp+/definicije,viri |
||
| Vrstica 4: | 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. |
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}} |
{{math-stub}} |
||
Redakcija: 20:03, 26. november 2009
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.
- Robin J., Wilson (1997). Uvod v teorijo grafov. Ljubljana: DMFA. COBISS 72250368.
{{navedi knjigo}}: Prezrt neznani parameter|coauthors=(predlagano je|author=) (pomoč)
