Стабло (теорија графова) — разлика између измена
Садржај обрисан Садржај додат
м Bot: Migrating 29 interwiki links, now provided by Wikidata on d:q272735 (translate me) |
м разне исправке; козметичке измене |
||
Ред 1:
{{infobox graph
| име = стабло
| слика = [[
| наслов слике = Стабло са 6 чворова и 5 грана
| чворови = ''-{v}-''
Ред 15:
== Дефиниције ==
'''Стабло''' је неповезан прост граф ''-{G}-'' који задовољава било који од следећих (еквивалентних)
* ''-{G}-'' је [[повезан граф|повезан]] и нема [[прост цикл|простих циклова]].
* ''-{G}-'' нема простих циклова, а прост цикл се добија ако се било било која нова грана дода у ''-{G}-''.
* ''-{G}-'' је повезан, али ако се било која грана уклони из ''-{G}-'', више неће бити повезан.
* ''-{G}-'' је повезан и [[комплетан граф]] од три чвора, <math>K_3</math>, није [[минор (теорија графова)|минор]] од ''-{G}-''.
* Било која два чвора у ''-{G}-'' су повезана јединственом простом стазом.
Ако ''-{G}-'' има коначно много чворова, нека тај број буде ''-{n}-'', онда су горњи искази еквивалентни следећим условима:
* ''-{G}-'' је повезан и има ''-{n}-'' − 1 грана.
* ''-{G}-'' нема простих циклова и има ''-{n}-'' − 1 грна.
'''Усмерено стабло''' је [[усмерен граф]] који би био стабло ако би се смерови грана игнорисали. Неки аутори ограничавају овај израз на случајеве када су све гране усмерене према одређеном чвору или од одређеног чвора.
Ред 46:
где је ''-{C}-'' = 0,53495… а α = 2,95576… (овде, ''-{f}-'' ∼ ''-{g}-'' значи да -{lim ''f''/''g'' = 1}-).
==
*[[Стабло (структура података)]]▼
*[[Бинарно стабло]]▼
{{reflist}}
== Види још ==
== Спољашње везе==▼
▲* [[Стабло (структура података)]]
▲* [[Бинарно стабло]]
▲== Спољашње везе ==
{{Commonscat|Decision diagrams}}
| |||