Stablo (teorija grafova)

U teoriji grafova, stablo je graf u kome su svaka dva čvora povezana tačno jednom stazom. Drugačije rečeno, svaki povezan graf bez ciklusa je stablo. Šuma je disjunktna unija stabala. Stabla se izuzetno puno koriste u kao strukture podataka u računarstvu (kao binarna stabla pretrage, hipovi, i slično).

stablo
Tree graph.svg
Stablo sa 6 čvorova i 5 grana
Čvoroviv
Granev - 1
Hromatski broj2

DefinicijeUredi

Stablo je neorjentisan prost graf G koji zadovoljava bilo koji od sledećih (ekvivalentnih) uslova:

  • G je povezan i nema prostih ciklusa.
  • G nema prostih ciklusa, a prost ciklus se dobija ako se bilo bilo koja nova grana doda u G.
  • G je povezan, ali ako se bilo koja grana ukloni iz G, više neće biti povezan.
  • G je povezan i kompletan graf od tri čvora,  , nije minor od G.
  • Bilo koja dva čvora u G su povezana jedinstvenom prostom stazom.

Ako G ima konačno mnogo čvorova, neka taj broj bude n, onda su gornji iskazi ekvivalentni sledećim uslovima:

  • G je povezan i ima n − 1 grana.
  • G nema prostih ciklusa i ima n − 1 grna.

Usmereno stablo je usmeren graf koji bi bio stablo ako bi se smerovi grana ignorisali. Neki autori ograničavaju ovaj izraz na slučajeve kada su sve grane usmerene prema određenom čvoru ili od određenog čvora.

Stablo se naziva korenskim stablom ako se jedan čvor označi kao koren, u kom slučaju grane imaju prirodnu orijentaciju, prema ili od korena.

PrimerUredi

Primer stabla sa desne strane ima 6 čvorova i 6 − 1 = 5 grana. Jedinstvena prosta staza koja povezuje čvorove 2 i 6 je 2-4-5-6.

ČinjeniceUredi

  • Svako neprazno stablo ima najmanje jedan list, ili čvor stepena 1 (Ako ima čvor, ima i list).

PrebrojavanjeUredi

Ako je dato n označenih čvorova, postoji -{n]-n−2 različitih načina da se oni povežu u stablo. Ovo je rezultat Kejlijeve formule. Može se dokazati tako što se prvo pokaže da broj stabala sa n čvorova stepena d1,d2,...,dn predstavlja multinomni koeficijent

 

Prebrojavanje neoznačenih stabala je teži problem. Ne postoji zatvorena formula za broj t(n) stabala sa n čvorova do na izomorfizam grafova. Ričard Oter[1] je dokazao da

 

gde je C = 0,53495… a α = 2,95576… (ovde, fg znači da lim f/g = 1).

Vidi jošUredi

ReferenceUredi

  1. ^ Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series 49 (3): 583–599, DOI 10.2307/1969046.

Spoljašnje vezeUredi