Strom (graf)

Strom V teorii grafů se jako strom označuje graf, který je souvislý a neobsahuje žádnou kružnici. Lze jej ovšem definovat i dalšími způsoby:

Následující podmínky pro neorientovaný graf G jsou ekvivalentní: # G je strom. # Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty). +more # G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost). # G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) . # G je souvislý a \left | V \right | = \left | E \right |+ 1, kde V je množina vrcholů a E množina hran grafu G.

Stromy mohou být:

* neorientované * orientované (kořenové)

Les

Les je neorientovaný graf, ve kterém jsou libovolné dva vrcholy spojeny nejvýše jednou cestou. Ekvivalentní definice zní, že les je množina navzájem nepropojených stromů (odtud tedy jméno). +more Rovněž lze les definovat jako obyčejný graf, jehož žádný podgraf není kružnicí.

Zakořeněný strom{{Kotva|Kořen}}

Tzv. zakořeněný strom (též kořenový) má jeden význačný vrchol - kořen. +more Zakořeněním stromu je definována orientace hran: hrany pak vedou směrem od kořene (tato orientace je tak dána u každé hrany, protože strom je acyklický). Dále se definují tyto pojmy: * Potomek určitého vrcholu je každý vrchol, do kterého vede z tohoto vrcholu orientovaná hrana * Vrchol, který nemá potomky, se nazývá list * Větev je (jednoznačně určená) cesta od kořene k listu.

Vztahy mezi uzly

Předchůdce a následovník

Uvažujme uzel A v kořenovém stromu, pak libovolný uzel X na jednoznačné cestě od kořene do uzlu A se nazývá „předchůdce“ uzlu A (předek). Uzel ležící na cestě z uzlu A do libovolného listu stromu se nazývá „následovník“ uzlu (potomek). +more Předci a potomci ve stromu.

Rodič a dítě

Bezprostředně následující uzel ve směru z kořene do uzlu se nazývá „dítě“ nebo „syn“ uzlu (anglicky child); uzel bezprostředně předcházející je „rodič“ uzlu (anglicky parent). Kořen stromu nemá rodiče a list stromu nemá žádné syny. +more Ostatní uzly mohou mít libovolný počet synů. Rodič a dítě ve stromu.

Vlastnosti

každý strom je bipartitní * každý strom se spočetně mnoha vrcholy je rovinný * kostra libovolného grafu je tvořena stromem * jsou-li d_1, d_2, \ldots, d_n stupně jednotlivých vrcholů, existuje na těchto vrcholech {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1} stromů (včetně těch, které jsou navzájem izomorfní)

Související články

Strom (datová struktura) * Binární strom * Halda (datová struktura) * List (graf)

Externí odkazy

Kategorie:Typy grafů Kategorie:Rovinné grafy