TreeEdit

strom je neorientovaný graf G, který splňuje některou z následujících ekvivalentních podmínek:

• G je připojen a acyklický (neobsahuje cykly).
• G je acyklický, a jednoduchý cyklus je vytvořen, pokud některý okraj je přidána na G.
• G je připojen, ale by být odpojen, pokud žádné jeden okraj je odstraněn z G.
• G je připojen a 3-vrchol úplný graf K3 není malým G.
• Žádné dva vrcholy v G mohou být spojeny unikátní jednoduchou cestu.

Pokud G má konečně mnoho vrcholů, řekněme n, pak výše uvedená prohlášení jsou také ekvivalentní k jakékoliv z následujících podmínek:

• G je připojen a má n − 1 hran.
• G je připojen, a každý podgraf G obsahuje alespoň jeden vrchol s nulovým nebo jeden incident hrany. (To znamená, že G je připojeno a 1-degenerováno.)
• G nemá jednoduché cykly a má hrany n − 1.

stejně jako jinde v teorii grafů se graf order-zero (graf bez vrcholů) obecně nepovažuje za strom: i když je vacuously připojen jako graf (žádné dva vrcholy mohou být spojeny cestu), to není 0-připojen (nebo i (-1)-připojen) v algebraické topologii, na rozdíl od non-prázdné stromy, a porušuje „jeden více vrcholů než hran“ vztahu. Může však být považován za Les sestávající z nulových stromů.

vnitřní vrchol (nebo vnitřní vrchol nebo větev vrchol) je vrchol stupně nejméně 2. Podobně vnější vrchol (nebo vnější vrchol, koncový vrchol nebo list) je vrchol stupně 1.

irreducible strom (nebo série-snížená strom) je strom, ve kterém není žádný vrchol stupně 2 (vyjmenovány v pořadí A000014 v OEIS).

ForestEdit

les je neorientovaný graf, ve kterém jsou všechny dva vrcholy spojeny nanejvýš jednou cestou. Ekvivalentně, les je neorientovaný acyklický graf, jehož veškeré připojené komponenty jsou stromy; jinými slovy, graf se skládá z nesouvislý unie stromů. Jako zvláštní případy jsou příklady lesů graf order-zero (les sestávající z nulových stromů), jeden strom a graf bez okrajů.Protože pro každý strom V − E = 1, můžeme snadno spočítat počet stromů, které jsou v lese odečtením rozdílu mezi celkovou vrcholů a celkem hrany. TV-TE = počet stromů v lese.

PolytreeEdit

polytree (nebo režie strom nebo orientovaný strom nebo jednotlivě připojené sítě) je zaměřen acyklický graf (DAG), jehož základní neorientovaný graf je strom. Jinými slovy, pokud nahradíme jeho směrované hrany neorientovanými hranami, získáme neorientovaný graf, který je připojen i acyklický.

někteří autoři omezují frázi „směrovaný strom“ na případ, kdy jsou okraje všechny směrovány k určitému vrcholu nebo všechny směřovány pryč od určitého vrcholu (viz arborescence).

PolyforestEdit

polyforest (nebo směrovaný les nebo orientovaný les) je směrovaný acyklický graf, jehož podkladovým neorientovaným grafem je les. Jinými slovy, pokud nahradíme jeho směrované hrany neorientovanými hranami, získáme neorientovaný graf, který je acyklický.

Někteří autoři omezit frázi „v režii les“ v případě, kdy hrany každého připojeného zařízení jsou zaměřena na konkrétní vrchol, nebo všechny směřovat od konkrétního vrcholu (viz větvení).

zakořeněný stromedit

zakořeněný strom je strom, ve kterém byl jeden vrchol označen kořenem. Okraje zakořeněný strom může být přiřazeno přirozené orientace, a to buď od nebo směrem do kořene, v takovém případě se konstrukce stává režie kořeny stromu. Když směrovaný zakořeněný strom má orientaci od kořene, nazývá se arborescence nebo out-tree; když má orientaci na kořen, nazývá se anti-arborescence nebo in-tree. Strom-cílem je částečné uspořádání na vrcholech stromu s u < v případě, a pouze tehdy, pokud jedinečnou cestu z kořene do v prochází u. Zakořeněný strom T, který je podgraf nějakého grafu G je normální strom, když na konec každé T-cesta v G jsou srovnatelné v tomto stromu-pořadí (Diestel 2005, str. 15). Zakořeněné stromy, často s další strukturou, jako je uspořádání sousedů na každém vrcholu, jsou klíčovou datovou strukturou v informatice; viz stromová datová struktura.

v kontextu, kde stromy mají mít kořen, strom bez jakéhokoli určeného kořene se nazývá volný strom.

označený strom je strom, ve kterém je každému vrcholu přidělen jedinečný štítek. Vrcholy označeného stromu na n vrcholech jsou obvykle uvedeny štítky 1, 2, …, n. rekurzivní strom je označený kořenový strom, kde vrcholové štítky respektují pořadí stromů (tj., pokud u < v pro dva vrcholy u A v, pak je štítek u menší než štítek v).

v kořenovém stromu je rodič vrcholu v vrchol připojený k v na cestě ke kořenu; každý vrchol má jedinečného rodiče kromě kořene, který nemá rodiče. Dítě vrcholu v je vrchol, jehož v je rodič. Ascendent vrcholu v je libovolný vrchol, který je buď rodičem v, nebo je (rekurzivně) ascendentem rodiče v. Potomek vrcholu v je libovolný vrchol, který je buď dítě v nebo je (rekurzivně) potomek některého z dětí z v. sourozenec na vrchol v je jakýkoliv jiný vrchol stromu, který má stejné rodiče jako v. list je vrchol, s žádné děti. Vnitřní vrchol je vrchol, který není listem.

výška vrcholu v kořenovém stromu je délka nejdelší sestupné cesty k listu z tohoto vrcholu. Výška stromu je výška kořene. Hloubka vrcholu je délka cesty k jeho kořenu (kořenová cesta). To je běžně nutné při manipulaci s různými samovyvažujícími se stromy, zejména stromy AVL. Kořen má hloubku nulovou, listy mají výšku nulovou a strom s jediným vrcholem (tedy kořenem i listem) má hloubku a výšku nulovou. Obvykle má prázdný strom (strom bez vrcholů, pokud jsou povoleny) hloubku a výšku -1.

k-ary strom je zakořeněný strom, ve kterém má každý vrchol nanejvýš k Děti. 2-ary stromy se často nazývají binární stromy, zatímco 3-ary stromy se někdy nazývají ternární stromy.

Objednal treeEdit

uspořádaný strom (nebo platan) je zakořeněný strom, v němž objednání je určen pro děti každého vrcholu. To se nazývá „platan“, protože objednávání dětí je ekvivalentní vkládání stromu v rovině, s kořenem nahoře a děti každý vrchol je nižší než vrchol. Vzhledem k vložení zakořeněného stromu do roviny, pokud jeden stanoví směr dětí, řekněme zleva doprava, pak vložení dává uspořádání dětí. Naopak, vzhledem k tomu, uspořádaný strom, a konvenčně kreslení root na vrcholu, pak dítě vrcholy v uspořádaný strom může být nakreslena zleva doprava, čímž se získá v podstatě unikátní rovinné vnoření.