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 .
- Třetí vrstva stromu je množina uzlů stromu na úrovni od kořene stromu.
- čá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 .
- kořenový podstrom zakořeněný jako podgraf .
- 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;
- úroveň jakéhokoli jiného uzlu je o jednu větší než úroveň kořene nejbližšího podstromu stromu obsahujícího tento uzel.
- 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)
Binární strom
Termín binární strom (také se používá termín binární strom) má několik významů:
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.
- 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] ).
- Generující funkce
pro počet neizomorfních kořenových stromů s vrcholy splňuje funkční rovnici
.
pro počet neizomorfních stromů s vrcholy lze reprezentovat pomocí výpisové řady pro kořenové stromy:
- Následující asymptotika je pravdivá
kde a jsou určité konstanty, , .
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:
- 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 .
- 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é
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.