Stablo (teorija grafova)

stablo
Stablo sa 6 čvorova i 5 grana
Čvorovi	v
Grane	v - 1
Hromatski broj	2

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

Definicije

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, $K_{3}$, 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.

Primer

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.

Činjenice

• Svako stablo je bipartitni graf. Svako stablo sa prebrojivo mnogo čvorova je planaran graf.

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

Prebrojavanje

Ako je dato n označenih čvorova, postoji -{n]-ⁿ⁻² 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 d₁,d₂,...,d_n predstavlja multinomni koeficijent

${n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.$

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 je dokazao da

$t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{kada }}n\to \infty ,$

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

Vidi još

• Stablo (struktura podataka)
• Binarno stablo