Strom (teorie grafů)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. června 2020; kontroly vyžadují 6 úprav .

Strom je souvislý acyklický graf . [1] Konektivita znamená přítomnost trasy mezi libovolným párem vrcholů, acykličnost znamená absenci cyklů. Z toho zejména vyplývá, že počet hran ve stromu je o jednu menší než počet vrcholů a mezi libovolným párem vrcholů je jedna a pouze jedna cesta.

V lese je spousta stromů.

Orientovaný (orientovaný) strom je acyklický digraf ( orientovaný graf , který neobsahuje cykly), ve kterém pouze jeden vrchol má nulový stupeň vstupu (nejsou v něm žádné oblouky) a všechny ostatní vrcholy mají vstupní stupeň 1 (vede k nim přesně jeden oblouk). Vrchol s nulovým stupněm vstupu se nazývá kořen stromu, vrcholy s nulovým stupněm výsledku (ze kterých nevychází žádný oblouk) se nazývají terminální vrcholy nebo listy . [2]

Související definice

Stupeň vrcholu je počet hran, které k němu přiléhají.

Koncový uzel ( list , terminální vrchol ) je uzel se stupněm 1 (tedy uzel, ke kterému vede pouze jedna hrana; v případě orientovaného stromu uzel, ke kterému vede pouze jeden oblouk a žádné oblouky nevycházejí) .

Uzel větvení je nekoncový uzel.

Strom s vyznačeným vrcholem se nazývá kořenový strom .
- $m$ Třetí vrstva stromu je množina uzlů stromu na úrovni od kořene stromu. $T$ $m$
- částečné pořadí na vrcholech: pokud jsou vrcholy a různé a vrchol leží na (jedinečném!) elementárním řetězci spojujícím kořen s vrcholem . $u\prec v$ $u$ $proti$ $u$ $proti$
- kořenový podstrom zakořeněný jako podgraf . $proti$ $\{v\}\pohár \{w\mid v<w\}$
- V kontextu, kde se předpokládá, že strom má kořen, se strom bez rozlišujícího kořene nazývá volný .

Úroveň uzlu - délka cesty od kořene k uzlu. Lze definovat rekurzivně:

úroveň kořene stromu je 0; $T$
úroveň jakéhokoli jiného uzlu je o jednu větší než úroveň kořene nejbližšího podstromu stromu obsahujícího tento uzel. $T$

Spanning tree ( kostra ) je podgraf daného grafu, který obsahuje všechny jeho vrcholy a je stromem. Hrany grafu, které nejsou součástí kostry, se nazývají tětivy grafu vzhledem ke kostře.

Strom se nazývá neredukovatelný, pokud nemá žádné vrcholy stupně 2.

Les je množina (obvykle uspořádaná), která neobsahuje jeden neprotínající se strom nebo obsahuje několik neprotínajících se stromů.
Centroid - vrchol, při jehož odstranění rozměry výsledných připojených komponent nepřesahují (polovinu velikosti původního stromu) ${\dfrac {n}{2))$

Binární strom

Termín binární strom (také se používá termín binární strom) má několik významů:

Neorientovaný strom s vrcholovými stupni nejvýše 3.
Orientovaný strom, ve kterém výstupní stupně vrcholů (počet odchozích hran) nepřesahují 2.
Abstraktní datová struktura používaná v programování . Datové struktury jako binární vyhledávací strom , binární halda , červeno-černý strom , AVL strom , Fibonacciho halda atd. jsou založeny na binárním stromu.

N-ární stromy

N-ární stromy jsou definovány analogicky s binárním stromem. Mají také řízené a neřízené případy, stejně jako odpovídající abstraktní datové struktury.

N-ární strom (neorientovaný) je strom (obyčejný, neorientovaný), ve kterém stupně vrcholů nepřesahují N + 1.
N-ární strom (orientovaný) je řízený strom, ve kterém odchozí stupně vrcholů (počet odchozích hran) nepřesahují N.

Vlastnosti

