V matematice, přesněji v teorii grafů, je strom neřízený graf, ve kterém jsou libovolné dva vrcholy spojeny přesně jednou jednoduchou cestou. Jinými slovy, každý spojený graf bez cyklů je strom. Les je nesouvislé spojení stromů.
Různé druhy datových struktur označované jako stromy v informatice jsou v teorii grafů ekvivalentní stromům, i když takové datové struktury jsou běžně zakořeněné stromy a mohou mít další uspořádání větví.
Strom je neřízený jednoduchý graf G, který splňuje některou z následujících rovnocenných podmínek:
Pokud G má konečně mnoho vrcholů, řekněme n z nich, pak výše uvedené výroky jsou také ekvivalentní některou z následujících podmínek:
List je vrchol stupně 1. Vnitřní vrchol je vrchol stupně alespoň 2.
Strom s neredukovatelným (nebo sériově redukovaným) stromem je strom, ve kterém není žádný vrchol stupně 2.
Les je neřízený graf, jehož všechny spojené složky jsou stromy; jinými slovy, graf se skládá z nesouvislého spojení stromů. Ekvivalentně je les neřízený graf bez cyklu. Jako zvláštní případy, prázdný graf, jediný strom a diskrétní graf na množině vrcholů (tedy graf s těmito vrcholy, který nemá hrany), to vše jsou příklady lesů.
Pojem živý plot někdy odkazuje na uspořádanou sekvenci stromů.
Polystrom nebo orientovaný strom je směrovaný graf s maximálně jednou neřízenou cestou mezi libovolnými dvěma vrcholy. Jinými slovy, polystrom je směrovaný acyklický graf, pro který neexistují ani neřízené cykly.
Směrovaný strom je směrovaný graf, který by byl stromem, pokud by směry na okrajích byly ignorovány. Někteří autoři omezují frázi na případ, kdy jsou všechny okraje směrovány k určitému vrcholu, nebo všechny směrovány od určitého vrcholu (viz arborescence).
Strom se nazývá kořenový strom, pokud byl určen jeden vrchol jako kořen, v takovém případě mají okraje přirozenou orientaci, směrem ke kořenu nebo od něj. Stromový řád je částečné řazení na vrcholech stromu s u ≤ v tehdy a jen tehdy, pokud unikátní cesta od kořene k v prochází u. Kořenový strom, který je podgrafem nějakého grafu G, je normální strom, pokud jsou konce každé hrany v G v tomto stromovém řádu srovnatelné, kdykoli jsou tyto konce vrcholy stromu (Diestel 2005, str. 15). Kořenové stromy, často s dodatečnou strukturou, jako je řazení sousedů na každém vrcholu, jsou klíčovou datovou strukturou v informatice; viz stromová datová struktura. V kontextu, kdy stromy mají mít kořen, se strom bez určeného kořene nazývá svobodný strom.
V kořenovém stromu je rodičem vrcholu vrchol, který je s ním spojen na cestě ke kořeni; každý vrchol kromě kořene má jedinečného rodiče. Dítě vrcholu v je vrchol, jehož v je rodičem.
Označený strom je strom, ve kterém je každý vrchol označen jedinečným štítkem. Vrcholy označeného stromu na n vrcholech jsou obvykle označeny štítky 1, 2, …, n. Rekurzivní strom je označený kořenový strom, kde štítky vrcholů respektují pořadí stromů (tj. pokud u < v pro dva vrcholy u a v, pak je štítek u menší než štítek v).
n-ary strom je kořenový strom, pro který má každý vrchol maximálně n dětí. 2-ary stromy se někdy nazývají binární stromy, zatímco 3-ary stromy se někdy nazývají ternární stromy.
Konečný vrchol stromu je vrchol stupně 1. U kořenového stromu jsou všechny listy konečnými vrcholy; navíc kořen, ne-li list sám, je konečným vrcholem, má-li právě jedno dítě.
n-ary strom je kořenový strom, pro který má každý vrchol maximálně n dětí. 2-ary stromy se někdy nazývají binární stromy, zatímco 3-ary stromy se někdy nazývají ternární stromy.
Konečný vrchol stromu je vrchol stupně 1. U kořenového stromu jsou všechny listy konečnými vrcholy; navíc kořen, ne-li list sám, je konečným vrcholem, má-li právě jedno dítě.
Příklad stromu vpravo má 6 vrcholů a 6 − 1 = 5 hran. Jedinečná jednoduchá cesta spojující vrcholy 2 a 6 je 2-4-5-6.
Cayleyho vzorec uvádí, že na n označených vrcholech jsou stromy nn−2. Lze to dokázat tím, že nejprve ukazujeme, že počet stromů s vrcholy 1,2,…,n, o stupních d1,d2,…,dn resp. je multinomiální koeficient
Alternativní důkaz používá Prüferovy sekvence.
Cayleyho vzorec je zvláštním případem úplných grafů v obecnějším problému počítání překlenujících stromů v neřízeném grafu, který je řešen maticovou stromovou větou. Podobný problém počítání všech podstromů bez ohledu na velikost se ukázal jako #P-úplný v obecném případě (Jerrum (1994)).
Počítání počtu neoznačených volných stromů je těžší problém. Není znám žádný uzavřený vzorec pro počet t(n) stromů s n vrcholy až do izomorfismu grafu. Prvních několik hodnot t(n) jsou:
Ne.
Vydra (1948) prokázal asymptotický odhad:
s D = 0,43992401257… a α stejné jako výše (srov. Knuth (1997), Chap. 2.3.4.4 a Flajolet & Sedgewick (2009), Chap. VII.5).
Hvězdný graf je strom, který se skládá z jednoho vnitřního vrcholu (a listů n − 1). Jinými slovy, hvězdný graf řádu n je strom řádu n s co největším počtem listů. Jeho průměr je nejvýše 2.
Strom se dvěma listy (nejmenším možným) je graf cesty. Pokud jsou všechny vrcholy ve stromě ve vzdálenosti jedna z podgrafu centrální cesty, pak strom je strom housenky. Pokud jsou všechny vrcholy ve vzdálenosti dvě z podgrafu centrální cesty, pak strom je humr.