Strom (graf): Porovnání verzí

'''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 [[Graf (teorie grafů)|obyčejný graf]], jehož žádný [[podgraf]] není [[Kružnice (graf)|kružnicí]].

 

Tzv. '''zakořeněný strom''' (též '''kořenový''') má jeden význačný vrchol – ''kořen''. 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