Strom nemá více hran nebo smyček .
Každý strom s vrcholy obsahuje hranu. Navíc, konečně souvislý graf je strom právě tehdy, když , kde je počet vrcholů a počet hran grafu. $n$ $n-1$ $BP = 1$ $B$ $P$
Graf je strom tehdy a jen tehdy, když kterékoli dva z jeho odlišných vrcholů mohou být spojeny jediným jednoduchým řetězcem .
Každý strom je jednoznačně určen vzdálenostmi (délkou nejmenšího řetězce) mezi jeho koncovými (1. stupeň) vrcholy.
Každý strom je bipartitní graf .
Každý strom, jehož množina vrcholů je nanejvýš spočetná, je rovinný graf .
Pro libovolné tři vrcholy stromu mají cesty mezi dvojicemi těchto vrcholů právě jeden společný vrchol.

Počítání stromů

Počet zřetelných stromů, které lze postavit na očíslovaných vrcholech, je ( Cayleyho věta [3] ). $n$ $n^{{n-2}}$
Generující funkce

T(z)=\sum _{n=1}^{\infty }T_{n}z^{n}

pro počet neizomorfních kořenových stromů s vrcholy splňuje funkční rovnici

T_{n}

n

T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})

Generující funkce

t(z)=\součet _{n=1}^{\infty }t_{n}z^{n}

pro počet neizomorfních stromů s vrcholy lze reprezentovat pomocí výpisové řady pro kořenové stromy:

t_{n}

n

t(z)=T(z)-{\frac {1}{2}}\left(T^{2}(z)-T(z^{2})\vpravo).

Následující asymptotika je pravdivá $n\to\infty$

t_{n}\sim C\alpha ^{n}/n^{5/2}

kde a jsou určité konstanty, , .

C

\alpha

C=0,534948...

\alpha =2,95576...

Kódování stromu

Strom lze zakódovat jako sady nul a jedniček. Vezměme si například položení stromu na rovinu. Začneme-li od nějakého vrcholu, budeme se pohybovat podél okrajů stromu, přičemž se v každém vrcholu otočíme k okraji nejblíže vpravo a v koncových vrcholech stromu se budeme otáčet zpět. Přejetí podél nějaké hrany píšeme při prvním pohybu po hraně a při druhém pohybu po hraně (v opačném směru). Je-li počet hran stromu, pak se po krocích vrátíme do původního vrcholu a každou hranu projdeme dvakrát. Výsledná sekvence délek a (kódu stromu) umožňuje jednoznačně obnovit nejen samotný strom , ale i jeho položení v rovině. Libovolnému stromu odpovídá několik takových kódů. Z této kódovací metody vyplývá zejména následující hrubý odhad počtu stromů s vrcholy: $0$ $jeden$ $m$ $2m$ $0$ $jeden$ $2m$ $D$ $n$ $t_{n}\leq T_{n}<2^{2n}$

Pruferův kód mapuje do libovolného konečného stromu s vrcholy posloupnost čísel od do s možným opakováním. Například strom na obrázku má Pruferův kód (4,4,4,5). Mezi označenými vertexovými stromy a jejich Pruferovými kódy existuje vzájemná shoda. Cayleyův vzorec je odvozen z Prüferova kódu . $n$ $n-2$ $jeden$ $n$

Strom lze zadat jako řetězec obsahující znaky, které označují uzly stromu, a také otevírací a uzavírací závorky. Mezi stromy a jejich lineárními závorkami existuje vzájemná korespondence.

Viz také

Glosář teorie grafů
Les disjunktních množin
Seznam datových struktur (stromů)

Poznámky

↑ § 13. Definice stromu // Přednášky o teorii grafů / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - S. 53. - 384 s. — 22 000 výtisků. — ISBN 5-02-013992-0 .
↑ Alfs Berztiss. Kapitola 3. Teorie grafů. 3.6. Stromy // Datové struktury = AT Berztiss. datové struktury. teorie a praxe. - M. : Statistika, 1974. - S. 131. - 10 500 výtisků.
↑ Diskrétní matematika: Algoritmy. Cayleyho vzorec (nepřístupný odkaz) . Získáno 29. října 2009. Archivováno z originálu 14. června 2009. (neurčitý)

Literatura

Donald Knuth . The Art of Computer Programming, sv. 1. Základní algoritmy. - 3. vyd. - M .: Williams , 2006. - T. 1. Základní algoritmy. — 720 s. - ISBN 0-201-89683-4 .
Ruda O. Teorie grafů. - 2. vyd. — M .: Nauka , 1980. — 336 s.
Harari F. Teorie grafů. — M .: Mir , 1973. — 302 s.

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree