Drevo (teorija grafov)

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Drevesa
Tree graph.svg
Označeno neusmerjeno drevo s 6 točkami in 5 povezavami
Točkev
Povezavev - 1
Kromatično število2
Bethejeva rešetka je vrsta drevesa

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[uredi | uredi kodo]

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[uredi | uredi kodo]

  • Cvetković, Dragoš (1990), Teorija grafova (3. dop. izd.), Beograd: Naučna knjiga, COBISS 3149573
  • Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1