Strom (graf)

Z Wikipedie, otevřené encyklopedie

V teorii grafů se jako strom označuje neorientovaný 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í:

1. G je strom.
2. Každé dva vrcholy z G jsou spojeny právě jednou cestou (jednoznačnost cesty).
3. G je souvislý a po odebrání libovolné hrany se stane nesouvislým (minimální souvislost).
4. G neobsahuje kružnici, ale po přidání libovolné hrany vznikne v G kružnice (maximální graf bez kružnic) .
5. G je souvislý a , kde V je množina vrcholů a E množina hran grafu G.

[editovat] 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). Rovněž lze les definovat jako obyčejný graf, jehož žádný podgraf není kružnicí.

[editovat] Zakořeněný strom

Je-li strom orientovaný, lze definovat tzv. zakořeněný strom, který má jeden význačný vrchol - kořen. Hrany pak vedou směrem od kořene (tuto orientaci lze zvolit u každé hrany, protože strom je acyklický). Dále se definují tyto pojmy:

• Vrchol, který nemá potomky se nazývá list
• Větev je (jediná) cesta od kořene k listu

[editovat] 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 stupně jednotlivých vrcholů, existuje na těchto vrcholech stromů (včetně těch, které jsou navzájem izomorfní)