Drevo (teorija grafov): Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
dp+/definicije,viri |
m robot Odstranjevanje: lv:Aciklisks grafs, ru:Дерево (теория графов) Spreminjanje: ko:트리 |
||
| Vrstica 29: | Vrstica 29: | ||
[[Kategorija:Teorija grafov]] |
[[Kategorija:Teorija grafov]] |
||
[[Kategorija:Drevesa (teorija grafov)| ]] |
[[Kategorija:Drevesa (teorija grafov)| ]] |
||
[[cs:Strom (graf)]] |
[[cs:Strom (graf)]] |
||
| Vrstica 37: | Vrstica 36: | ||
[[es:Árbol (teoría de grafos)]] |
[[es:Árbol (teoría de grafos)]] |
||
[[fa:درخت (نظریه گراف)]] |
[[fa:درخت (نظریه گراف)]] |
||
| ⚫ | |||
[[fr:Arbre (graphe)]] |
[[fr:Arbre (graphe)]] |
||
[[he:עץ (תורת הגרפים)]] |
[[he:עץ (תורת הגרפים)]] |
||
| Vrstica 42: | Vrstica 42: | ||
[[it:Albero (grafo)]] |
[[it:Albero (grafo)]] |
||
[[ja:木 (数学)]] |
[[ja:木 (数学)]] |
||
[[ko:트리 |
[[ko:트리]] |
||
[[lv:Aciklisks grafs]] |
|||
[[lt:Medis (grafų teorija)]] |
[[lt:Medis (grafų teorija)]] |
||
[[nl:Boomstructuur]] |
[[nl:Boomstructuur]] |
||
| Vrstica 49: | 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:Стабло (теорија графова)]] |
||
| ⚫ | |||
[[sv:Träd (graf)]] |
[[sv:Träd (graf)]] |
||
[[th:ต้นไม้ (ทฤษฎีกราฟ)]] |
[[th:ต้นไม้ (ทฤษฎีกราฟ)]] |
||
| ⚫ | |||
[[uk:Дерево (теорія графів)]] |
[[uk:Дерево (теорія графів)]] |
||
| ⚫ | |||
[[zh:树 (图论)]] |
[[zh:树 (图论)]] |
||
Redakcija: 14:52, 30. junij 2010
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č)
