neusmerjen, povezan in acikličen graf From Wikipedia, the free encyclopedia
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.
Drevesa | |
---|---|
![]() Označeno neusmerjeno drevo s 6 točkami in 5 povezavami | |
Točke | v |
Povezave | v - 1 |
Kromatično število | 2 |
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.
Za drevo T, ki je neusmerjeni enostavni graf, veljajo naslednje enakovredne definicije:
Če ima T končno mnogo točk, recimo n, veljata še naslednji dve enakovredni definiciji: