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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze