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

стабло
Стабло са 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 чворова степена d₁,d₂,...,d_n представља мултиномни коефицијент

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

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

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

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

Види још

• Стабло (структура података)
• Бинарно стабло