Стабло (теорија графова)

Из Википедије, слободне енциклопедије
стабло
Tree graph.svg
Стабло са 6 чворова и 5 грана
Чворови v
Гране v - 1
Хроматски број 2

У теорији графова, стабло је граф у коме су свака два чвора повезана тачно једном стазом. Другачије речено, сваки повезан граф без циклова је стабло. Шума је дисјунктна унија стабала. Стабла се изузетно пуно користе у као структуре података у рачунарству (као бинарна стабла претраге, хипови, и слично).

Дефиниције[уреди]

Стабло је неповезан прост граф G који задовољава било који од следећих (еквивалентних) услова:

  • G је повезан и нема простих циклова.
  • G нема простих циклова, а прост цикл се добија ако се било било која нова грана дода у G.
  • G је повезан, али ако се било која грана уклони из G, више неће бити повезан.
  • G је повезан и комплетан граф од три чвора, K_3, није минор од G.
  • Било која два чвора у G су повезана јединственом простом стазом.

Ако G има коначно много чворова, нека тај број буде n, онда су горњи искази еквивалентни следећим условима:

  • G је повезан и има n − 1 грана.
  • G нема простих циклова и има n − 1 грна.

Усмерено стабло је усмерен граф који би био стабло ако би се смерови грана игнорисали. Неки аутори ограничавају овај израз на случајеве када су све гране усмерене према одређеном чвору или од одређеног чвора.

Стабло се назива коренским стаблом ако се један чвор означи као корен, у ком случају гране имају природну оријентацију, према или од корена.

Пример[уреди]

Пример стабла са десне стране има 6 чворова и 6 − 1 = 5 грана. Јединствена проста стаза која повезује чворове 2 и 6 је 2-4-5-6.

Чињенице[уреди]

  • Свако непразно стабло има најмање један лист, или чвор степена 1 (Ако има чвор, има и лист).

Пребројавање[уреди]

Ако је дато n означених чворова, постоји -{n]-n−2 различитих начина да се они повежу у стабло. Ово је резултат Кејлијеве формуле. Може се доказати тако што се прво покаже да број стабала са n чворова степена d1,d2,...,dn представља мултиномни коефицијент

 {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1}.

Пребројавање неозначених стабала је тежи проблем. Не постоји затворена формула за број t(n) стабала са n чворова до на изоморфизам графова. Ричард Отер[1] је доказао да

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

где је C = 0,53495… а α = 2,95576… (овде, fg значи да lim f/g = 1).

Види још[уреди]

Референце[уреди]

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

Спољашње везе[уреди]