Drevo (teorija grafov): Razlika med redakcijama

Iz Wikipedije, proste enciklopedije
Izbrisana vsebina Dodana vsebina
JAnDbot (pogovor | prispevki)
Rubinbot (pogovor | prispevki)
Vrstica 48: Vrstica 48:
[[pt:Árvore (grafo)]]
[[pt:Árvore (grafo)]]
[[ro:Arbore (teoria grafurilor)]]
[[ro:Arbore (teoria grafurilor)]]
[[ru:Дерево (теория графов)]]
[[sk:Strom (graf)]]
[[sk:Strom (graf)]]
[[sr:Стабло (теорија графова)]]
[[sr:Стабло (теорија графова)]]

Redakcija: 06:57, 6. julij 2010

Bethejeva rešetka je vrsta drevesa

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č)