Pořadí vrcholů stromu
Úloha číslo: 4074
Ukažte, že pro každý strom s \(n\) vrcholy existuje pořadí vrcholů \(\{v_1,…,v_n\}\) takové, že pro každé \(i > 1\) platí, že \(v_i\) má právě jednoho souseda v množině \(\{v_1,…,v_{i-1}\}\).
Nápověda
Odebírejte vrcholy tak, aby každý měl jen jediného předchůdce.
Řešení
Pokud má strom dva vrcholy, pak je každé očíslování dobré.
Pokud má více vrcholů, má alespoň jeden vrchol, který není list, tak v tomto vrcholu zakořeníme strom. Nyní postupně odebereme kořen a každého jeho souseda prohlásíme za kořen (pracujeme s lesem). Každý kořen v daném okamžiku má právě jednoho souseda mezi již očíslovanými vrcholy.