Definujte strom, les, list. Formulujte tvrzení o existenci listů.

Strom, les a list

Strom - graf G nazveme stromem pokud je acyklický a souvislý

Les - graf G nazveme lesem pokud je acyklický

List - vrchol grafu G nazveme listem pokud má deg(v) = 1

Základní vlastnosti stromů

Věta o existenci listů

• Každý strom T s alespoň 2 vrcholy obsahuje alespoň dva listy

Důkaz

• Nechť P je nejdelší cesta v T
• Nechť u a v jsou její koncové vrcholy